1 Introduction↩︎

Given a graph \(G = (V,E)\), a subset \(D\) of \(V\) is a dominating set of \(G\) if every vertex in \(V \setminus D\) is adjacent to at least one vertex of \(D\). The minimum dominating set (MDS) problem is to compute a dominating set \(D\) of minimum cardinality. The MDS problem is fundamental in the field of graph theory. The problem has real-world applications in network design, facility location, and the analysis of social networks [1]–[5]. It has been shown that the MDS problem is NP-hard on general graphs [6], as are many other variants of domination, including total dominating set, connected dominating set, independent dominating set, and dominating clique [6]–[8]. All of these variants, except for independent dominating set, are also NP-hard on chordal graphs [9]–[13]. For a summary of the complexity of these variants on other classes of graphs, see Table 1 in [14].

A circle graph \(G=(V,E)\) is the intersection graph of a set \({{\cal{C}}}\) of chords in a circle, such that each vertex \(v \in V\) uniquely corresponds to a chord, and there is an edge \((u,v) \in E\) if and only if the two chords corresponding to \(u\) and \(v\) intersect. \({{\cal{C}}}\) is called a chord intersection model of the circle graph \(G\). Equivalently, an interval model of \(G\) is a set \({{\cal{I}}}\) of intervals located on a horizontal line \(L\), such that the vertices of \(V\) uniquely correspond to the intervals of \({{\cal{I}}}\), and two vertices in \(V\) are adjacent if and only if the corresponding intervals intersect, i.e., overlap, but neither contains the other. The three models of a circle graph (as a graph, as a set of chords, and as a set of intervals) are equivalent via linear time transformations [15]. Thus, w.l.o.g., when specifying instances of problems, we assume the availability of the most convenient model.

Circle graphs have been extensively studied in the literature [15]–[20]. Many problems that are NP-hard in general graphs become solvable in polynomial time when restricted to circle graphs, including maximum clique and maximum independent set [15], minimum feedback vertex set [21], and dominating clique [19]. On the other hand, some problems remain NP-hard in circle graphs, such as Hamiltonian cycle [22], minimum clique cover [23], and \(k\)-coloring for \(k \ge 4\) [24].

Determining the complexity of the MDS problem in circle graphs was first asked by Johnson [25] in 1985. This question remained open until Keil [19] proved in 1993 that the MDS problem is NP-complete. Later, Damian and Pemmaraju [17] provided a \((2 + {\varepsilon})\)-approximation scheme for the problem and proved that the problem is APX-hard [18]. Finally, Bousquet et al. [16] showed that the MDS problem in circle graphs is \(W[1]\)-hard parameterized by the size of the solution.

In this paper, we assume that \({{\cal{C}}}\) consists of chords colored red and blue, such that no two chords of the same color intersect; see Figure 1 (a). Hence, the resulting circle graph is bipartite. Moreover, we also use the interval model. That is, the intervals in \({{\cal{I}}}\) are partitioned into two sets: a set \({{\cal{I}}}_R\) of red intervals corresponding to the red chords of \({{\cal{C}}}\) and a set \({{\cal{I}}}_B\) of blue intervals corresponding to the blue chords of \({{\cal{C}}}\). For ease of presentation, we represent the intervals of \({{\cal{I}}}_R\) as red curves below the line \(L\) and the intervals of \({{\cal{I}}}_B\) as blue curves above \(L\). An example of a chord intersection model \({{\cal{C}}}\) of a bipartite circle graph and its corresponding interval model \({{\cal{I}}}\) is given in Figure 1.

1.0.0.1 Our contributions.

We study the MDS problem on bipartite circle graphs, a natural subclass of circle graphs that admits a chord representation in which the chords can be colored red and blue so that no two chords of the same color intersect. We prove (in Section 2) that the problem remains NP-hard even under this restriction. Since the known NP-hardness construction for circle graphs (used by Keil [19]) does not preserve bipartiteness, we provide a new reduction from Planar Monotone 3-SAT. We also provide (in Section 3) a polynomial-time \(2\)-approximation algorithm. The algorithm computes an optimal set of red intervals that dominate all blue intervals and, symmetrically, an optimal set of blue intervals that dominate all red intervals. Finally, we show (in Section 4) that the problem admits a polynomial-time approximation scheme (PTAS). We show that the standard local-search yields a PTAS for computing a minimum dominating set in bipartite circle graphs.

2 NP-hardness↩︎

In this section, we prove that the MDS problem on bipartite circle graphs is NP-hard. More precisely, we prove that, given a bipartite circle graph \(G=(V,E)\) and an integer \(k\), determining whether there exists a dominating set of \(G\) of size at most \(k\) is NP-hard. The proof is by a reduction from Planar Monotone 3-SAT, which is known to be NP-hard [26].

A 3-SAT formula is monotone if each clause consists of only three positive or only three negative literals. The corresponding graph of 3-SAT formula \({\varphi}\) is a bipartite graph \(G_{\varphi}\), such that each variable and each clause in \({\varphi}\) is a vertex in \(G_{\varphi}\) and there is an edge between a variable \(x_i\) and a clause \(C_j\) if and only if \(x_i\) or its negation \(\overline{x_i}\) appears in \(C_j\). If \(G_{\varphi}\) is planar, then \({\varphi}\) is called a planar 3-SAT formula.

