Maximum Bipartite Subgraph of Geometric Intersection Graphs

Abstract

We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set S of n geometric objects in the plane, we want to compute a maximum-size subset $S'\subseteq S$ such that the intersection graph of the objects in $S'$ is bipartite. We first show that the $\texttt {MBS}$ problem is $\texttt {NP}$-hard on geometric graphs for which the maximum independent set is $\texttt {NP}$-hard (hence, it is $\texttt {NP}$-hard even on unit squares and unit disks). On the algorithmic side, we first give a simple $\mathcal {O}(n)$-time algorithm that solves the $\texttt {MBS}$ problem on a set of n intervals. Then, we give an $\mathcal {O}(n^2)$-time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. Moreover, for the approximability of the problem, we first present a $\texttt {PTAS}$ for the problem on unit squares and unit disks. Then, we present efficient approximation algorithms with small-constant factors for the problem on unit squares, unit disks and unit-height rectangles. Finally, we study a closely related geometric problem, called Maximum Triangle-free Subgraph (${{\texttt {\textit{MTFS}}}}$), where the objective is the same as that of $\texttt {MBS}$ except the intersection graph induced by the set $S'$ needs to be triangle-free only (instead of being bipartite).

This work is supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC).

1 Introduction

In this paper, we study the following geometric problem. Given a set S of n geometric objects in the plane, we are interested in computing a maximum-size subset $S'\subseteq S$ such that the intersection graph induced by the objects in $S'$ is bipartite. We refer to this problem as the Maximum Bipartite Subgraph (${{\texttt {\textit{MBS}}}}$) problem. The $\texttt {MBS}$ problem is closely related to the Odd Cycle Transversal ($\texttt {OCT}$) problem: given a graph G, the objective of the $\texttt {OCT}$ problem is to compute a minimum-cardinality subset of $S\subseteq V(G)$ such that the intersection of S and the vertices of every odd cycle of the graph is non-empty. Notice that $\texttt {MBS}$ and $\texttt {OCT}$ are equivalent for the class of graphs on which $\texttt {OCT}$ is polynomial-time solvable: an exact solution S for $\texttt {OCT}$ gives $V(G)\setminus S$ as an exact solution for $\texttt {MBS}$ within the same time bound (see below for a summary of the main known results on the $\texttt {OCT}$ problem). However, on classes of graphs for which $\texttt {OCT}$ is $\texttt {NP}$-hard, an $\alpha$-approximation algorithm for $\texttt {OCT}$ might not provide any information on the approximability of $\texttt {MBS}$ on the same classes of graphs.

Another problem that is related to $\texttt {MBS}$ is the Feedback Vertex Set ($\texttt {FVS}$) problem. The objective of $\texttt {FVS}$ is the same as that of $\texttt {OCT}$ except the set S has a non-empty intersection with every cycle of the graph (not only the odd ones). The $\texttt {FVS}$ problem has been extensively studied in graph theory from both hardness [11, 29] and algorithmic [4, 9, 14, 17] points of view.

We also study a simpler variant of $\texttt {MBS}$, called the Maximum Triangle-free Subgraph (${{\texttt {\textit{MTFS}}}}$) problem. Let S be a set of n geometric objects in the plane. Then, the objective of the $\texttt {MTFS}$ problem is to compute a maximum-size subset $S'\subseteq S$ such that the intersection graph induced by the objects in $S'$ is triangle free (as opposed to being bipartite).

Related Work. The $\texttt {MBS}$ problem is NP-complete for planar graphs with maximum degree four [6]. For graphs with maximum degree three, Choi et al. [6] showed that for a given constant k there is a vertex set of size k or less whose removal leaves an induced bipartite subgraph if and only if there is an edge set of size k or less whose removal leaves a bipartite spanning subgraph. As edge deletion graph bipartization problem is NP-complete for cubic graphs [28], the $\texttt {MBS}$ problem is NP-complete for cubic graphs. Moreover, since the maximum edge deletion graph bipartization problem is solvable in $\mathcal {O}(n^3)$ time for planar graphs [1, 12] where n is the number of vertices of the input graph, this immediately implies that $\texttt {MBS}$ is $\mathcal {O}(n^3)$-time solvable for planar graphs with maximum degree three. For the vertex-weighted version of the $\texttt {MBS}$ problem, Baiou et al. [2] showed that the $\texttt {MBS}$ problem can be solved in $\mathcal {O}(n^{3/2}\log n)$ time for planar graphs with maximum degree three. Finally, Cornaz et al. [8] considered the maximum induced bipartite subgraph problem: given a graph with non-negative weights on the edges, the goal is to find a maximum-weight bipartite subgraph. An edge subset $F \subseteq E$ is called independent if the subgraph induced by the edges in F (incident vertices) is bipartite; otherwise, it is called dependent. They showed that the minimum dependent set problem with non-negative weights can be solved in polynomial time.

