Visibility Graphs of Points, Segments and Polygons — Problem 35

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph, and put $n=|V|$. A set $D\subseteq V$ is a dominating set if \[ \forall v\in V\setminus D\;\exists u\in D:\ \{u,v\}\in E. \] Its minimum possible cardinality is the domination number \[ \gamma(G)=\min\{\,|D|:D\subseteq V\text{ is a dominating set of }G\,\}. \] In particular, $\gamma(G)=0$ when $V=\varnothing$.

Let $\mathcal V$ denote the intended class of visibility graphs. Under the usual polynomial-time interpretation of an approximation-algorithm problem, the requested statement is: construct an algorithm $A$ and an absolute constant $C\geq 1$, independent of the input and its size, such that for every $G\in\mathcal V$, the algorithm returns a dominating set $D=A(G)$ satisfying \[ |D|\leq C\,\gamma(G), \] with running time polynomial in the length of the specified input representation.

The supplied record does not define $\mathcal V$ or the input representation. Its source title includes points, segments, and polygons, whereas its discussion relates domination to the art gallery problem in polygons. These descriptions do not specify a unique visibility model. In particular, the underlying geometric objects, adjacency and boundary conventions, permitted polygonal domains, guard locations and coverage requirements, and availability of a geometric representation remain unresolved. Thus the displayed algorithmic target is conditional on specifying these data; it is not a fully determined problem for a particular visibility class.

The source reports NP-hardness through the art gallery connection, citing ll-ccagp-86 and ls-cavg-95, and an $O(\log n)$-approximation following algorithms attributed to Ghosh, citing g-apat-2006 and g-apatpp-2010. These are supplied background claims whose precise models and applicability are not established by this record. The registry labels the problem open; this label is supplied curation, not an independently verified mathematical or literature assessment.

Short English statement

Find a polynomial-time algorithm that, for every graph in the intended visibility class, produces a dominating set within a fixed constant factor of the minimum size. The visibility class, geometric conventions, and input representation must first be specified. The supplied source connects this question to polygon guarding and reports an $O(\log n)$ approximation, but does not supply the hypotheses needed to make that connection precise.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $800561$, source code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 35." The registry attributes the problem to Ghosh and Goswami, gives the year 2010, and labels it open.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 35. Supplied source URL: https://arxiv.org/abs/1012.5187. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not access or verification performed for this draft.
• The supplied statement cites ll-ccagp-86 and ls-cavg-95 for NP-hardness of the polygon art gallery problem. Their bibliographic entries and precise problem variants are not supplied.
• The supplied statement cites g-apat-2006 and g-apatpp-2010 for approximation algorithms attributed to Ghosh. Their bibliographic entries and applicable geometric hypotheses are not supplied.