Given a planar monotone 3-SAT formula \({\varphi}\), a monotone rectilinear representation of \({\varphi}\) is a rectilinear representation where (i) the variables are drawn as axis-aligned rectangles arranged along a horizontal line \(l\), (ii) all positive clauses are drawn as axis-aligned rectangles and lie on one side (above) of \(l\), (iii) all negative clauses are drawn as axis-aligned rectangles and lie on the other side (below) of \(l\), and (iv) the edges connecting the variables to the clauses are drawn as vertical segments. See Figure 2 for an example.

Let \({\varphi}\) be a planar monotone 3-SAT formula defined on the variables \(x_1,\dots,x_n\) and the clauses \(C_1,\dots,C_m\), with its monotone rectilinear representation. We show how to construct, in polynomial time, a set of bicolored intervals \({{\cal{I}}}\) on a horizontal line \(L\) (corresponding to a bipartite circle graph \(G\)) and fix an integer \(k\), such that \(G\) has a dominating set of size \(k\) if and only if \({\varphi}\) is satisfiable. Let \(L\) be a horizontal line. We draw the blue intervals as curves above \(L\) and the red intervals as curves below \(L\).

2.0.0.1 Variable gadget.

For each variable \(x_i\), we create a set \(A_i\) consisting of 10 intervals: five red intervals \(r_i^1,r_i^2,\dots, r_i^5\) arranged from left to right on \(L\) and five blue intervals \(b_i^1,b_i^2,\dots, b_i^5\) arranged from right to left on \(L\), such that (i) \(r_i^2\) is contained in \(r_i^3\), and \(r_i^1, r_i^3, r_i^4, r_i^5\) are pairwise disjoint, (ii) \(b_i^2\) is contained in \(b_i^3\), and \(b_i^1, b_i^3, b_i^4, b_i^5\) are pairwise disjoint, and (iii) \((r_i^1, b_i^5, r_i^2, b_i^4, r_i^4, b_i^2, r_i^5, b_i^1)\) forms a simple path in \(G\); see Figure 3.

Let \(R_i=\{r_i^2,r_i^3\}\) and \(B_i=\{b_i^2,b_i^3\}\). Notice that each set of intervals \(A_i\) corresponding to a variable \(x_i\) can be optimally dominated by three intervals from \(A_i\). Moreover, any minimum dominating set \(D_i\) of \(A_i\) must satisfy: (i) \(D_i\) contains only one of the intervals \(r_i^1,b_i^5\), only one of the intervals \(r_i^4,b_i^4\), and only one of the intervals \(r_i^5,b_i^1\), (ii) \(D_i\) does not contain any of the intervals of \(R_i \cup B_i\), (iii) if \(r_i^1 \in D_i\), then \(b_i^1 \notin D_i\), and (iv) if \(r_i^4 \in D_i\), then \(b_i^4 \notin D_i\). This follows by a straightforward case analysis on the constant-size gadget in Figure 3. Therefore, we have the following observation.

In our construction, we show that there exists a minimum dominating set of \({{\cal{I}}}\) that includes only one of the sets \(\{r_i^1,b_i^4,r_i^5\}\) or \(\{b_i^1,r_i^4,b_i^5\}\). Thus, we associate the set \(\{r_i^1,b_i^4,r_i^5\}\) with the assignment \(x_i = T\) and the set \(\{b_i^1,r_i^4,b_i^5\}\) with the assignment \(x_i = F\).

We arrange (the intervals of) the gadgets \(A_1, A_2,\dots, A_n\) on \(L\), such that \(R_n \subset R_{n-1} \subset \dots \subset R_2 \subset R_1\), \(B_1 \subset B_2 \subset \dots \subset B_n\), and the intervals of every two gadgets \(A_i\) and \(A_j\) can intersect each other only with \(R_i, B_i\) and \(R_j, B_j\); see Figure 4.

2.0.0.2 Positive clause gadgets.