The $\texttt {OCT}$ problem is known to be NP-complete on planar graphs with degree at most 6 [6]. For planar graphs with degree at most 3, $\texttt {OCT}$ can be solved in $\mathcal {O}(n^3)$ time [6] (even the weighted version of the problem). There are several results known concerning the parameterized complexity of $\texttt {OCT}$ (i.e., given a graph G on n vertices and an integer k, is there a vertex set U in G of size at most k such that $G\setminus U$ is bipartite). Reed et al. [26] first gave an algorithm with running time $\mathcal {O}(4^k kmn)$. Lokshtanov et al. [19] improved this running time to $\mathcal {O}(3^k kmn)$. Lokshtanov et al. [20] provide an algorithm with running time $\mathcal {O}(2^{\mathcal {O}(k \log k)} n)$ for planar graphs. Moreover, assuming the exponential time hypothesis, the running time cannot be improved to $2^{\mathcal {O}(k)} n^{\mathcal {O}(1)}$.

The $\texttt {MBS}$ problem is also closely related to the Maximum Independent Set ($\texttt {MIS}$) problem. Observe that any feasible solution for MIS is also a feasible solution for $\texttt {MBS}$ and, moreover, a feasible solution $S\subseteq V(G)$ for the $\texttt {MBS}$ problem provides a feasible solution of size at least |S|/2 for the MIS problem. Hence, $\texttt {OPT}(\texttt {MIS})\le \texttt {OPT}(\texttt {MBS})\le 2\texttt {OPT}(\texttt {MIS})$. This implies that an $\alpha$-approximation algorithm for $\texttt {MIS}$ on a class of graphs is a $2\alpha$-approximation for $\texttt {MBS}$ on the same class. In particular, the $\texttt {PTAS}$es for $\texttt {MIS}$ on unit disks and unit squares [13] imply polynomial-time $(2+\epsilon )$-approximation algorithms for MBS on unit disks and unit squares. Moreover, we obtain a polynomial-time $\mathcal {O}(\log \log n)$-approximation [5] (or, $\mathcal {O}(\log \texttt {OPT})$-approximation [3]) algorithm for $\texttt {MBS}$ on rectangles.

Our Results. In this paper, we present the following results.

• On the hardness side, we show that the $\texttt {MBS}$ problem is NP-hard on the classes of geometric intersection graphs for which $\texttt {MIS}$ is NP-hard (Sect. 2); this in particular includes unit disks and unit squares. We also extend this result to a corresponding W[1]-hardness result.

• On the algorithmic side, we give a linear-time algorithm for $\texttt {MBS}$ on interval graphs, and an $\mathcal {O}(n^2)$-time algorithm that computes a near-optimal solution for $\texttt {MBS}$ on any circular-arc graph with n vertices (Sect. 3).

• On the approximation side, we obtain a $\texttt {PTAS}$ for the $\texttt {MBS}$ problem on unit disks and unit squares. For a set of n unit-height rectangles in the plane, we give an $\mathcal {O}(n\log n)$-time 2-approximation algorithm for the problem. Moreover, we design an $\mathcal {O}(n^2)$-time 4-approximation algorithm for the same problem on unit disks (Sect. 4).

• Finally, we show that the $\texttt {MTFS}$ problem is $\texttt {NP}$-hard on the intersection graph of axis-parallel rectangles in the plane (Sect. 5).

2 $\texttt {NP}$-Hardness

