An intersection representation \(\mathcal{R}\) of a graph \( G = (V , E)\) is a family of \(\{\mathcal{R}_u\}\) \(u\in V\) sets such that \(uv \in E\) if and only if \({\mathcal{R}_u}\bigcap{\mathcal{R}_v}\neq \emptyset\). When \(\mathcal{R}\) is a collection of geometric objects, it is said to be a geometric intersection representation of \(G\). When \(\mathcal{R}\) is a collection of simple unbounded curves on the plane, it is called a string representation. A graph \(G\) is a string graph if \(G\) has a string representation. String graphs are important as it contains all intersection graphs of connected sets in \(\mathcal{R}^2\). String graphs have been intensively studied both for practical applications and theoretical interest. S. Benzer [“On the topology of the genetic fine structure”, Proc. Natl. Acad. Sci. 45, No. 11, 1607–1620 (1959; doi:10.1073/pnas.45.11.1607)] introduced string graphs while exploring the topology of genetic structures. F. W. Sinden [Bell Syst. Tech. J. 45, 1639–1662 (1966; Zbl 0144.45601)] considered the same constructs at Bell Labs. In 1976, Graham introduced string graphs to the mathematics community at the open problem session of a conference in Keszthely. Since then, many researchers have been carrying out extensive research on string graphs. The graph classes like planar graphs, chordal graphs, cocomparability graph, disk graphs, rectangle intersection graphs, segment graphs, and circular arc graphs are subclasses of string graphs. Any intersection graph of arc-connected sets on the plane is a string graph. However, not all graphs are string graphs and this is the reason why people study the computational complexities of various optimisation problems in string graphs and their subclasses.
In this paper, the authors propose constant factor approximation algorithms for the Minimum Dominating Set (MDS) problem on string graphs.
A dominating set of a graph \(G = (V , E)\) is a subset \(D\) of vertices \(V\) such that each vertex in \(V\backslash D\) is adjacent to some vertex in \(D\). The Minimum Dominating Set (MDS) problem is to find a minimum cardinality dominating set of a graph \(G\).
The readers can read the paper by M. Chlebík and J. Chlebíková [Inf. Comput. 206, No. 11, 1264–1275 (2008; Zbl 1169.68037)] to see that it is not possible to approximate the MDS problem on string graphs.
Thus, researchers are compelled to develop approximation algorithms for the MDS problem on various subclasses of string graphs. Planar graphs, chordal graphs, disk graphs, unit disk graphs, rectangle intersection graphs, intersection graphs of homothets of convex objects, etc. are examples. M. de Berg et al. [Theor. Comput. Sci. 769, 18–31 (2019; Zbl 1421.68071)] studied the fixed-parameter tractability of the MDS problem on various classes of geometric intersection graphs. T. Erlebach and E. J. van Leeuwen [Lect. Notes Comput. Sci. 4957, 747–758 (2008; Zbl 1136.68568)] gave constant-factor approximation algorithms for intersection graphs of \(r\)-regular polygons, where \(r\) is an arbitrary constant, for pairwise homothetic triangles, and rectangles with bounded aspect ratio.
A. Asinowski et al. [J. Graph Algorithms Appl. 16, No. 2, 129–150 (2012; Zbl 1254.68184)] introduced the concept of \(B_k\)-VPG graphs to initiate a systematic study of string graphs and its subclasses in the year. A path is a simple rectilinear curve made of axis-parallel line segments, and a \(k\)-bend path is a path having \(k\) bends. The \(B_k\)-VPG graphs are intersection graphs of \(k\)-bend paths. Asinowski et al. have shown that any string graph has a \(B_k\)-VPG representation for some \(k\). M. J. Katz et al. [Comput. Geom. 30, No. 2, 197–205 (2005; Zbl 1162.68751)] proved the NP-hardness of the MDS problem on \(B_0\)-VPG graphs. An interesting fact is that a sublogarithmic approximation algorithm for the MDS problem on \(B_0\)-VPG graphs is still unknown. It is to be noted that intersection graphs of orthogonal segments having unit length, i.e. unit \(B_0\)-VPG graphs is a subclass of \(B_0\)-VPG graphs.
In this paper, the authors show that the MDS problem is NP-hard on unit \(B_0\)-VPG graphs. This result strengthens a result of Katz et al. [loc. cit.]. They also propose the first constant-factor approximation algorithm for the MDS problem on unit \(B_0\)-VPG graphs. Specifically, the authors prove the following theorems.
Theorem 1. It is NP-Hard to solve the MDS problem on unit \(B_k\)-VPG graphs with \(k \geq 0\).
Theorem 2. Given a unit \(B_0\)-VPG representation of a graph \(G\) with \(n\) vertices, there is an \(O(n^5)\)-time 18-approximation algorithm to solve the MDS problem on \(G\).
Theorem 3. Given a unit \(B_k\)-VPG representation of a graph \(G\) with \(n\) vertices, there is an \(O(k^2n^5)\)-time \(O(k^4)\)-approximation algorithm to solve the MDS problem on \(G\).
Theorem 4. Given a vertically-stabbed L-representation of a graph \(G\) with \(n\) vertices, there is an \(O(n^5)\)-time 8-approximation algorithm to solve the MDS problem on \(G\).
Theorem 5. Assuming the Unique Games Conjecture to be true, it is not possible to have a polynomial time \((2 -\epsilon)\)-approximation algorithm for the MDS problem on rectangle overlap graphs for any \(\epsilon > 0\).
Theorem 6. Given a stabbed rectangle overlap representation of a graph \(G\) with \(n\) vertices, there is an \(O(n^5)\)-time 656-approximation algorithm for the MDS problem on \(G\).
The interval overlap graphs and intersection graphs of diagonally anchored rectangles are strict subclasses of stabbed rectangle overlap graphs.
Note that approximation algorithms for optimization problems like Maximum Independent Set and Minimum Hitting Set on intersection graphs of “stabbed” geometric objects have been studied by different authors.
Proofs of Theorem 2, 3, 4, and 6 use two crucial lemmas. The first one is about the stabbing segment with rays SSR problem and the second one is about the stabbing rays with segment SRS problem, both introduced by Katz et al. [loc. cit.].
The definitions of both SSR and SRS problems are given below. Stabbing segments with rays SSR.
Input: A set R of disjoint leftward-directed horizontal semi-infinite rays and a set of disjoint vertical segments.
Output: A minimum cardinality subset of \(R\) that intersect all segments in \(V\).
Stabbing rays with segments SRS.
Input: A set \(R\) of disjoint leftward-directed horizontal semi-infinite rays and a set of disjoint vertical segments.
Output: A minimum cardinality subset of \(V\) that intersect all rays in \(R\).
Let \(\mathrm{SSR}(R, V)\) (resp. \(\mathrm{SRS}(R,V)\)) denote an SSR instance (resp. an SRS instance) where \(R\) is a given set of disjoint leftward-directed horizontal semi-infinite rays and \(V\) is a given set of disjoint vertical segments. Katz et al. [loc. cit.] gave dynamic programming-based polynomial time algorithms for both the SSR problem and the SRS problem. Here the authors, to prove Theorems 2, 3, 4, and 6, have developed an upper bound on the ratio of the cardinality of the optimal solution of an SSR instance (and SRS instance) with the optimal cost of the corresponding relaxed LP formulation(s).
Therefore, they have proved the following lemmas.
Lemma 1. Let \(C\) be an ILP formulation of an \(\mathrm{SSR}(R,V)\) instance. There is an \(O((n +m) \log(n +m))\)-time algorithm to compute a set \(D\subseteq R\) which gives a feasible solution of \(C\) and \(|D|\leq 2\cdot \mathrm{OPT}(C_1)\) where \(n = |R|, m- |V |\) and \(C_1\) is the relaxed LP formulation of \(C\).
Lemma 2. Let \(C\) be an ILP formulation of an SRS(R,V) instance. There is an \(O(n \log n)\) time algorithm to compute a set \(D \subsetneq V\) which gives a feasible solution of \(C\) and \(|D|\leq 2\cdot \mathrm{OPT}(C_l)\) where \(n = |V |\) and \(C_l\) is the relaxed LP formulation of \(C\).
To prove both the above lemma, the authors have not explicitly solved the LP(s). Moreover, since \(\mathrm{OPT}(C_l) \leq \mathrm{OPT}(C)\), the algorithm of Lemma 1 provides an approximate solution to the \(\mathrm{SSR}(R,V)\) instance with approximation ratio 2. So, it is argued that Theorem 7 is a consequence of Lemma 1.
Theorem 7. There is an \(O((n +m) \log(n +m))\)-time 2-approximation algorithm for SSR problem where \(n\) and \(m\) are the number of rays and segments, respectively.
In Section 2.1 and Section 2.2, the authors have proved the hardness results (Theorem 1 and Theorem 5). In Section 3 and Section 4, they have proved Lemma 1 and Lemma 4, respectively. In Section 5, they have applied both Lemma 1 and Lemma 2 to prove Theorem 4. Then in Sections 6, 7, and 8, they have proved Theorem 2, Theorem 3, and Theorem 6, respectively. The authors end the paper with the following four questions.
Question 1. What are the integrality gaps of the SSR and the SRS problems?
Question 2. Is there a \(c\)-approximation algorithm for the MDS problem on unit \(B_0\)-VPG graphs with \(c < 18\)?
Question 3. Is there a constant-factor approximation algorithm for the MDS problem on \(B_0\)-VPG graphs? Is there an \(O(\log k)\)-approximation algorithm for the MDS problem on \(B_k\)-VPG graphs?
Question 4. Is there a \(c\)-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs with \(c < 656\)?
We see in this paper an amalgamation of areas such as linear programming, algorithms, NP-hardness and graph theory. It has an exhaustive list of bibliography with 49 papers and all of these papers are used in the writing of this paper. The standard of the paper is high. The researchers will learn a lot by reading this paper. There are four questions for which the researchers can break their heads and find answers. Overall the paper is classic and it contains a lot of treasure in it.