For each positive clause \(C_j=(x_p \vee x_q \vee x_t)\), we create two disjoint blue intervals \(b_j^{p,q},b_j^{q,t}\). Moreover, we create a set \(R'_j\) containing two red intervals \(r'_j, r''_j\), such that \(r'_j\) is contained in \(r''_j\) and they intersect both \(b_j^{p,q}\) and \(b_j^{q,t}\); see Figure 5 (a).

2.0.0.3 Negative clause gadgets.

The gadget of each negative clause \(C_l=(\overline{x_p} \vee \overline{x_q} \vee \overline{x_t})\) is created symmetrically; see Figure 5 (b).

2.0.0.4 Connection between clauses and variables.

The connection between a positive clause \(C_j=(x_p \vee x_q \vee x_t)\) and the gadgets corresponding to the variables \(x_p, x_q, x_t\) is established via the set \(R'_j\); as shown in Figure 6 (a). More precisely, We locate the blue intervals \(b_j^{p,q},b_j^{q,t}\) of \(C_j\) along \(L\), such that

• the two red intervals of \(R'_j\) are contained in the interval \(r_q^1\) of \(x_q\);

• the left endpoint of \(b_j^{p,q}\) is located inside the interval \(r_p^1\) of \(x_p\); and

• the right endpoint of \(b_j^{q,t}\) is located inside the interval \(r_t^1\) of \(x_t\).

The connection between a negative clause and the gadgets of its variables is made symmetrically, as shown in Figure 6 (b). Figure 7 shows the construction of \({{\cal{I}}}\) corresponding to the formula in Figure 2.

Clearly, the final set \({{\cal{I}}}\) contains \(10n + 4m\) intervals and is constructed in polynomial time. Moreover, the intervals in \({{\cal{I}}}\) are partitioned into red and blue, and no two intervals of the same color intersect. Hence, the intersection graph of the intervals in \({{\cal{I}}}\) is bipartite. Let \(G\) be the bipartite circle graph corresponding to \({{\cal{I}}}\).

It remains to fix the integer \(k\). By Lemma 1, any minimum dominating set of \(G\) must contain at least three intervals to dominate each set \(A_i\), at least one interval to dominate each set \(R'_j\), and at least one interval to dominate each set \(B'_l\). Thus, we set \(k = 3n + m\).

The following theorem summarizes the result of this section.

3 Approximation Algorithm↩︎

Let \({{\cal{I}}}={{\cal{I}}}_R \cup {{\cal{I}}}_B\) be a set of intervals arranged along a horizontal line \(L\) and corresponding to a bipartite circle graph \(G\), such that \({{\cal{I}}}_R\) is a set of \(n\) red intervals, and \({{\cal{I}}}_B\) is a set of \(m\) blue intervals. Let \(D^*\) be a minimum dominating set of \(G\), and let \(|D^*|\) denote its size. In this section, we present a polynomial-time approximation algorithm that computes a dominating set \(D\) of \(G\), such that \(|D| \le 2\cdot|D^*|\). The idea of the algorithm is to compute a minimum dominating set \(R\) that dominates all the blue intervals of \({{\cal{I}}}_B\) and a minimum dominating set \(B\) that dominates all the red intervals of \({{\cal{I}}}_R\), and to take \(D = R \cup B\). In the following, we show how to compute the set \(R\). Computing the set \(B\) is symmetric.

3.1 Computing the set \(\boldsymbol{R}\)↩︎

In this section, we present a dynamic programming algorithm that computes a minimum dominating set \(R\) of the blue intervals of \({{\cal{I}}}_B\). Notice that if there are blue intervals that do not intersect any red interval from \(I_R\), then they must be in any dominating set of \({{\cal{I}}}_B\). Therefore, we may assume that each blue interval intersects at least one red interval, and thus \(R\) contains only red intervals.

Let \(N=n+m\), and let \({{\cal{P}}}=\{p_1, p_2, \dots, p_{2N}\}\) be the set of endpoints of the intervals in \({{\cal{I}}}\) listed from left to right. We assume, w.l.o.g., that the points in \({{\cal{P}}}\) are distinct and located on consecutive integers \(1,2,\dots,2N\). For an interval \(I \in {{\cal{I}}}\), let \(s(I)\) and \(e(I)\) denote the starting and ending points (i.e., the left and right endpoints) of \(I\), respectively, and let \(C(I)\) denote the set of intervals in \({{\cal{I}}}\) that intersect \(I\), i.e., \(C(I) = \{I' \in {{\cal{I}}}:s(I') < s(I) < e(I') < e(I) \text{ or } s(I) < s(I') < e(I) < e(I')\}\).

For each \(1 \le i \le j \le 2N\), let \({{\cal{P}}}[i,j]=\{p_i,p_{i+1},\dots,p_j\}\) be the subset of \({{\cal{P}}}\) containing the points between \(p_i\) and \(p_j\). Let \({{\cal{I}}}_B[i,j]\) denote the set of blue intervals in \({{\cal{I}}}_B\) that have both endpoints in \({{\cal{P}}}[i,j]\), i.e., \({{\cal{I}}}_B[i,j] = \{b \in {{\cal{I}}}_B:i \le s(b) < e(b) \le j\}\). Let \({{\cal{I}}}^+_R[i,j]\) denote the set of red intervals in \({{\cal{I}}}_R\) whose ending points are in \({{\cal{P}}}[i,j]\), i.e., \({{\cal{I}}}^+_R[i,j] = \{r \in {{\cal{I}}}_R:i \le e(r) \le j\}\).

3.1.0.1 Subproblems.

For each \(1 \le i \le j \le 2N\), a subproblem is defined on the points in \({{\cal{P}}}[i,j]\). More precisely, a subproblem is to compute the minimum number of red intervals from \({{\cal{I}}}^+_R[i,j]\) that dominate the blue intervals in \({{\cal{I}}}_B[i,j]\). For each subproblem \({{\cal{P}}}[i,j]\), we define \(O[i,j]\) to be the minimum number of red intervals from \({{\cal{I}}}^+_R[i,j]\) that dominate the blue intervals in \({{\cal{I}}}_B[i,j]\). If \(i=j\) or \({{\cal{I}}}_B[i,j] = \emptyset\), then we set \(O[i,j] = 0\).

Let \(b=LB[i,j]\) be the blue interval in \({{\cal{I}}}_B[i,j]\) having the leftmost starting point \(s(b)\). For each \(r \in C(b)\) such that \(e(r) \le j\), we define a value \(f(r)\) as follows:

• If \(s(b) < s(r) < e(b)\), then

  • if \(e(r) < j\), then \[\begin{align} f(r) = O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1] + O[e(r)+1,j] + 1, \end{align}\]

  • else (\(e(r) = j\)) \[\begin{align} f(r) = O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1]+1. \end{align}\]

• If \(s(b) < e(r) < e(b)\), then \[\begin{align} f(r) = O[s(b)+1, e(r)-1] + O[e(r)+1,j] + 1. \end{align}\]

The following lemma establishes the optimal substructure property of \(O[i,j]\).

Proof. If \(i=j\) or \({{\cal{I}}}_B[i,j] = \emptyset\), then there are no blue intervals to dominate, and hence \(O[i,j]=0\). Otherwise, let \(b=LB[i,j]\) and let \(r\) be the leftmost red interval in \(C(b)\) (i.e., having the leftmost starting point \(s(r)\)), such that \(f(r)\) is minimized over all \(r \in C(b)\) with \(e(r) \le j\). We distinguish between two cases.
Case 1: \(\boldsymbol{s(b) < s(r) < e(b)}\). We distinguish between two subcases according to \(e(r)\).
Case 1.1: \(\boldsymbol{e(r) < j}\). In this case, the blue intervals in \({{\cal{I}}}_B[i,j] \setminus C(r)\) are partitioned into three disjoint sets: \({{\cal{I}}}_B[s(b)+1, s(r)-1]\), \({{\cal{I}}}_B[s(r)+1,e(r)-1]\), and \({{\cal{I}}}_B[e(r)+1,j]\); see Figure 8. Let \(R[s(b)+1, s(r)-1]\), \(R[s(r)+1,e(r)-1]\), and \(R[e(r)+1,j]\) be minimum dominating sets of the blue intervals in \({{\cal{I}}}_B[s(b)+1, s(r)-1]\), \({{\cal{I}}}_B[s(r)+1,e(r)-1]\), and \({{\cal{I}}}_B[e(r)+1,j]\), respectively.

Clearly, since the red intervals in \({{\cal{I}}}_R\) do not intersect each other, we have \[\begin{align} R[s(b)+1, s(r)-1] \cap R[s(r)+1,e(r)-1] = \emptyset \;\;\text{ and } \; \; R[s(r)+1,e(r)-1] \cap R[e(r)+1,j] = \emptyset. \end{align}\] Moreover, since \(r\) is the leftmost interval in \(C(b)\), we also have \[\begin{align} R[s(b)+1, s(r)-1] \cap R[e(r)+1,j] = \emptyset, \end{align}\] otherwise, there is an interval \(r' \in R[s(b)+1, s(r)-1] \cap R[e(r)+1,j]\), such that \(s(b) < s(r') <s(r) < e(b) <e(r) < e(r')\), which implies that \(r' \in C(b)\) and \(s(r') < s(r)\), contradicting that \(r\) is the leftmost interval in \(C(b)\). However, there might be an interval \(r' \in R[e(r)+1,j]\), such that \(s(r') < s(b)\) and \(e(r) < e(r') < j\), i.e., \(r'\) starts before \(b\) and ends after \(r\). Hence, each interval \(r' \in R[s(b)+1, s(r)-1]\) has \(e(r') \in {{\cal{P}}}[s(b)+1, s(r)-1]\), each interval \(r' \in R[s(r)+1,e(r)-1]\) has \(e(r') \in {{\cal{P}}}[s(r)+1,e(r)-1]\), and each interval \(r' \in R[e(r)+1,j]\) has \(e(r') \in {{\cal{P}}}[e(r)+1,j]\). Thus, the sets \(R[s(b)+1, s(r)-1]\), \(R[s(r)+1,e(r)-1]\), and \(R[e(r)+1,j]\) are disjoint, \[\begin{align} R[s(b)+1, s(r)-1] & \subseteq {{\cal{I}}}^+_R[s(b)+1, s(r)-1], \\ R[s(r)+1,e(r)-1] & \subseteq {{\cal{I}}}^+_R[s(r)+1,e(r)-1], \text{ and} \\ R[e(r)+1,j] & \subseteq {{\cal{I}}}^+_R[e(r)+1,j]. \end{align}\] Moreover, we have \[\begin{align} O[s(b)+1, s(r)-1] & = |R[s(b)+1, s(r)-1]|, \\ O[s(r)+1,e(r)-1] & = |R[s(r)+1,e(r)-1]|, \text{ and} \\ O[e(r)+1,j] & = |R[e(r)+1,j]|. \end{align}\] Therefore, \(R[s(b)+1, s(r)-1] \cup R[s(r)+1,e(r)-1] \cup R[e(r)+1,j] \cup \{r\}\) is a minimum dominating set of \({{\cal{I}}}_B[i,j]\), and its size is \[\begin{align} O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1] + O[e(r)+1,j] + 1 = f(r). \end{align}\]

Case 1.2: \(\boldsymbol{e(r) = j}\). In this case, the blue intervals in \({{\cal{I}}}_B[i,j] \setminus C(r)\) are partitioned into two disjoint sets: \({{\cal{I}}}_B[s(b)+1, s(r)-1]\) and \({{\cal{I}}}_B[s(r)+1,e(r)-1]\). Let \(R[s(b)+1, s(r)-1]\) and \(R[s(r)+1,e(r)-1]\) be minimum dominating sets of the blue intervals in \({{\cal{I}}}_B[s(b)+1, s(r)-1]\) and \({{\cal{I}}}_B[s(r)+1,e(r)-1]\), respectively.

As in Case 1.1, since the red intervals in \({{\cal{I}}}_R\) do not intersect each other, we have \[\begin{align} R[s(b)+1, s(r)-1] \cap R[s(r)+1,e(r)-1] = \emptyset, \end{align}\] and each interval \(r' \in R[s(b)+1, s(r)-1]\) has \(e(r') \in {{\cal{P}}}[s(b)+1, s(r)-1]\) and each interval \(r' \in R[s(r)+1,e(r)-1]\) has \(e(r') \in {{\cal{P}}}[s(r)+1,e(r)-1]\). Thus, the sets \(R[s(b)+1, s(r)-1]\) and \(R[s(r)+1,e(r)-1]\) are disjoint, \[\begin{align} R[s(b)+1, s(r)-1] \subseteq {{\cal{I}}}^+_R[s(b)+1, s(r)-1], \;\;\text{ and } \;\; R[s(r)+1,e(r)-1] \subseteq {{\cal{I}}}^+_R[s(r)+1,e(r)-1]. \end{align}\] Moreover, \[\begin{align} O[s(b)+1, s(r)-1] = |R[s(b)+1, s(r)-1]| \;\;\text{ and } \;\; O[s(r)+1,e(r)-1] = |R[s(r)+1,e(r)-1]|. \end{align}\] Therefore, \(R[s(b)+1, s(r)-1] \cup R[s(r)+1,e(r)-1] \cup \{r\}\) is a minimum dominating set of \({{\cal{I}}}_B[i,j]\), and its size is \[\begin{align} O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1] + 1 = f(r). \end{align}\]
Case 2: \(\boldsymbol{s(b) < e(r) < e(b)}\). In this case, the blue intervals in \({{\cal{I}}}_B[i,j] \setminus C(r)\) are partitioned into two disjoint sets: \({{\cal{I}}}_B[s(b)+1, e(r)-1]\) and \({{\cal{I}}}_B[e(r)+1,j]\); see Figure 9. Let \(R[s(b)+1, e(r)-1]\) and \(R[e(r)+1,j]\) be minimum dominating sets of the blue intervals in \({{\cal{I}}}_B[s(b)+1, e(r)-1]\) and \({{\cal{I}}}_B[e(r)+1,j]\), respectively.

Since the red intervals in \({{\cal{I}}}_R\) do not intersect each other, we have \[\begin{align} R[s(b)+1, e(r)-1] \cap R[e(r)+1,j] = \emptyset, \end{align}\] and each interval \(r' \in R[s(b)+1, e(r)-1]\) has \(e(r') \in {{\cal{P}}}[s(b)+1, e(r)-1]\) and each interval \(r' \in R[e(r)+1,j]\) has \(e(r') \in {{\cal{P}}}[e(r)+1,j]\). Thus, the sets \(R[s(b)+1, e(r)-1]\) and \(R[e(r)+1,j]\) are disjoint, \[\begin{align} R[s(b)+1, e(r)-1] \subseteq {{\cal{I}}}^+_R[s(b)+1, e(r)-1], \;\text{ and } \;\; R[e(r)+1,j] \subseteq {{\cal{I}}}^+_R[e(r)+1,j]. \end{align}\] Moreover, \[\begin{align} O[s(b)+1, e(r)-1] = |R[s(b)+1, e(r)-1]| \;\;\text{ and } \;\; O[e(r)+1,j] = |R[e(r)+1,j]|. \end{align}\] Therefore, \(R[s(b)+1, e(r)-1] \cup R[e(r)+1,j] \cup \{r\}\) is a minimum dominating set of \({{\cal{I}}}_B[i,j]\), and its size is \[\begin{align} O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1] + 1 = f(r). \end{align}\]

Since \(r\) minimizes \(f(r)\), we have \(O[i,j] = f(r)\), and therefore \(O[i,j] = \underset{\underset{ e(r) \le j}{r \in C(b)}}{\min} f(r)\). ◻

According to Lemma 3, our goal is to compute \(O[1,2N] = |R|\).

3.1.1 Algorithm implementation and running time↩︎

We focus on computing \(O[1,2N] = |R|\). By slightly modifying the algorithm using a standard backtracking technique, an actual minimum dominating set \(R\) can also be recovered within asymptotically the same time complexity.

We compute \(O[1, 2N]\) using dynamic programming. The dynamic programming table \(O\) has \(2N\) rows and \(2N\) columns. Each entry \(O[i,j]\) stores the solution for the subproblem defined on \({{\cal{P}}}[i,j]\), i.e., the minimum number of red intervals from \({{\cal{I}}}^+_R[i,j]\) needed to dominate all blue intervals in \({{\cal{I}}}_B [i,j]\).

We fill in the table iteratively in such a way that, for each entry \(O[i,j]\), all of the entries needed to compute \(O[i,j]\) have already been computed. To this end, we fill the table \(O\) in increasing order of the length \(j-i\). For each \(1 \le i \le j \le 2N\), in increasing order of \(j-i\), if \(i=j\) or \({{\cal{I}}}_B[i,j] = \emptyset\), then we set \(O[i,j] = 0\). Otherwise, for \(b = LB[i,j]\) and for each \(r \in C(b)\) with \(e(r) \le j\), we compute \(O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1] + O[e(r)+1,j] + 1\), in case \(s(b) < s(r) < e(b) < e(r) < j\), \(O[s(b)+1, s(r)-1] + O[s(r)+1,e(r)-1] + 1\), in case \(s(b) < s(r) < e(b) < e(r) = j\), or \(O[s(b)+1, e(r)-1] + O[e(r)+1,j] + 1\), in case \(s(r) < s(b) < e(r)\), and take the minimum over these values; see Algorithm 10.

3.1.1.1 Running time.

For each interval \(b \in {{\cal{I}}}_B\), we can compute \(C(b)\) in \(O(n)\) time. For each entry \(O[i,j]\), we consider every red interval that intersects \(LB[i,j]\). Thus, \(O[i,j]\) can be computed in \(O(n)\) time. Since the table \(O\) has \(O(N^2)\) entries, the total running time for computing \(|R| = O[1,2N]\) is \(O(N^2 n) = O((n+m)^2n)\).

3.1.1.2 Recovering \(R\).

To recover the actual set \(R\), we store, for each entry \(O[i,j]\), a red interval \(r\) that attains the minimum. After the table has been filled, we backtrack from \(O[1,2N]\) and recursively collect the selected red intervals.

3.2 Approximating the MDS Problem↩︎

Recall that \(D^*\) denotes a minimum dominating set of \(G\). We compute a minimum dominating set \(R\) of red intervals that dominate the blue intervals in \({{\cal{I}}}_B\), using the algorithm described in Section 3.1. Using a symmetric algorithm, we compute a minimum dominating set \(B\) of blue intervals that dominate the red intervals in \({{\cal{I}}}_R\).

Let \(D = R \cup B\). By Lemma 4, \(|D| \le 2\cdot |D^*|\).

4 PTAS for the MDS Problem↩︎

Let \(G\) be a bipartite circle graph represented by a set \({{\cal{I}}}={{\cal{I}}}_R \cup {{\cal{I}}}_B\) of intervals arranged along a horizontal line \(L\), such that \({{\cal{I}}}_R\) is a set of \(n\) red intervals, and \({{\cal{I}}}_B\) is a set of \(m\) blue intervals. In this section, we show that the standard local-search algorithm leads to a PTAS for computing a minimum dominating set of \(G\). For the analysis, we use a separator-based technique introduced independently by Chan and Har-Peled [27] and by Mustafa and Ray [28]. The main part of this proof technique is to show the existence of a planar graph satisfying a locality condition (to be defined in Section 4.2).

The algorithm is given in Section 4.1, and the analysis of the approximation ratio is provided in Section 4.2.

4.1 The algorithm↩︎

A dominating set \(D \subseteq {{\cal{I}}}\) is called \(k\)-locally optimal if one cannot obtain a smaller dominating set by replacing a subset \(X \subseteq D\) of size at most \(k\) with a subset of size at most \(|X|-1\) from \({{\cal{I}}}\). Given a constant \({\varepsilon}> 0\), our algorithm computes a \(k\)-locally optimal dominating set for \(k=\frac{c}{{\varepsilon}^2}\), where \(c\) is a suitably large constant. The algorithm begins with an arbitrary dominating set \(D\) of \(G\) (for example, the dominating set computed in Section 3) and proceeds by making small exchanges of size at most \(k\). That is, as long as there is a subset \(X \subseteq D\) of size at most \(k\) and a subset \(X' \subseteq {{\cal{I}}}\) of size at most \(|X|-1\), such that \((D\setminus X) \cup X'\) is a dominating set of \(G\), we replace \(D\) with \((D\setminus X) \cup X'\). The algorithm stops when no further improvements exist and returns \(D\).

Since the size of \(D\) decreases by at least one after each iteration, the number of iterations in the algorithm is at most \(n+m\). Moreover, each iteration takes \(O((n+m)^k)\) time, because we need to check every subset of size at most \(k\). Therefore, the total running time of the algorithm is \(O((n+m)^{k+1}) = (n+m)^{O(1/{\varepsilon}^2)}\).

4.2 Approximation ratio↩︎

We now analyze the approximation ratio of our algorithm based on the framework of [27], [28]. Let \(D\) denote the locally optimal dominating set obtained by the algorithm, and let \(O\) denote an optimal dominating set of \(G\). We assume, w.l.o.g., that \(D \cap O = \emptyset\), i.e., there is no interval that belongs to both \(D\) and \(O\). (Common intervals are ignored since they belong to both solutions and do not affect the analysis.)

Section 4.2.1 is devoted to the proof of Lemma 5. Once we establish the locality condition, the analysis of the algorithm is the same as in [28]. For completeness, we include the proof specialized to our setting.

Since the graph \(H = (D \cup O,E_H)\) is planar, the following planar separator theorem can be used.

We apply Theorem 4 to the graph \(H = (D \cup O,E_H)\) in Lemma 5, setting \(n = |D| + |O|\) and \(r=\frac{k}{c_2}\), where \(c_2\) is the constant in Theorem 4. Hence, \(|V_i| \le k\), for every \(1 \le i \le \frac{n}{r}\).

Let \(D_i = V_i \cap D\) and \(O_i = V_i \cap O\). Thus, \(|D_i| \le |O_i| + |N(V_i) \cap S|\); otherwise, replacing \(D_i\) with \(O_i \cup (N(V_i) \cap S)\) results in a dominating set of size smaller than \(D\), which contradicts that \(D\) is locally optimal. Therefore, we have \[\begin{align} |D| & \le |S| + \sum_{i=1}^{n/r}|D_i| \; \le |S| + \sum_{i=1}^{n/r}|O_i| + \sum_{i=1}^{n/r} |N(V_i) \cap S|. \end{align}\] Since \(O_1,O_2,\dots,O_{\frac{n}{r}}\) are disjoint, we have \[\begin{align} |D| \le |O| + |S| + \sum_{i=1}^{n/r} |N(V_i) \cap S|. \end{align}\] Since \(\sum\limits_{i=1}^{n/r}|N(V_i) \cap S| \le \frac{c_3 n}{\sqrt{r}} = \frac{c_3(|D|+|O|)}{\sqrt{r}}\), \(|S| \le \frac{c_1n}{\sqrt{r}}= \frac{c_1(|D|+|O|)}{\sqrt{r}}\), and \(r=\frac{k}{c_2}\), we have \[\begin{align} |D| \le |O| + \frac{c_1(|D|+|O|)}{\sqrt{k}/\sqrt{c_2}} + \frac{c_3(|D|+|O|)}{\sqrt{k}/\sqrt{c_2}}. \end{align}\] By setting \(c_4 = (c_1+c_3)\sqrt{c_2}\), we have \[\begin{align} |D| \le |O| + \frac{c_4(|D|+|O|)}{\sqrt{k}}. \end{align}\] Thus, we have \[\begin{align} |D| \le \frac{1+c_4/\sqrt{k}}{1-c_4/\sqrt{k}} |O|. \end{align}\] By choosing \(k = \frac{c}{{\varepsilon}^2}\) for sufficiently large constant \(c \ge (c_4({\varepsilon}+2))^2\), we have \(|D| \le (1+{\varepsilon}) |O|\).

4.2.1 Establishing the Locality Condition↩︎

We construct a planar exchange graph \(H = (D \cup O,E_H)\) satisfying the locality condition of Lemma 5 as follows. Recall that, for each interval \(I \in {{\cal{I}}}\), \(s(I)\) and \(e(I)\) denote the starting and ending points (i.e., the left and right endpoints) of \(I\), respectively, and that \(C(I)\) denotes the set of intervals in \({{\cal{I}}}\) that intersect \(I\), i.e., \(C(I) = \{I' \in {{\cal{I}}}:s(I') < s(I) < e(I') < e(I) \text{ or } s(I) < s(I') < e(I) < e(I')\}\). We assume throughout that the endpoints of the intervals of \({{\cal{I}}}\) are distinct.

Let \(I\) be an interval of \({{\cal{I}}}\) and assume, w.l.o.g., that \(I\) is blue. We define the exchange edge contributed by \(I\) as follows.
Rule 1: If \(D \cap C(I) \neq \emptyset\) and \(O \cap C(I) \neq \emptyset\), then we select an interval \(u \in D \cap C(I)\) and an interval \(v \in O \cap C(I)\), such that \(u\) and \(v\) are consecutive (along \(I\)) among all intervals of \(D \cup O\) intersecting \(I\), and add \((u,v)\) to \(E_H\).
Rule 2: If \(D \cap C(I) = \emptyset\), then \(I \in D\) and there exists at least one interval \(v \in O\) dominating \(I\). We select the shortest interval \(v \in O\) that dominates \(I\) (if there is more than one such interval, we select one arbitrarily) and add \((I,v)\) to \(E_H\).
Rule 3: Similarly, if \(O \cap C(I) = \emptyset\), then \(I \in O\) and there exists at least one interval \(v \in D\) dominating \(I\). We select the shortest interval \(u \in D\) that dominates \(I\) (if there is more than one such interval, we select one arbitrarily) and add \((u,I)\) to \(E_H\).

Notice that the edges produced by Rule 1 connect intervals of the same color, while the edges produced by Rule 2 and Rule 3 connect intervals of different colors. Moreover, since \(D \cap O = \emptyset\), the two endpoints of the resulting exchange edge do not coincide as vertices. If the same edge is produced by several intervals, we keep only one copy.

The exchange graph \(H\) has a vertex set \(D \cup O\) and an edge set \(E_H\) containing the edges produced by the above rules over all intervals of \({{\cal{I}}}\). We now prove that \(H\) is planar. The proof is topological. We first consider the edges connecting intervals of the same color, i.e., the edges produced by Rule 1. Let \(H_R\) be the subgraph of \(H\) induced by the red intervals of \(D \cup O\), and let \(H_B\) be the subgraph of \(H\) induced by the blue intervals of \(D \cup O\).

Proof. Each edge in \(H_R\) is generated by a blue interval of \({{\cal{I}}}\) and connects a red interval from \(D\) and a red interval from \(O\). We draw the red intervals as non-crossing arcs below a baseline \(\ell\). This is possible because the red intervals do not cross each other: disjoint red intervals are drawn as disjoint arcs, and nested red intervals are drawn as nested arcs. We regard each red interval as a small vertex-region and draw the exchange edges as curves between these regions. The blue intervals are drawn similarly.

Let \((u,v)\) be an exchange edge of \(H_R\) contributed by a blue interval \(b \in {{\cal{I}}}\) according to Rule 1. We draw the edge \((u,v)\) as a sub-curve of \(b\) connecting the intersection points of \(b\) with \(u\) and \(v\). Since the blue intervals do not cross, this drawing has no crossing edges.

We now show that each vertex-region is safe, i.e., no exchange edge \((u,v)\) of \(H_R\) can intersect the vertex-region of each red interval \(r\). This is true since, for each edge \((u,v)\) that is contributed by a blue interval \(b\), using Rule 1, \(u\) and \(v\) are consecutive, and hence, \(r\) cannot intersect \(b\) between \(u\) and \(v\). Thus, the edges in the drawing do not cross any vertex-region of the red intervals.

Finally, consider two exchange edges incident to the same red interval \(r\). Each such edge is attached to \(r\) near the endpoint of the corresponding interval that is dominated by \(r\). These attachment points appear in a well-defined left-to-right order along \(r\). We draw the incident edges in this order around the vertex-region of \(r\). Thus, edges that share an endpoint of \(r\) meet only at \(r\) and do not cross. Therefore, \(H_R\) is planar. ◻

The following lemma is symmetric to Lemma 6, and its proof is similar.

Proof. By Lemma 6, \(H_R\) is planar, and by Lemma 7, \(H_B\) is planar. Moreover, the vertex sets of \(H_R\) and \(H_B\) are disjoint since one consists only of red intervals and the other consists only of blue intervals. Thus, the union of \(H_R\) and \(H_B\) is also planar. It remains to show that the edges produced by Rule 2 and Rule 3, connecting the red intervals of \(H_R\) and the blue intervals of \(H_B\), can be drawn without crossings.

Assume that the drawing of \(H_R\) is below the horizontal line \(\ell\) and the drawing of \(H_B\) is above the horizontal line \(\ell'\), which is one unit above \(\ell\). Let \(b\) be a blue interval and let \((b,r)\) be the edge contributed by \(b\) according to Rule 2. Hence, \(b \in D\) is drawn above \(\ell'\), and \(r\) is the shortest red interval in \(O\) that dominates \(b\) is drawn below \(\ell\); see Figure 13. Assume, w.l.o.g., that \(r\) contains the endpoint \(e(b)\) of \(b\). Let \(p(b)\) be the projection of \(e(b)\) on \(\ell\) and let \(ref(b)\) be the reflection of \(b\) below \(\ell\). We draw the edge \((b,r)\) as a curve consisting of a vertical segment connecting \(s(b)\) to \(e(b)\) and the portion of \(ref(b)\) between \(p(b)\) and the intersection point of \(ref(b)\) with \(r\).

Clearly, \((b,r)\) does not cross the vertex-regions of the blue intervals of \(H_B\) and does not cross the vertex-regions of the red intervals of \(H_B\) that contain \(r\). Since the blue intervals do not cross each other, \((b,r)\) does not cross the edges of \(H_R\), since these edges are drawn as portions of blue intervals. Moreover, since \(D \cap C(b) = \emptyset\), no red interval in \(D\) contains \(p(b)\), and since \(r\) is the shortest red interval in \(O\) that intersects \(b\), no red interval of \(O\) that is contained in \(r\) contains \(p(b)\). Thus, \((b,r)\) does not cross the vertex-regions of the red intervals of \(H_R\).

We draw the edges contributed by the red intervals similarly (see, for example, the edge \((r',b')\) and \((b'',r)\) in Figure  13). Hence, the edges produced by Rule 2 and Rule 3 can be drawn without crossings. Therefore, \(H\) is planar. ◻

5 Concluding Remarks↩︎

We studied the minimum dominating set problem on bipartite circle graphs. We proved that the problem remains NP-hard even in this restricted class by presenting a reduction from Planar Monotone 3-SAT. On the positive side, we developed a polynomial-time 2-approximation algorithm based on dynamic programming and showed that a local-search algorithm yields a polynomial-time approximation scheme.

Several interesting questions remain open. In particular, it would be interesting to determine whether the problem admits an exact polynomial-time algorithm for further restricted subclasses of bipartite circle graphs or whether faster approximation schemes can be obtained.

References↩︎