In this section, we show that the $\texttt {MBS}$ problem is NP-complete on the classes of geometric intersection graphs for which $\texttt {MIS}$ is NP-complete. The $\texttt {MIS}$ problem is known to be $\texttt {NP}$-complete on a wide range of geometric intersection graphs, even restricted to unit disks and unit squares [7], 1-string graphs [16], and B$_1$-VPG graphs [18]. Let $G=(V,E)$ be an intersection graph induced by a set S of n geometric objects in the plane. We construct a new graph $G'$ from the disjoint union of two copies of G by adding edges as follows. For each vertex in V, we add an edge from each vertex in one copy of G to the corresponding vertex in the other copy. For each edge $(u,v)\in E$, we add four edges $(u,v), (u',v'),(u,v'),$ and $(v,u')$ to $G'$, where $u'$ and $v'$ are the corresponding vertices of u and v, respectively in the other copy. Graph $G'$ is the intersection graph of 2n geometric objects S, where each object has occurred twice in the same position. Clearly, the number of vertices and edges in $G'$ are polynomial in the number of vertices of G; hence, the construction can be done in polynomial time.

Lemma 1

G has an independent set of size at least k if and only if $G'$ has a bipartite subgraph of size at least 2k.

Proof

Let U be an independent set of G with $|U|\ge k$. Let H be the subgraph of $G'$ induced by U along with all the corresponding vertices of U in the other copy. Then, H is a bipartite subgraph with size at least 2k. Conversely, if $G'$ has a bipartite subgraph of size at least 2k, then $G'$ must have an independent set of size at least k. By the construction of $G'$, if $G'$ has an independent set of size at least k, then G must have an independent set of size at least k.$\Box$

By Lemma 1, we have the following theorem.

Theorem 1

The MBS problem is NP-complete on the classes of geometric intersection graphs for which $\texttt {MIS}$ is NP-complete.

Remark. By the definition of parameterized reduction [10], one can verify that the above reduction is in fact a parameterized reduction and so we have the following result.

Corollary 1

The $\texttt {MBS}$ problem is W[1]-complete on the classes of geometric intersection graphs for which $\texttt {MIS}$ is W[1]-complete.

We note that Marx [22, 23] proved that $\texttt {MIS}$ is W[1]-complete on unit squares, unit disks, and even unit line segments. As such, by Corollary 1, the $\texttt {MBS}$ problem is W[1]-complete on all these geometric intersection graphs.

3 Algorithmic Results

In this section, we present our algorithms for the $\texttt {MBS}$ problem on interval graphs and circular-arc graphs. We start with interval graphs.

3.1 Interval Graphs

In this section, we consider the $\texttt {MBS}$ problem on a set S of n intervals and give a linear-time algorithm for the problem. Notice that for interval graphs, the $\texttt {MBS}$ problem is the same as $\texttt {FVS}$; to the best of our knowledge, the best-known algorithm for solving $\texttt {FVS}$ on interval graphs takes $\mathcal {O}(|V|+|E|))$ time [21]. Since interval graphs are a subclass of chordal graphs, the $\texttt {MBS}$ problem on interval graphs reduces to the problem of computing a maximum-size subset of intervals in S whose induced graph is triangle free. Consequently, a point can “stab” at most two intervals in any feasible solution for the $\texttt {MBS}$ problem on intervals. Algorithm 1 exploits this property to solve the problem exactly.

In the following, we assume that (i) the endpoints of intervals in S are 2n distinct points on the real line, and (ii) the intervals are sorted from left to right by the increasing order of their right endpoint; we denote them as $I_1,I_2,\dots ,I_n$. Moreover, the variable x (resp., y) denotes the x-coordinate of the rightmost point on the real line such that it is contained in two intervals (resp., one interval) of the current solution computed by the algorithm. For an interval I, we denote the left and right endpoints of I by $\texttt {left}(I)$ and $\texttt {right}(I)$, respectively.

Correctness. Let $M_i$, for all $1\le i\le n$, denote the set M at the end of iteration i of the for-loop. Consider the following invariant.

• Invariant I. For all $i=1,\dots ,n$, at the end of iteration i of the for-loop, the set $M_i$ is an optimal solution for the set of intervals $\{I_1,I_2,\dots ,I_i\}$.

We prove Invariant I by induction on |S|. If $|S|=1$, then $M=\{I_1\}$ by line 5 of the algorithm and we are done. Moreover, if $|S|=2$, then there are two cases depending on whether $\{I_1,I_2\}$ form a clique or an independent set. In either case, $M=\{I_1,I_2\}$ and we are done. Now, suppose that Invariant I is true for all $|S|=1,2,\dots ,n-1$. Let S be a set of n intervals and consider the set $S\setminus I_n$ (where $I_n$ is the interval with rightmost right endpoint in S). By induction hypothesis, let $M_{n-1}$ be the optimal solution for $S\setminus I_n$ computed by the algorithm and consider the values of x and y before returning $M_{n-1}$ in line 13. We must have that either (i) $\texttt {left}(I_n)>y$, (ii) $x<\texttt {left}(I_n)<y$, or (iii) $\texttt {left}(I_n)<x$. In cases (i) and (ii), the algorithm adds $I_n$ to $M_{n-1}$ resulting in an optimal solution. In case (iii), the algorithm returns $M_{n-1}$ without adding $I_n$ to the solution. Observe that this is optimal as no feasible solution can add $I_n$.

The algorithm clearly runs in time linear in n and so we have the following theorem.

Theorem 2

The $\texttt {MBS}$ problem on a set of n intervals can be solved in $\mathcal {O}(n)$ time, assuming that the intervals are already sorted on their right endpoint.

3.2 Circular-Arc Graphs

We now give a near-optimal solution for the $\texttt {MBS}$ problem on circular-arc graphs. For an optimization problem, a near-optimal solution is a feasible solution whose objective function value is within a specified range from the optimal objective function value. A circular-arc graph is the intersection graph of arcs on a circle. That is, every vertex is represented by an arc, and there is an edge between two vertices if and only if the corresponding arcs intersect. Observe that interval graphs are a proper subclass of circular-arc graphs. For the rest of this section, let $G=(V,E)$ be a circular-arc graph and assume that a geometric representation of G (i.e., a set of |V(G)| arcs on a circle $\mathcal{C}$) is given as part of the input. First, we prove the following lemmas.

Lemma 2

If G is triangle-free, then it can have at most one cycle.

Proof

Suppose for the sake of contradiction that G has more than one cycle. Let $A_1$ and $A_2$ be two cycles of G. Now, since G is a triangle-free circular-arc graph, the corresponding arcs of the vertices of any cycle in G together cover the circle $\mathcal {C}$. So, there must exist three distinct vertices $v\in A_1, u\in A_1$ and $w\in A_2$ such that v, u, w are pairwise adjacent. Which is a contradiction to the fact that G is triangle-free.$\Box$

Lemma 3

If B and T are optimal solutions for the $\texttt {MBS}$ and $\texttt {MTFS}$ problems on G, respectively, then $|T|-1\le |B|\le |T|$.

Proof

Since a bipartite subgraph contains no triangle, $|B|\le |T|$. Now, if G[T] (i.e., the subgraph of G induced by T) is odd-cycle free, then it induces a bipartite subgraph. Otherwise, G[T] can have at most one cycle by Lemma 2. If this cycle is odd, then by removing any single vertex form the cycle, we obtain a bipartite subgraph of G with size at least $|T|-1$.$\Box$

Since G[T] contains at most one cycle, following lemma trivially holds.

Lemma 4

If H is a maximum-size induced forest in G, then $|V(H)|\ge |T|-1$.

By the above lemmas, our goal now is to find a maximum acyclic subgraph H of G. Notice that there must be a clique K ($|K|\ge 1$) in G that is not in H. Now, for each arc u in the circular-arc representation of G, let l(u) and r(u) denote the two endpoints of u in the clockwise order of the endpoints u. Then, we consider two vertex sets $S_{u}^1= \{w :w \in V, l(u) \notin [l(w),r(w)] \}$ and $S_{u}^2= \{z :z \in V, r(u) \notin [l(z),r(z)] \}$. Both $S_{u}^1$ and $S_{u}^2$ are interval graphs. Since there are n vertices in G, we compute 2n interval graphs in total. Then, for each of these interval graphs, we apply Algorithm 1 to compute an optimal solution for $\texttt {MBS}$, and will return the one with maximum size as the final solution. Since Algorithm 1 runs in $\mathcal {O}(n)$ time, the total time to find H is $\mathcal {O}(n^2)$; so we have the following theorem.

Theorem 3

Let OPT be a maximum-size induced bipartite subgraph of a circular-arc graph G with n vertices. Then, there is an algorithm that computes an induced bipartite subgraph H of G such that $|V(H)|\ge |OPT|-1$. The algorithm runs in $\mathcal {O}(n^2)$ time.

4 Approximation Algorithms

Recall that since $\texttt {MIS}$ is $\texttt {NP}$-complete on unit disks and unit squares, the $\texttt {MBS}$ problem is $\texttt {NP}$-complete on these graphs by Theorem 1. In this section, we first give $\texttt {PTAS}$es for $\texttt {MBS}$ on both unit squares and unit disks, and will then consider the problem on unit-height rectangles.

4.1 Unit Disks and Unit Squares

We first show the $\texttt {PTAS}$ for unit disks, and will then discuss it for unit squares as well as the weighted $\texttt {MBS}$ problem.

Let S be a set of n unit disks in the plane, and let $k>1$ be a fixed integer. A $\texttt {PTAS}$ running in $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(1/\epsilon ^2)})$ time, for any $\epsilon >0$, is straightforward using the shifting technique of Hochbaum and Maass [13] and the following packing argument: for an instance of the $\texttt {MBS}$ problem, where the unit disks lie inside a $k\times k$ square, an optimal solution cannot have more than $k^2$ unit disks. Hence, we can compute an exact solution for such an instance of the problem in $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(k^2)})$ time. Consequently, by setting $k=1/\epsilon$, we obtain a $\texttt {PTAS}$ running in time $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(1/\epsilon ^2)})$.

To improve the running time to $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(1/\epsilon )})$, we rely on the shifting technique again, but instead of applying the plane partitioning twice, we only partition the plane into horizontal slabs and solve the $\texttt {MBS}$ problem for each of them exactly. This gives us the desired running time for our $\texttt {PTAS}$. We next describe the details of how to solve $\texttt {MBS}$ exactly for a slab.

Algorithm for a Slab. Let H be a horizontal slab of height k and let $D\subseteq S$ be the set of disks that lie entirely inside H. The idea is to build a vertex-weighted directed acyclic graph G such that finding a maximum-weight path from the source vertex to the target vertex corresponds to an exact solution for the $\texttt {MBS}$ problem [24]. To this end, let a and b ($a<b$) be two integers such that every disk in D lies inside the rectangle R bounded by H and the vertical lines $x=a$ and $x=b$. Partition R vertically into unit-width boxes $B_i$, where the left side of $B_i$ has the x-coordinate $a+i$, for all integers $0\le i<b-a$; let $D_i\subseteq D$ denote the set of disks whose centers lie inside $B_i$. Since $B_i$ has height k and width 1, we can compute all feasible (not necessarily exact) solutions for the $\texttt {MBS}$ problem on $D_i$ in $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(k)})$ time; let $\mathcal{M}_i$ be the set of all such feasible solutions. We now build a directed vertex-weighted acyclic graph G as follows. The vertex set of V(G) is $V\cup \{s,t\}$, where V has one vertex for each solution in $\mathcal{M}_i$, for all i. Moreover, the weight of each vertex is the number of disks in the corresponding bipartite graph. For every pair i, j, where $1\le i<j<n$, consider two solutions $M\in \mathcal{M}_i$ and $M'\in \mathcal{M}_j$. Then, there exists an edge from the vertex of M to that of $M'$ in G if the intersection graph induced by the disks in $M\cup M'$ is bipartite. Finally, for all i and for all $M\in \mathcal{M}_i$: there exists an edge from s to M, and there exists an edge from M to t. The weights of vertices s and t are zero.

Lemma 5

The $\texttt {MBS}$ problem has a feasible solution of size k on G if and only if there exists a directed path from s to t with the total weight k.

Proof

For a given directed st-path with total weight k, let X be the union of all the disks corresponding to the interval vertices of this path. Then, the intersection graph of X is bipartite because the disks in $X\cap \mathcal{M}_i$ are disjoint from the disks in $S\cap \mathcal{M}_j$ when $j>i+1$. Moreover, when $j=i+1$, the disks in $X\cap (\mathcal{M}_i\cup \mathcal{M}_j)$ must form an induced bipartite graph by the definition of an edge in G. Since the total weight of the vertices on the path is k, we have $|X|=k$. On the other hand, let Y be a feasible solution of size k for the $\texttt {MBS}$ problem on G. Then, the intersection graph of disks in $Y\cap D_i$ is bipartite, for all i. Hence, selecting the vertices corresponding to $Y\cap D_i$ for all i gives us a path with total weight k from s to t.$\Box$

By Lemma 5, the $\texttt {MBS}$ problem for H reduces to the problem of finding the maximum-weighted path from s to t on G. The number of vertices of G that correspond to feasible solutions for the $\texttt {MBS}$ problem on disks in $S\,\cap \, D_i$ is bounded by $\mathcal {O}(n^{\mathcal {O}(k)})$, which is the bound on the number of vertices of G that correspond to these feasible solutions. Hence, we can compute the edge set of G in $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(k)})$ time (we can check whether a subset of disks form a bipartite graph in $\mathcal {O}(n^{\mathcal {O}(1)})$ time). Since G is directed and acyclic, the maximum-weighted st-path problem can be solved in linear time. Therefore, by setting $k=1/\epsilon$, we have the following theorem.

Theorem 4

There exists a $\texttt {PTAS}$ for $\texttt {MBS}$ on unit disks that runs in $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(1/\epsilon )})$ time, for any $\epsilon >0$.

${{\texttt {\textit{PTAS}}}}$ on Unit Squares. One can verify that the above algorithm can be applied to obtain a $\texttt {PTAS}$ for $\texttt {MBS}$ on a set of n unit squares, as well. Moreover, the algorithm extends to the weighted $\texttt {MBS}$ problem on unit disks and unit squares. The only modification is, instead of assigning the number of disks (resp., squares) in a solution as the weight of the corresponding vertex, we assign the total weight of the disks (resp., squares) in the solution as the vertex weight.

Theorem 5

There exists a $\texttt {PTAS}$ for the $\texttt {MBS}$ problem on unit squares running in $\mathcal {O}(n^{\mathcal {O}(1)}\cdot n^{\mathcal {O}(1/\epsilon )})$ time, for any $\epsilon >0$. Moreover, the weighted $\texttt {MBS}$ problem also admits a $\texttt {PTAS}$ running within the same time bound on unit disks and unit squares.

A 4-Approximation on Unit Disks. Recall from Sect. 1 that $\texttt {OPT}(\texttt {MIS})\le \texttt {OPT}(\texttt {MBS})\le 2\texttt {OPT}(\texttt {MIS})$. Nandy et al. [25] designed a factor-2 approximation algorithm for the $\texttt {MIS}$ problem on unit disks, which runs in $\mathcal {O}(n^2)$ time. Consequently, we obtain an $\mathcal {O}(n^2)$-time 4-approximation algorithm for the $\texttt {MBS}$ problem on unit disks.

4.2 Unit-Height Rectangles

Here, we give an $\mathcal {O}(n\log n)$-time 2-approximation algorithm for $\texttt {MBS}$ on a set of n unit-height rectangles. To this end, suppose that the bottom side of the bottommost rectangle has y-coordinate a and the top side of the topmost rectangle has y-coordinate b. Consider the set of horizontal lines $y:=a+i+\epsilon$ for all $i=0,\dots ,b$, where $\epsilon >0$ is a small constant; we may assume w.l.o.g. that each rectangle intersects exactly one line. Ordering the lines from bottom to top, let $S_i$ be the set of rectangles that intersect the horizontal line i. We now run BipartiteInterval(S), once for when $S=S_1\cup S_3\cup S_5\dots$ and once for when $S=S_2\cup S_4\cup S_6\dots$, and will then return the largest of these two solutions. We perform an initial sorting that takes $\mathcal {O}(n\log n)$ time, and BipartiteInterval(S) runs in $\mathcal {O}(n)$ time. This gives us the following theorem.

Theorem 6

There exists an $\mathcal {O}(n\log n)$-time 2-approximation algorithm for the $\texttt {MBS}$ problem on a set of n unit-height rectangles in the plane.

5 NP-Hardness of MTFS

Here, we show that MTFS problem is NP-hard when geometric objects are axis-parallel rectangles. We give a reduction from the independent set problem on 3-regular planar graphs, which is known to be NP-complete [11].

Rim et al. [27] proved that $\texttt {MIS}$ is NP-hard for planar rectangle intersection graphs with degree at most 3. They also gave a reduction from the independent set problem on 3-regular planar graphs. Given a 3-regular planar graph $G=(V,E)$, they construct an instance $H=(V', E')$ of the MIS problem on rectangle intersection graphs. First we outline their construction of H from G. For any cubic planar graph G, it is always possible to get a rectilinear planar embedding of G such that each vertex $v \in V$ is drawn as a point $p_v$, and each edge $e=(u,v)\in E$ is drawn as a rectilinear path, connecting the points $p_u$ and $p_v$, having at most four bends, and thus consisting of at most five straight line segments. They [27] construct a family of rectangles B in the following way. For each point $p_{v_i}$ where $v_i \in V$, a rectangle $b_i$ is placed surrounding the point $p_{v_i}$. In each rectilinear path connecting $p_{v_i}$ and $p_{v_j}$, they place six rectangles $b^1_{ij}, b^2_{ij}, \dots ,b^6_{ij}$ such that (i) $b_i$ intersects $b^1_{ij}$, (ii) $b_j$ intersects $b^6_{ij}$, (iii) $b^k_{ij}$ intersects $b^{k+1}_{ij}$ for $k= 1,2, \dots ,5$ (iv) $b^1_{ij}, b^2_{ij}, \dots ,b^6_{ij}$ do not intersect any other rectangles in B. For an illustration see Fig. 1.

Fig. 1.

(a) A cubic planar graph G. (b) A rectilinear embedding of G. (c) Family of rectangle B.

Clearly, $H(V', E')$ is an axis-parallel rectangle intersection graph with degree at most 3 where $|V'|=|V|+6|E|$ and $|E'|= 7|E|$. In their reduction, the following lemma holds.

Lemma 6

[27] $G=(V,E)$ has an independent set of size $\ge m$ if and only if H has an independent set of size $m+3|E|$.

Given H, we construct an instance $G_H$ of MTFS problem in axis-parallel rectangles intersection graphs. For the sake of understanding, let all rectangles corresponding to vertices in H, i.e., all rectangles in B, be colored black. To get $G_H$, we insert a family R of red rectangles in the following way. For each pair of adjacent rectangles b and $b'$ in B, we place a red rectangle $R_{b,b'}$ such that (i) $R_{b,b'}$ intersects both b and $b'$, (ii) $R_{b,b'}$ does not intersect any other rectangles in $B \cup R$. As per construction of H, it is always possible to place such a rectangle for each pair of adjacent rectangles in B. See Fig. 2 for an illustration of this transformation. This completes the construction of our instance of the MTFS problem on axis-parallel rectangles intersection graphs. Since R contains 7|E| rectangles, the above transformation can be done in polynomial time. Now $G_H$ is an axis-parallel rectangle intersection graph with underlying geometric objects $B \cup R$. Clearly the number of vertices in $G_H$ is $(|V|+13|E|)$. We now prove the following lemma whose proof is given in the full version of the paper [15] due to space constraints.

Fig. 2.

Construction of an instance of MTFS problem from B. (Color figure online)

Lemma 7

H has an independent set of size $\ge k$ if and only if $G_H$ has a triangle-free subgraph on $\ge k+7|E|$ vertices.

By Lemmas 6 and 7, we have the following.

Lemma 8

$G=(V,E)$ has an independent set of size $\ge m$ if and only if $G_H$ has a triangle-free subgraph on $m+10|E|$ vertices.

We can now conclude the following theorem.

Theorem 7

The MTFS problem is NP-complete on axis-parallel rectangle intersection graphs.

6 Conclusion

In this paper, we studied the problem of computing a maximum-size bipartite subgraph on geometric intersection graphs. We showed that the problem is NP-hard on the geometric graphs for which maximum independent set is NP-hard. On the positive side, we gave polynomial-time algorithms for solving the problem on interval graphs and circular-arc graphs. We furthermore obtained several approximation algorithms for the problem on unit squares, unit disks, and unit-height rectangles. Finally, we showed the $\texttt {NP}$-hardness of a simpler problem in which the goal is to compute a maximum-size induced triangle-free subgraph. We conclude by the following open questions:

• Does $\texttt {MBS}$ admit a $\texttt {PTAS}$ on unit-height rectangles, or is it $\texttt {APX}$-hard?

• Is there a polynomial-time algorithm for $\texttt {MBS}$ on a set of n unit disks intersecting a common horizontal line?

• Can we improve the 4-approximation algorithm for unit disks with the same time bound $\mathcal{O}(n^2)$ (or, even better)?