# Bipartizing (Pseudo-)Disk Graphs:
Approximation with a Ratio Better than 3

Daniel Lokshtanov111University of California, Santa Barbara, USA. Email:
<EMAIL_ADDRESS>Fahad Panolan222University of Leeds, UK. Email:
<EMAIL_ADDRESS>Saket Saurabh333Institute of Mathematical Sciences,
Chennai, India. Email<EMAIL_ADDRESS>Jie Xue444New York University
Shanghai, China. Email<EMAIL_ADDRESS>Meirav Zehavi555Ben-Gurion University,
Israel. Email<EMAIL_ADDRESS>
###### Abstract

In a disk graph, every vertex corresponds to a disk in $\mathbb{R}^{2}$ and
two vertices are connected by an edge whenever the two corresponding disks
intersect. Disk graphs form an important class of geometric intersection
graphs, which generalizes both planar graphs and unit-disk graphs. We study a
fundamental optimization problem in algorithmic graph theory, Bipartization
(also known as Odd Cycle Transversal), on the class of disk graphs. The goal
of Bipartization is to delete a minimum number of vertices from the input
graph such that the resulting graph is bipartite. A folklore (polynomial-time)
$3$-approximation algorithm for Bipartization on disk graphs follows from the
classical framework of Goemans and Williamson [Combinatorica’98] for cycle-
hitting problems. For over two decades, this result has remained the best
known approximation for the problem (in fact, even for Bipartization on unit-
disk graphs). In this paper, we achieve the first improvement upon this
result, by giving a $(3-\alpha)$-approximation algorithm for Bipartization on
disk graphs, for some constant $\alpha>0$. Our algorithm directly generalizes
to the broader class of pseudo-disk graphs. Furthermore, our algorithm is
robust in the sense that it does not require a geometric realization of the
input graph to be given.

##  1 Introduction

Disk graphs refer to intersection graphs of disks in the plane
$\mathbb{R}^{2}$. Formally, in a disk graph, every vertex corresponds to a
disk in $\mathbb{R}^{2}$ and two vertices are connected by an edge whenever
the two corresponding disks intersect. As a rather general class of geometric
intersection graphs, disk graphs simultaneously generalize two important graph
classes, unit-disk graphs and planar graphs, both of which have been
extensively studied over decades. Many central problems in algorithmic graph
theory have been considered on disk graphs, including Vertex Cover [8, 29,
42], Independent Set [8], Maximum Clique [5], Feedback Vertex Set [27, 29],
Dominating Set [13], etc.

In this paper, we investigate a fundamental optimization problem on the class
of disk graphs, called Bipartization. In this problem, the input is a graph
$G$ and the goal is to delete a smallest number of vertices from $G$ such that
the resulting graph is bipartite. There has been a long line of work studying
Bipartization (e.g., see [10, 20, 21, 35, 37, 38] and citations therein).
Observe that the edge counterpart of the Bipartization problem, Edge
Bipartization, where we need to find fewest edges whose deletion results in a
bipartite graph, is equivalent to the classical Maximum Cut problem (which has
been studied for over five decades [14, 40]). It is known that Edge
Bipartization (and Maximum Cut) reduces to Bipartization [43], and both
problems find applications in computational biology [43, 39], VLSI chip design
[18], genome sequence assembly [33], and more. Bipartization is of particular
interest also due to the following observation: a graph is bipartite if and
only if it does not contain any odd cycle. As such, it can be formulated as
hitting all odd cycles in the graph (using fewest vertices). For this reason,
the Bipartization problem is also known as Odd Cycle Transversal, and belongs
to the family of cycle-hitting problems, one of the most well-studied topics
in algorithmic graph theory. Besides Bipartization, other important cycle-
hitting problems that have been studied on disk graphs include Feedback Vertex
Set, Triangle Hitting, Short Cycle Hitting, etc.

There is no surprise that Bipartization is NP-complete. In fact, it is NP-
complete even on graphs of maximum degree $3$ and planar graphs of maximum
degree $4$ [6]. As such, the study of the problem is mainly in the context of
approximation algorithms and parameterized algorithms. On the parameterized
front, it was known that Bipartization can be solved in $2^{O(k)}\cdot
n^{O(1)}$ time where $k$ is the solution size [21, 26, 36]. On planar graphs
and unit-disk graphs, there exist improved algorithms with running time
$k^{O(\sqrt{k})}\cdot n^{O(1)}$ [2, 3, 30, 32], which are almost tight
assuming the Exponential-Time Hypothesis (ETH). On disk graphs, it was not
known whether Bipartization admits a subexponential-time parameterized
algorithm, until very recently Lokshtanov et al. gave a $k^{O(k^{27/28})}\cdot
n^{O(1)}$-time algorithm [27].

From the perspective of approximation algorithms (which is the focus of this
paper), Bipartization is one of the trickiest problems in the sense that no
polynomial-time approximation scheme (PTAS) was known on any (nontrivial)
graph classes, but at the same time no inapproximability results was known
except for general graphs. On general graphs, Bipartization cannot admit any
(polynomial-time) constant-approximation algorithm assuming the Unique Games
Conjecture [4], and the best known approximation ratio is $O(\sqrt{\log{\sf
opt}})$ due to Kratsch and Wahlström [25], improving the earlier bounds of
$O(\log n)$ [9] and $O(\sqrt{\log n})$ [1]. It has been a long-standing open
question whether Bipartization admits a PTAS on planar graphs or unit-disk
graphs. On planar graphs, the currently best approximation for Bipartization
is still the $\frac{9}{4}$-approximation algorithm given in the seminal work
of Goemans and Williamson [15] more than two decades ago. This result
immediately gives a $3$-approximation algorithm for Bipartization on disk
graphs (and in particular, unit-disk graphs) by the well-known fact that
triangle-free disk graphs are planar [23].

######  Theorem 1.1 (folklore).

There exists a polynomial-time $3$-approximation algorithm for Bipartization
on the class of disk graphs.

###### Proof.

Let $G$ be the input disk graph. We repeat the following step until $G$
contains no triangles: find a triangle in $G$, add its three vertices to the
solution, and remove them from $G$. Denote by $S$ the set of vertices added to
the solution and by $G^{\prime}=G-S$ the resulting triangle-free graph, which
is planar [23]. Now apply the algorithm of Goemans and Williamson [15] on
$G^{\prime}$ to obtain a $\frac{9}{4}$-approximation solution $S^{\prime}$.
Note that $S\cup S^{\prime}$ is a $3$-approximation solution (for $G$).
Indeed, any solution of Bipartization must hit all triangles in $G$ and thus
contains at least $|S|/3$ vertices in $S$. Also, it contains at least
$|S^{\prime}|/\frac{9}{4}$ vertices in $V(G^{\prime})$. So its size is at
least $|S|/3+|S^{\prime}|/\frac{9}{4}\geq|S\cup S^{\prime}|/3$. ∎

For over two decades, this has remained the best approximation algorithm for
Bipartization on disk graphs (in fact, even on unit-disk graphs). Thus, there
is a natural question to be asked: can we achieve an approximation ratio
better than $3$ for the problem? Note that one cannot achieve this by
improving the approximation ratio $\frac{9}{4}$ for Bipartization on planar
graphs. Indeed, even if we had a PTAS on planar graphs, the above argument
still only gives us a $3$-approximation algorithm on disk graphs. Therefore,
the number $3$ here is truly a bottleneck of the approximation ratio of the
problem. In this paper, we break this bottleneck and answer the above question
affirmatively by giving the first algorithm for Bipartization on disk graphs
with an approximation ratio better than 3. Specifically, our main result is
the following.

######  Theorem 1.2.

There exists a polynomial-time $(3-\alpha)$-approximation algorithm for
Bipartization on the class of disk graphs, for some constant $\alpha>0$.

We remark that Theorem 1.2 should be viewed as a proof of concept, rather than
the quantitative improvement. Our algorithm in Theorem 1.2 is robust in the
sense that it does not require the geometric realization of the input disk
graph to be given. Furthermore, our algorithm directly generalizes to the
broader class of pseudo-disk graphs, which are the intersection graphs of
topological disks in which the boundaries of every two of them intersect at
most twice. (Note that the 3-approximation algorithm in Theorem 1.1 also works
for pseudo-disk graphs as triangle-free pseudo-disk graphs are planar [23].)
Again, this generalized algorithm is robust.

######  Theorem 1.3.

There exists a polynomial-time $(3-\alpha)$-approximation algorithm for
Bipartization on the class of pseudo-disk graphs, for some constant
$\alpha>0$.

Finally, we observe that our technique not only works for the Bipartization
problem. In fact, it can be applied to a large category of vertex-deletion
problems on (pseudo-)disk graphs, resulting in $(3-\alpha)$-approximation
algorithms. Although at this point it only yields interesting results for
Bipartization (mainly because most well-studied problems in the category
already have algorithms on disk graphs with approximation ratio better than
3), this demonstrates that our technique could possibly have further
applications in the future. We shall briefly discuss this part in Section 4.

##### Other related work.

NP-complete optimization problems on disk graphs and other geometric
intersection graphs have received considerable attention over years. Here we
only summarize some recent work on this topic. The work of de Berg et al. [7]
gave a framework for designing ETH-tight exact algorithms on (unit-)disk
graphs or more generally (unit-)ball graphs, which works for a variety of
classical optimization problems. Bonamy et al. [5] presented the first EPTAS
and subexponential-time algorithm for Maximum Clique on disk graphs. Fomin et
al. [11] designed almost ETH-tight parameterized algorithms for various cycle-
packing and cycle-hitting problems on unit-disk graphs; in a follow-up paper
[12], the same authors improved some of their algorithms to be ETH-tight.
Recently, Lokshtanov et al. [27, 29] proposed frameworks for subexponential
parameterized algorithms and EPTASes for various vertex-deletion problems on
disk graphs (the framework for EPTASes does not work for Bipartization, while
the one for subexponential parameterized algorithms works). A very recent work
by the same authors [28] gave a 1.9999-approximation for Vertex Cover on
string graphs (i.e., intersection graphs of arbitrary connected geometric
objects in the plane), which has the same flavor as this paper.

Besides the aforementioned algorithmic research on Bipartization, the problem
was also studied in the context of kernelization complexity. The seminal work
by Kratsch and Wahlström [24] showed that Bipartization admits a randomized
polynomial kernel with respect to $k$. Later, for planar graphs, it was shown
to admit a deterministic polynomial kernel by Jansen et al. [17]. Moreover,
the kernelization complexity of Bipartization was studied also with respect to
some structural parameterizations [16].

On a related note, we remark that structural properties of odd cycles in a
graph has also received significant attention from various combinatorial
points of view. While the survey of these results is beyond the scope of this
paper, as an illustrative example, let us mention the study of Erdős–Pósa
properties for odd cycles (see e.g., [10, 19, 34, 41]).

##  2 Preliminaries

Let $G$ be a graph. We use $V(G)$ and $E(G)$ to denote the vertex set and edge
set of $G$, respectively. For a subset $V\subseteq V(G)$, denote by $G[V]$ the
subgraph of $G$ induced by $V$, and by $G-V$ the subgraph of $G$ induced by
$V(G)\backslash V$. For a vertex $v$, we use $N_{G}(v)$ to denote the set
$\\{x\in V(G)\setminus\\{v\\}~{}\colon~{}(x,v)\in E(G)\\}$. For a vertex
subset $S$, we use $N_{G}(S)$ and $N_{G}[S]$ to denote the sets $\bigcup_{z\in
S}N_{G}(z)\setminus S$ and $S\cup N_{G}(S)$, respectively. For a vertex $v$ in
$G$, we use $d_{G}(v)$ to denote the degree of $v$ (i.e., $|N_{G}(v)|$) in
$G$. A vertex subset $I\subseteq V(G)$ is a distance-$d$ independent set in
$G$, if for any two distinct vertices $x$ and $y$ in $I$, the distance between
$x$ and $y$ in $G$ is strictly more than $d$. Here, the distance between two
vertices is the number of edges in a shortest path between those vertices. Let
$\mathcal{S}$ be a collection of subsets of $V(G)$. A packing of $\mathcal{S}$
is a sub-collection $\mathcal{S}^{\prime}$ such that $S\cap
S^{\prime}=\emptyset$ for all $S,S^{\prime}\in\mathcal{S}^{\prime}$ with
$S\neq S^{\prime}$. We say a packing
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ is maximal if any
$\mathcal{S}^{\prime\prime}\subseteq\mathcal{S}$ satisfying
$\mathcal{S}^{\prime}\subsetneq\mathcal{S}^{\prime\prime}$ is not a packing of
$\mathcal{S}$, and is maximum if any subset
$\mathcal{S}^{\prime\prime}\subseteq\mathcal{S}$ satisfying
$|\mathcal{S}^{\prime}|<|\mathcal{S}^{\prime\prime}|$ is not a packing of
$\mathcal{S}$. Any maximum packing of $\mathcal{S}$ has the same size.

An odd cycle transversal (or OCT for short) of $G$ is a subset $S\subseteq
V(G)$ such that $G-S$ is a bipartite graph. A triangle in $G$ refers to a set
$T=\\{u,v,w\\}$ of three vertices of $G$ such that $(u,v),(v,w),(w,u)\in
E(G)$. We use $\Delta(G)$ to denote the family of all triangles in $G$. For a
set $\mathcal{T}$ of triangles in $G$, we denote by $V(\mathcal{T})$ the set
of vertices of all triangles in $\mathcal{T}$, i.e.,
$V(\mathcal{T})=\bigcup_{T\in\mathcal{T}}T$. The notation
$\mathsf{tri}(\mathcal{T})$ denotes the size of a maximum packing of
$\mathcal{T}$.

##  3 Our algorithm

In this section, we present our approximation algorithm for Bipartization on
disk graphs. Our algorithm first takes a simple preprocessing step, which
reduces the general problem to the problem on $K_{4}$-free disk graphs (i.e.,
disk graphs without cliques of size 4). Then in the main part of our
algorithm, we solve Bipartization on $K_{4}$-free disk graphs. For a cleaner
exposition, we shall first give a randomized version of our algorithm, as it
is more intuitive and yields a better approximation ratio. We then show how to
derandomize it in Appendix A.

###  3.1 Preprocessing: reducing to the $K_{4}$-free case

For a graph $G$, let $K_{4}(G)$ be the set of all $K_{4}$’s in $G$. The
following lemma allows us to reduce the problem to Bipartization on
$K_{4}$-free disk graphs.

######  Lemma 3.1.

Let $G$ be a graph and ${\cal C}$ be a packing of $K_{4}(G)$. Let $S$ be a
$\rho$-approximation solution for Bipartization on $G-V({\cal C})$. Then,
$S\cup V({\cal C})$ is a $\max\\{2,\rho\\}$-approximation solution for
Bipartization on $G$.

###### Proof.

First, it is clear that $S\cup V({\cal C})$ is an OCT of $G$, since $G-S\cup
V({\cal C})=(G-V({\cal C}))-S$ contains no odd cycles. Let $S^{*}$ be an
optimal OCT of $G$. For every $K_{4}$ in ${\cal C}$, $S^{*}$ must contain at
least $2$ vertices in the $K_{4}$ (for otherwise $G-S^{*}$ contains a
triangle). Since the $K_{4}$’s in ${\cal C}$ are disjoint, we have $|S^{*}\cap
V(\mathcal{C})|\geq 2|\mathcal{C}|=|V(\mathcal{C})|/2$. Furthermore,
$S^{*}\cap(V(G)\backslash V(\mathcal{C}))$ is an OCT of $G-V(\mathcal{C})$,
which implies $|S^{*}\cap(V(G)\backslash V(\mathcal{C}))|\geq|S|/\rho$.
Therefore,

$|S^{*}|=|S^{*}\cap V(\mathcal{C})|+|S^{*}\cap(V(G)\backslash
V(\mathcal{C}))|\geq\frac{|V(\mathcal{C})|}{2}+\frac{|S|}{\rho}\geq\frac{|S|+|V(\mathcal{C})|}{\max\\{2,\rho\\}}.$

As $|S\cup V(\mathcal{C})|=|S|+|V(\mathcal{C})|$, we have $|S\cup
V(\mathcal{C})|\leq\max\\{2,\rho\\}\cdot|S^{*}|$. ∎

One reason for why this reduction helps us is the degeneracy of a $K_{4}$-free
disk graph. Recall that a graph $G$ is $c$-degenerate if we can sort its
vertices as $v_{1},\dots,v_{n}$ such that each $v_{i}$ is neighboring to at
most $c$ vertices in $\\{v_{1},\dots,v_{i-1}\\}$. A $c$-degenerate graph of
$n$ vertices has at most $cn$ edges and thus has average degree at most $2c$.
We prove that every $K_{4}$-free disk graph is $11$-degenerate. To prove this
we use the following known result.

######  Lemma 3.2 ([31]).

Let $D$ be a disk of radius $r$. Let ${\cal S}$ be a set of pairwise non-
overlapping disks of radius $r$ such that every disk in ${\cal S}$ intersects
with $D$. Then, $|{\cal S}|\leq 5$.

######  Lemma 3.3.

Every $K_{4}$-free disk graph is $11$-degenerate.

###### Proof.

To prove the lemma, it is enough to prove that for any $K_{4}$-free disk
graph, there is a vertex of degree at most $11$. Let $G$ be a $K_{4}$-free
disk graph with a realization $\mathcal{D}$, and let $D_{v}\in\mathcal{D}$ be
the disk representing the vertex $v\in V(G)$. Let $u$ be a vertex in $G$ such
that disk $D_{u}$ has the smallest radius among the disks in $\mathcal{D}$. We
will prove that $d_{G}(u)\leq 11$. Let $r$ be the radius of $D_{u}$. Notice
that for each $v\in N_{G}(u)$, the radius of $D_{v}$ is at least $r$. Now we
construct a graph $H$ with vertex set $N_{G}[u]$ such that $H$ is a unit disk
graph, $H$ is a subgraph of $G$ (and hence $K_{4}$-free), and
$d_{G}(u)=d_{H}(u)$. The construction of $H$ is as follows. For each $v\in
N_{G}(u)$, construct a disk $D^{\prime}_{v}$ of radius $r$ which is fully
contained in the disk $D_{v}$ and intersects $D_{u}$. The graph $H$ is the
geometric intersection graph of ${\cal
D^{\prime}}=\\{D_{u}\\}\cup\\{D^{\prime}_{v}~{}\colon v\in N_{G}(u)\\}$. It is
easy to see that $H$ is a unit disk graph, $H$ is a subgraph of $G$ and
$d_{G}(u)=d_{H}(u)$. For each $v\in V(H)\setminus\\{u\\}$, let $L_{v}$ be the
line segment between the centers of $D_{u}$ and $D^{\prime}_{v}$. Let
$\\{v_{1},\ldots v_{t}\\}=N_{G}(u)$ such that the line segments
$L_{v_{1}},L_{v_{2}},\ldots,L_{v_{t}}$ are in the clockwise order. We claim
that $t\leq 11$. For the sake of contradiction assume that $t\geq 12$. Suppose
there exists two distinct $i,j\in\\{1,3,5,7,9,11\\}$ such that
$D^{\prime}_{v_{i}}$ intersects with $D^{\prime}_{v_{j}}$. This implies that
$D^{\prime}_{v_{i+1}}$ or $D^{\prime}_{v_{j+1}}$ intersects both
$D^{\prime}_{v_{i}}$ and $D^{\prime}_{v_{j}}$. Let $w\in\\{v_{i+1},v_{j+1}\\}$
be the vertex such that $D^{\prime}_{w}$ intersects both $D^{\prime}_{v_{i}}$
and $D^{\prime}_{v_{j}}$. Then, $H[\\{u,w,v_{i},v_{j}\\}]$ is a complete graph
on $4$ vertices, which is a contradiction because $H$ is $K_{4}$-free. Then,
the disks
$D^{\prime}_{v_{1}},D^{\prime}_{v_{3}},D^{\prime}_{v_{5}},D^{\prime}_{v_{7}},D^{\prime}_{v_{9}},D^{\prime}_{v_{11}}$
are pairwise non-overlapping, which is a contradiction to Lemma 3.2. Thus, we
proved that $t\leq 11$ and hence $d_{H}(v)=d_{G}(v)\leq 11$. That is, the
degeneracy of $G$ is at most $11$. ∎

###  3.2 The main algorithm

Our main algorithm for Bipartization on $K_{4}$-free disk graphs is presented
in Algorithm 1. At the beginning, it takes an arbitrary maximal triangle
packing $\mathcal{T}$ of $G$ (line 1) and defines $\mathcal{O}$ as the
triangles in $G$ that have at least one vertex outside $V(\mathcal{T})$. In a
high-level, our algorithm computes three different solutions
$S_{1},S_{2},S_{3}$ and returns the best one.

The first solution $S_{1}$ is computed in exactly the same way as the
3-approximation algorithm described in the introduction. Specifically, we
include in $S_{1}$ all vertices in the triangle packing $\mathcal{T}$, and an
OCT $X_{1}$ of $G-V(\mathcal{T})$ computed by a sub-routine PlanarBip (line
3), which is an algorithm for Bipartization on planar graphs.

The second solution $S_{2}$ is constructed in a more involved way. First, in
each triangle $T\in\mathcal{T}$, we randomly sample one vertex $v_{T}\in T$
(line 6); here the function $\mathsf{random}(T)$ returns each vertex in $T$
with probability $\frac{1}{3}$ and different calls of $\mathsf{random}$ are
independent. Let $R$ be the vertices in $V(\mathcal{T})$ not sampled (line 7).
Then we include in $S_{2}$ all vertices in $R$, all vertices in an arbitrary
maximal triangle packing $\mathcal{T^{\prime}}$ of $G-R$ (line 8), and an OCT
$X_{2}$ of $G-(R\cup V(\mathcal{T}^{\prime}))$ computed by PlanarBip.

If $\mathcal{O}$ is nonempty, we need to construct our third solution $S_{3}$.
We take a maximal packing $\mathcal{T}^{\prime\prime}$ of the triangles in
$\mathcal{O}$ (line 12). Then we include in $S_{3}$ all vertices in
$V(\mathcal{T}^{\prime\prime})\cap V(\mathcal{T})$ and an OCT $X_{3}$ of
$G-(V(\mathcal{T}^{\prime\prime})\cap V(\mathcal{T}))$ recursively computed by
our algorithm (line 13).

Finally, we return the best one among $S_{1},S_{2},S_{3}$ (line 15); here
$\min\\{S_{1},S_{2},S_{3}\\}$ returns the set of smallest size among
$S_{1},S_{2},S_{3}$. If $S_{3}$ is not computed, we simply return
$\min\\{S_{1},S_{2}\\}$. It is obvious that each of $S_{1},S_{2},S_{3}$ is an
OCT of $G$ and thus the algorithm always returns a correct solution. The
quality of the solution obtained will be analyzed in the next section. Also,
one can easily see that Algorithm 1 runs in polynomial time. Indeed, except
the recursive call of OCT in line 13, all the other steps can be done in
polynomial time. Line 13 will only be executed when
$\mathcal{O}\neq\emptyset$. In this case,
$\mathcal{T}^{\prime\prime}\neq\emptyset$ and
$V(\mathcal{T}^{\prime\prime})\neq\emptyset$. Thus, the graph
$G-(V(\mathcal{T}^{\prime\prime})\cap V(\mathcal{T}))$ has at most $n-1$
vertices where $n=V(G)$, and the running time of Algorithm 1 satisfies the
recurrence $T(n)\leq T(n-1)+n^{O(1)}$ which solves to $T(n)=n^{O(1)}$.

Algorithm 1 $\textsc{Bipartization}(G)$ $\triangleright$ $G$ is a $K_{4}$-free
disk graph

1:$\mathcal{T}\leftarrow$ a maximal packing of $\Delta(G)$

2:$\mathcal{O}\leftarrow\\{T\in\Delta(G):T\nsubseteq V(\mathcal{T})\\}$

3:$X_{1}\leftarrow\textsc{PlanarBip}(G-V(\mathcal{T}))$ $\triangleright$
construct the first solution $S_{1}$

4:$S_{1}\leftarrow V(\mathcal{T})\cup X_{1}$

5:for every $T\in\mathcal{T}$ do $\triangleright$ construct the second
solution $S_{2}$

6: $v_{T}\leftarrow\mathsf{random}(T)$

7:$R\leftarrow\bigcup_{T\in\mathcal{T}}(T\backslash\\{v_{T}\\})$

8:$\mathcal{T}^{\prime}\leftarrow$ a maximal packing of $\Delta(G-R)$

9:$X_{2}\leftarrow\textsc{PlanarBip}(G-(R\cup V(\mathcal{T}^{\prime})))$

10:$S_{2}\leftarrow R\cup V(\mathcal{T}^{\prime})\cup X_{2}$

11:if $\mathcal{O}\neq\emptyset$ then $\triangleright$ construct the third
solution $S_{3}$

12: $\mathcal{T}^{\prime\prime}\leftarrow$ a maximal packing of $\mathcal{O}$

13:
$X_{3}\leftarrow\textsc{Bipartization}(G-(V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T})))$

14: $S_{3}\leftarrow(V(\mathcal{T}^{\prime\prime})\cap V(\mathcal{T}))\cup
X_{3}$

15:return $\min\\{S_{1},S_{2},S_{3}\\}$ $\triangleright$ if $S_{3}$ is
undefined, simply return $\min\\{S_{1},S_{2}\\}$

###  3.3 Analysis

In this section, we analyze the (expected) approximation ratio of Algorithm 1.
We denote by $\rho$ this ratio and aim to establish an upper bound for $\rho$.
Consider a given disk graph $G$ which is $K_{4}$-free. Let $\mathsf{opt}$ be
the minimum size of an odd cycle transversal of $G$, and
$\mathcal{T},\mathcal{O}$ be the two sets of triangles as in Algorithm 1. The
output of Algorithm 1 is the best one among three OCT solutions
$S_{1},S_{2},S_{3}$. Therefore, to analyze the approximation ratio of our
algorithm, we have to consider the approximation ratios of
$S_{1},S_{2},S_{3}$. It turns out that each solution $S_{i}$ individually may
be of size $3\mathsf{opt}$ or even larger in worst case. However, as we will
see, the best one among them always admits an approximation ratio strictly
smaller than 3.

In order to analyze the three solutions, we define two important parameters:
$a=|\mathcal{T}|/\mathsf{opt}$ and $b=\mathsf{tri}(\mathcal{O})/\mathsf{opt}$
(recall that $\mathsf{tri}(\mathcal{O})$ is the size of a maximum packing of
$\mathcal{O}$). Note that $a,b\in[0,1]$ because both $|\mathcal{T}|$ and
$\mathsf{tri}(\mathcal{O})$ are at most the size of a maximum triangle packing
in $G$, which is smaller than or equal to $\mathsf{opt}$. The analysis of
$S_{1},S_{2},S_{3}$ will be done in terms of $a$ and $b$, that is, we shall
represent the approximation ratios of $S_{1},S_{2},S_{3}$ as functions of $a$
and $b$. Roughly speaking, we shall show that $S_{1}$ is good when $a$ is
small, $S_{2}$ is good when $b$ is small, and $S_{3}$ is good when both $a$
and $b$ are large. For convenience, we use the notation $\rho_{0}$ to denote
the approximation ratio of the PlanarBip sub-routine used in Algorithm 1.

####  3.3.1 The quality of $S_{1}$

The solution $S_{1}$ is computed using exactly the 3-approximation algorithm
described in the introduction. A more careful analysis shows that its
approximation ratio is related to the parameter $a$: the smaller $a$ is, the
better $S_{1}$ is.

######  Lemma 3.4.

$|S_{1}|\leq(3a+\rho_{0}(1-a))\cdot\mathsf{opt}$.

###### Proof.

Since $a=|\mathcal{T}|/\mathsf{opt}$, and $\mathcal{T}$ is a triangle packing,
we get that $|V(\mathcal{T})|=3|\mathcal{T}|=3a\cdot\mathsf{opt}$. Since
$\mathcal{T}$ is a triangle packing, any odd cycle transversal contains at
least $|\mathcal{T}|$ vertices from $V(\mathcal{T})$, the size of a minimum
odd cycle transversal in $G-V(\mathcal{T})$ is at most
$\mathsf{opt}-|\mathcal{T}|=(1-a)\mathsf{opt}$. Therefore,
$|S_{1}|=|V(\mathcal{T})|+|X_{1}|\leq(3a+\rho_{0}(1-a))\cdot\mathsf{opt}$. ∎

####  3.3.2 The quality of $S_{2}$

Figuring out the quality of $S_{2}$ is the most involved part in our analysis.
Basically, what we shall show is that whenever the parameter $b$ is
sufficiently small, $S_{2}$ always gives us a better-than-3 approximation no
matter what the value of $a$ is. The analysis in this section shall explicitly
use the fact that $G$ is $K_{4}$-free. Let $v_{T}$, $R$, and
$\mathcal{T}^{\prime}$ be as in Algorithm 1. We first need the following
simple observation, which will allow us to bound the expected size of $S_{2}$
using the expected size of $\mathcal{T}^{\prime}$.

######  Observation 3.5.

$\mathbb{E}[|R\cap S_{\textnormal{opt}}|]\geq\frac{1}{3}|R|$ and
$|V(\mathcal{T}^{\prime})\cap
S_{\textnormal{opt}}|\geq|\mathcal{T}^{\prime}|$.

###### Proof.

Since $S_{\textnormal{opt}}$ is an OCT of $G$, it contains at least one vertex
in every triangle $T\in\mathcal{T}$. Thus,
$\mathbb{E}[|(T\backslash\\{v_{T}\\})\cap
S_{\textnormal{opt}}|]\geq\frac{2}{3}$. By the linearity of expectation, we
have

$\mathbb{E}[|R\cap
S_{\textnormal{opt}}|]=\sum_{T\in\mathcal{T}}\mathbb{E}[|(T\backslash\\{v_{T}\\})\cap
S_{\textnormal{opt}}|]\geq\frac{2}{3}|\mathcal{T}|=\frac{1}{3}|R|.$

The fact $|V(\mathcal{T}^{\prime})\cap
S_{\textnormal{opt}}|\geq|\mathcal{T}^{\prime}|$ follows from the fact that
$\mathcal{T}^{\prime}$ is a triangle packing: $S_{\textnormal{opt}}$ contains
at least one vertex in every triangle $T\in\mathcal{T}^{\prime}$. ∎

The above observation implies that $\mathbb{E}[|(R\cup
V(\mathcal{T}^{\prime}))\cap
S_{\textnormal{opt}})|]\geq\frac{1}{3}|R|+\mathbb{E}[|\mathcal{T}^{\prime}|]$.
Therefore, we have $\mathbb{E}[|S_{\text{opt}}\backslash(R\cup
V(\mathcal{T}^{\prime}))|]\leq\mathsf{opt}-\frac{1}{3}|R|-\mathbb{E}[|\mathcal{T}^{\prime}|]$
and hence
$\mathbb{E}[|X_{2}|]\leq\rho_{0}\cdot(\mathsf{opt}-\frac{1}{3}|R|-\mathbb{E}[|\mathcal{T}^{\prime}|])$.
It follows that

$\displaystyle\mathbb{E}[|S_{2}|]$
$\displaystyle=|R|+\mathbb{E}[|V(\mathcal{T}^{\prime})|]+\mathbb{E}[|X_{2}|]$
(1)
$\displaystyle\leq|R|+3\cdot\mathbb{E}[|\mathcal{T}^{\prime}|]+\rho_{0}\cdot\left(\mathsf{opt}-\frac{1}{3}|R|-\mathbb{E}[|\mathcal{T}^{\prime}|]\right)$
$\displaystyle=\left(1-\frac{\rho_{0}}{3}\right)\cdot|R|+\rho_{0}\cdot\mathsf{opt}+(3-\rho_{0})\cdot\mathbb{E}[|\mathcal{T}^{\prime}|]$

We say a vertex $v\in V(\mathcal{T})$ is dead if $v\notin R$ and $v$ is not
contained in any triangle in $G[V(\mathcal{T})\backslash R]$. Let $D$ denote
the set of all dead vertices, which is a random subset of $V(\mathcal{T})$ as
it depends on the random vertices $v_{T}$. For each $v\in V(\mathcal{T})$, let
$\mathsf{deg}(v)$ denote the degree of $v$ in $G[V(\mathcal{T})]$. Recall that
$a=|\mathcal{T}|/\mathsf{opt}$ and $b=\mathsf{tri}(\mathcal{O})/\mathsf{opt}$.
It is easy to see the following relation between $|\mathcal{T}^{\prime}|$ and
$|D|$.

######  Observation 3.6.

$|\mathcal{T}^{\prime}|\leq(a+b)\cdot\mathsf{opt}-\frac{|R|}{3}-\frac{|D|}{3}$.

###### Proof.

Since $\mathcal{T}^{\prime}$ is a triangle packing, we have
$|\mathcal{T}^{\prime}\cap\mathcal{O}|\leq\mathsf{tri}(\mathcal{O})=b\cdot\mathsf{opt}$.
On the other hand, all elements in $\mathcal{T}^{\prime}\backslash\mathcal{O}$
are triangles in $G[V(\mathcal{T})\backslash R]$. However, dead vertices
cannot be the vertex of any triangle in $G[V(\mathcal{T})\backslash R]$. Thus,
the vertices of the triangles in $\mathcal{T}^{\prime}\backslash\mathcal{O}$
must lie in $V(\mathcal{T})\backslash(R\cup D)$. We have
$|V(\mathcal{T})\backslash(R\cup
D)|=3\cdot|\mathcal{T}|-|R|-|D|=3a\cdot\mathsf{opt}-|R|-|D|$, which implies
$|\mathcal{T}^{\prime}\backslash\mathcal{O}|\leq
a\cdot\mathsf{opt}-\frac{|R|}{3}-\frac{|D|}{3}$. Because
$|\mathcal{T}^{\prime}|=|\mathcal{T}^{\prime}\cap\mathcal{O}|+|\mathcal{T}^{\prime}\backslash\mathcal{O}|$,
we have the inequality in the observation. ∎

Combining the above observation with Equation 1, we have

$\displaystyle\mathbb{E}[|S_{2}|]$
$\displaystyle\leq\left(1-\frac{\rho_{0}}{3}\right)\cdot|R|+\rho_{0}\cdot\mathsf{opt}+(3-\rho_{0})\cdot\mathbb{E}[|\mathcal{T}^{\prime}|]$
(2)
$\displaystyle=\left(1-\frac{\rho_{0}}{3}\right)\cdot|R|+\rho_{0}\cdot\mathsf{opt}+(3-\rho_{0})\cdot\left((a+b)\cdot\mathsf{opt}-\frac{|R|}{3}-\frac{\mathbb{E}[D]}{3}\right)$
$\displaystyle=(\rho_{0}+(3-\rho_{0})(a+b))\cdot\mathsf{opt}-(3-\rho_{0})\cdot\frac{\mathbb{E}[|D|]}{3}.$

To show that $S_{2}$ has an approximation ratio below 3 when $b$ is small, the
crucial observation is that we have a large number of dead vertices in
expectation.

######  Observation 3.7.

$\Pr[v\textnormal{ is
dead}]\geq(\frac{1}{3})^{\frac{3}{8}\mathsf{deg}(v)+\frac{1}{4}}$ for all
$v\in V(\mathcal{T})$. Thus, we have
$\mathbb{E}[|D|]\geq(\frac{1}{3})^{\frac{3}{8}d+\frac{1}{4}}(3a\cdot\mathsf{opt})$,
where $d$ is the average degree of $G[V(\mathcal{T})]$.

###### Proof.

Let $v\in V(\mathcal{T})$ and $T_{0}\in\mathcal{T}$ be the triangle containing
$v$. Denote by $N(v)$ the set of neighbors of $v$ in $V(\mathcal{T})$
(excluding $v$ itself). We then have $|N(v)|=\mathsf{deg}(v)$ and
$|N(v)\backslash T_{0}|=\mathsf{deg}(v)-2$. Observe that the graph $G[N(v)]$
is triangle-free. Indeed, if $G[N(v)]$ contains a triangle $T$, then
$T\cup\\{v\\}$ forms a clique in $G$ of size 4, which contradicts with the
fact that $G$ is $K_{4}$-free. As $G[N(v)]$ is triangle-free, it is planar. In
particular, $G[N(v)\backslash T_{0}]$ is planar. It was known that every
$n$-vertex planar graph has a vertex cover of size at most $\frac{3}{4}n$
(indeed, a planar graph is 4-colorable, so it has an independent set of size
at least $\frac{n}{4}$ and thus a vertex cover of size at most
$\frac{3}{4}n$). Thus, $G[N(v)\backslash T_{0}]$ has a vertex cover
$C\subseteq N(v)\backslash T_{0}$ with $|C|\leq\frac{3}{4}|N(v)\backslash
T_{0}|=\frac{3}{4}(\mathsf{deg}(v)-2)$.

Next, we notice that if $v\notin R$ and $C\subseteq R$, then $v$ is a dead
vertex. Indeed, if $v$ is contained in a triangle $\\{v,u,w\\}$ in
$G[V(\mathcal{T})\backslash R]$, then at least one of $u$ and $w$ must be in
$C$, since $C$ is a vertex cover of $N(v)\backslash T_{0}$ (note that
$u,w\notin T_{0}$ for otherwise $v\in R$). Let
$\mathcal{T}_{1}\subseteq\mathcal{T}$ (resp.,
$\mathcal{T}_{2}\subseteq\mathcal{T}$) consist of the triangles that contain
one vertex (resp., two vertices) in $C$. Note that no triangle in
$\mathcal{T}$ can contain three vertices in $C$ because $G[C]$ is triangle-
free. Therefore, $C\subseteq R$ if and only if $v_{T}\notin C$ for all
$T\in\mathcal{T}_{1}\cup\mathcal{T}_{2}$. The events $v_{T}\notin C$ for all
$T\in\mathcal{T}_{1}\cup\mathcal{T}_{2}$ are independent, and happen with
probability $\frac{2}{3}$ if $T\in\mathcal{T}_{1}$ and with probability
$\frac{1}{3}$ if $T\in\mathcal{T}_{2}$. It follows that $\Pr[C\subseteq
R]=(\frac{2}{3})^{|\mathcal{T}_{1}|}\cdot(\frac{1}{3})^{|\mathcal{T}_{2}|}$.
We have the inequality
$|\mathcal{T}_{1}|+2|\mathcal{T}_{2}|=|C|\leq\frac{3}{4}(\mathsf{deg}(v)-2)$.
Subject to $|\mathcal{T}_{1}|\geq 0$, $|\mathcal{T}_{2}|\geq 0$, and
$|\mathcal{T}_{1}|+2|\mathcal{T}_{2}|\leq\frac{3}{4}(\mathsf{deg}(v)-2)$, the
quantity
$(\frac{2}{3})^{|\mathcal{T}_{1}|}\cdot(\frac{1}{3})^{|\mathcal{T}_{2}|}$ is
minimized when $|\mathcal{T}_{1}|=0$ and
$|\mathcal{T}_{2}|=\frac{3}{8}(\mathsf{deg}(v)-2)$, and is equal to
$(\frac{1}{3})^{\frac{3}{8}(\mathsf{deg}(v)-2)}$. Thus, we have
$\Pr[C\subseteq R]\geq(\frac{1}{3})^{\frac{3}{8}(\mathsf{deg}(v)-2)}$.
Furthermore, the events $v\notin R$ and $C\subseteq R$ are independent because
whether $v\notin R$ happens only depends on the choice of $v_{T_{0}}\in
T_{0}$. We have $\Pr[v\notin R]=\frac{1}{3}$ and $\Pr[C\subseteq
R]\geq(\frac{1}{3})^{\frac{3}{8}(\mathsf{deg}(v)-2)}$. Since $v$ is a dead
vertex if both $v\notin R$ and $C\subseteq R$ happen, we finally have
$\Pr[v\textnormal{ is
dead}]\geq(\frac{1}{3})^{\frac{3}{8}\mathsf{deg}(v)+\frac{1}{4}}$. By the
linearity of expectation and the fact
$|V(\mathcal{T})|=3|\mathcal{T}|=3a\cdot\mathsf{opt}$, we then have

$\mathbb{E}[|D|]=\sum_{v\in V(\mathcal{T})}\Pr[v\textnormal{ is
dead}]\geq\sum_{v\in
V(\mathcal{T})}\left(\frac{1}{3}\right)^{\frac{3}{8}\mathsf{deg}(v)+\frac{1}{4}}\geq\left(\frac{1}{3}\right)^{\frac{3}{8}d+\frac{1}{4}}(3a\cdot\mathsf{opt}).$

where $d=\sum_{v\in V(\mathcal{T})}\mathsf{deg}(v)/|V(\mathcal{T})|$. ∎

At the end, we can establish the bound for $\mathbb{E}[|S_{2}|]$.

######  Lemma 3.8.

$\mathbb{E}[|S_{2}|]\leq(\rho_{0}+(1-(\frac{1}{3})^{\frac{3}{8}d+\frac{1}{4}})(3-\rho_{0})a+(3-\rho_{0})b)\cdot\mathsf{opt}$,
where $d$ denotes the average degree of $G[V(\mathcal{T})]$.

###### Proof.

Combining Observation 3.7 with Equation 2 completes the proof. ∎

According to Lemma 3.3, we have $d\leq 22$, and thus the above lemma gives us
a good bound for $\mathbb{E}[|S_{2}|]$: as long as $b$ is sufficiently small,
no matter what $a$ is, we can have that
$\mathbb{E}[|S_{2}|]\leq(3-\alpha)\cdot\mathsf{opt}$ for some constant
$\alpha>0$.

####  3.3.3 The quality of $S_{3}$

Finally, we analyze the quality of $S_{3}$. Given $S_{1}$ is good when $a$ is
small and $S_{2}$ is good when $b$ is small, we clearly want $S_{3}$ to be
good when both $a$ and $b$ are large.

######  Lemma 3.9.

If $\rho\geq 2$, then
$\mathbb{E}[|S_{3}|]\leq(\frac{2b}{3}+\rho(2-a-\frac{b}{3}))\cdot\mathsf{opt}$.

###### Proof.

Let $r=|\mathcal{T}^{\prime\prime}|/\mathsf{opt}$. Since
$\mathcal{T}^{\prime\prime}$ is a maximal packing in $\mathcal{O}$,
$V(\mathcal{T}^{\prime\prime})$ is a hitting set of $\mathcal{O}$, which
implies
$3|\mathcal{T}^{\prime\prime}|=|V(\mathcal{T}^{\prime\prime})|\geq\mathsf{tri}(\mathcal{O})$
and thus
$r\geq\frac{\mathsf{tri}(\mathcal{O})}{3\cdot\mathsf{opt}}=\frac{b}{3}$.

######  Claim 3.10.

$\mathbb{E}[|X_{3}|]\leq\rho(2-a-r)\mathsf{opt}$.

###### Proof.

Let $S^{*}$ be an optimal OCT of $G$. So $|S^{*}|=\mathsf{opt}$. We call a
triangle $T\in\mathcal{T}^{\prime\prime}$ bad if $S^{*}$ contains a vertex
from $V(T)\setminus V(\mathcal{T})$. Since $\mathcal{T}$ is a triangle
packing, we also know that $|S^{*}\cap
V(\mathcal{T})|\geq|\mathcal{T}|=a\cdot\mathsf{opt}$. Thus, the number of bad
triangles in $\mathcal{T}^{\prime\prime}$ is at most $(1-a)\mathsf{opt}$,
because $S^{*}$ contains at most $(1-a)\mathsf{opt}$ vertices outside of
$V(\mathcal{T})$, and any such vertex can be part of at most one triangle in
$\mathcal{T}^{\prime\prime}$. That is, the number of good triangles in
$\mathcal{T}^{\prime\prime}$ is at least $(r-(1-a))\mathsf{opt}$. For each
good triangle $T\in\mathcal{T}^{\prime\prime}$, $S^{*}$ contains a vertex from
$V(T)\cap V(\mathcal{T})$. This implies that
$|S^{*}\cap(V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T}))|\geq(r-(1-a))\mathsf{opt}$, and hence
$|S^{*}\setminus(V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T}))|\leq\mathsf{opt}-(r-(1-a))\mathsf{opt}=(2-a-r)\mathsf{opt}$.
Also, notice that $S^{*}\setminus(V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T}))$ is an OCT of $G-(V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T}))$. Thus, the size of an optimal OCT of
$G-(V(\mathcal{T}^{\prime\prime})\cap V(\mathcal{T}))$ is at most
$(2-a-r)\mathsf{opt}$, which implies
$\mathbb{E}[|X_{3}|]\leq\rho(2-a-r)\mathsf{opt}$. ∎

Since each triangle $T\in\mathcal{T}^{\prime\prime}$ is also in $\mathcal{O}$,
we have $|V(T)\cap V(\mathcal{T})|\leq 2$. This implies that
$|V(\mathcal{T}^{\prime\prime})\cap V(\mathcal{T})|\leq 2r\cdot\mathsf{opt}$.
Now we are ready to deduce

$\displaystyle\mathbb{E}[|S_{3}|]$ $\displaystyle=$
$\displaystyle\mathbb{E}[|V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T})|+|X_{3}|]$ $\displaystyle=$
$\displaystyle|V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T})|+\mathbb{E}[|X_{3}|]$ $\displaystyle\leq$
$\displaystyle(2r\cdot\mathsf{opt})+\rho(2-a-r)\mathsf{opt}\qquad\qquad(\mbox{By
Claim~{}\ref{clim:X3} and }|V(\mathcal{T}^{\prime\prime})\cap
V(\mathcal{T})|\leq 2r\cdot\mathsf{opt})$ $\displaystyle=$
$\displaystyle(2-\rho)r\cdot\mathsf{opt}+\rho(2-a)\mathsf{opt}$
$\displaystyle\leq$
$\displaystyle(2-\rho)\frac{b}{3}\mathsf{opt}+\rho(2-a)\mathsf{opt}\qquad\qquad(\mbox{Because
}r\geq\frac{b}{3},\mbox{ and }2-\rho<0)$ $\displaystyle\leq$
$\displaystyle\left(\frac{2b}{3}+\rho\left(2-a-\frac{b}{3}\right)\right)\cdot\mathsf{opt}.$

This completes the proof of the lemma. ∎

####  3.3.4 Putting everything together

Given the analyses for $S_{1}$, $S_{2}$, and $S_{2}$ in the previous sections,
we are ready to bound the (expected) approximation ratio $\rho$ of the entire
algorithm. Let $\rho_{1}=3a+\rho_{0}(1-a)$,
$\rho_{2}=\rho_{0}+(1-(\frac{1}{3})^{\frac{3}{8}d+\frac{1}{4}})(3-\rho_{0})a+(3-\rho_{0})b$,
$\rho_{3}=\frac{2b}{3}+\rho(2-a-\frac{b}{3})$ be the approximation ratios of
$S_{1},S_{2},S_{3}$ given in Lemmas 3.4, 3.8, 3.9, respectively666In Lemma
3.9, the bound for $\mathbb{E}[|S_{3}|]$ has a condition $\rho\geq 2$. But we
can assume this is always the case, for otherwise our algorithm is already a
2-approximation algorithm.. As the output is the best one among
$S_{1},S_{2},S_{3}$, we have

$\rho\leq\frac{\mathbb{E}[\min\\{|S_{1}|,|S_{2}|,|S_{3}|\\}]}{\mathsf{opt}}\leq\frac{\min\\{\mathbb{E}[|S_{1}|],\mathbb{E}[|S_{2}|],\mathbb{E}[|S_{3}|]\\}}{\mathsf{opt}}\leq\min\\{\rho_{1},\rho_{2},\rho_{3}\\}.$

Note that $\rho_{1},\rho_{2},\rho_{3}$ can be viewed as linear functions of
$a$ and $b$, when the other numbers $d$, $\rho_{0}$, $\rho$ are all fixed. So
we first figure out the values of $a$ and $b$ that maximizes
$\min\\{\rho_{1},\rho_{2},\rho_{3}\\}$. With calculation, we have

$\min\\{\rho_{1},\rho_{2},\rho_{3}\\}\leq\frac{(3-\rho_{0})(2\rho-\rho_{0})}{(3-\rho_{0}+\rho)+(\rho-2)\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})}}+\rho_{0},$ (3)

and the upper bound is achieved when

$a=\frac{(2\rho-\rho_{0})}{(3-\rho_{0}+\rho)+(\rho-2)\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})}}\text{ and }b=\frac{(2\rho-\rho_{0})\cdot
3^{\frac{3}{8}d+\frac{1}{4}}}{(3-\rho_{0}+\rho)+(\rho-2)\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})}},$

in which case $\rho_{1}=\rho_{2}=\rho_{3}$. Now combine Equation 3 with the
inequality $\rho\leq\min\\{\rho_{1},\rho_{2},\rho_{3}\\}$ and re-arrange the
terms in the inequality, we deduce

$(3^{-(\frac{3}{8}d+\frac{5}{4})}+1)\cdot\rho^{2}-((2+\rho_{0})\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})}+3)\cdot\rho+(2\rho_{0}\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})})\leq 0.$

The left-hand side of the above inequality is a quadratic function of $\rho$
in which the coefficient of the quadratic term is positive. Therefore, in
order to make the quadratic function non-positive, $\rho$ must be smaller than
its larger root, i.e.,

$\rho\leq\frac{((2+\rho_{0})\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})}+3)+\sqrt{((2+\rho_{0})\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})}+3)^{2}-(3^{-(\frac{3}{8}d+\frac{5}{4})}+1)(8\rho_{0}\cdot
3^{-(\frac{3}{8}d+\frac{5}{4})})}}{2\cdot(3^{-(\frac{3}{8}d+\frac{5}{4})}+1)}.$

By Lemma 3.3, $G[V(\mathcal{T})]$ is $11$-degenerate and thus $d\leq 22$.
Furthermore, using the $\frac{9}{4}$-approximation algorithm [15] for planar
bipartization, we can set $\rho_{0}=\frac{9}{4}$. Plugging in these values to
the above inequality, we have $\rho\leq 2.99993033741$.

Our entire algorithm first applies Lemma 3.1 with a maximal packing
$\mathcal{C}$ of $K_{4}(G)$ to reduce the problem to $G-V(\mathcal{C})$, which
is a $K_{4}$-free disk graph, and then applies Algorithm 1 on
$G-V(\mathcal{C})$. By Lemma 3.1 and the above analysis, this algorithm solves
Bipartization on disk graphs with an expected approximation ratio at most
$2.99993033741$. By repeating the algorithm polynomial number of times, we can
also obtain a randomized algorithm that achieves the same approximation ratio
with high probability.

######  Theorem 3.11.

There exists a polynomial-time randomized algorithm for Bipartization on the
class of disk graphs that gives a $(3-\alpha)$-approximation solution with
high probability, for some $\alpha>10^{-5}$.

With some efforts, we can derandomize our algorithm to obtain a deterministic
$(3-\alpha)$-approximation algorithm for Bipartization on disk graphs. In
fact, in Algorithm 1, only the construction of the set $R$ is randomized. We
show in Appendix A how to construct $R$ deterministically while still
guaranteeing the nice properties of $R$ (the key point is to guarantee that
there are many dead vertices). The approximation ratio of our deterministic
algorithm is slightly worse than the randomized one (while it is still smaller
than 3).

See 1.2

##  4 Generalizations

In this section, we discuss some generalizations of our result. First, we
observe that our algorithm directly generalizes to pseudo-disk graphs. A set
of geometric objects in the plane are called pseudo-disks if each of them is
homeomorphic to a disk and the boundaries of any two objects intersect at most
twice. A graph is a pseudo-disk graph if it can be represented as the
intersection graph of a set of pseudo-disks.

In our Bipartization algorithm, we only exploit two properties of disk graphs:
(i) triangle-free disk graphs are planar, and (ii) $K_{4}$-free disk graphs
are $c$-degenerate for some constant $c$. In fact, pseudo-disk graphs also
satisfy these two properties.

######  Fact 4.1 ([23]).

Triangle-free pseudo-disk graphs are planar.

######  Fact 4.2.

$K_{4}$-free pseudo-disk graphs are $c$-degenerate for some constant $c$.

###### Proof.

We show that any $K_{r}$-free pseudo-disk graph of $n$ vertices only has
$O(rn)$ edges, which implies the fact. Let $G$ be a $K_{r}$-free pseudo-disk
graph realized by a set $\mathcal{S}$ of pseudo-disks. We say an edge
$(S,S^{\prime})$ of $G$ is an inclusion edge if $S\subseteq S^{\prime}$ or
$S^{\prime}\subseteq S$. We first observe that $G$ has $O(rn)$ inclusion
edges. Indeed, a pseudo-disk $S\in\mathcal{S}$ cannot be contained in $r-1$
(or more) other pseudo-disks in $\mathcal{S}$, for otherwise there is a copy
of $K_{r}$ in $G$. Thus, if we charge every inclusion edge $(S,S^{\prime})$ to
the smaller one of $S$ and $S^{\prime}$, every pseudo-disk is charged at most
$r-2$ times. This implies that $G$ has $O(rn)$ inclusion edges. Now we bound
the number of other edges in $G$. Note that if $(S,S^{\prime})$ is a non-
inclusion edge in $G$, then the boundaries of $S$ and $S^{\prime}$ intersect.
So it suffices to bound the total number of intersection points of the
boundaries of the pseudo-disks in $\mathcal{S}$. The depth of an intersection
point $x$ is the number of pseudo-disks in $\mathcal{S}$ containing $x$. It is
well-known that in a set of $n$ pseudo-disks, the number of boundary
intersection points of depth at most $d$ is bounded by $O(dn)$ [22]. Since $G$
is $K_{r}$-free, every intersection point is of depth at most $r$. Thus, the
total number of boundary intersection points is $O(rn)$, implying that $G$ has
$O(rn)$ edges. ∎

Therefore, our algorithm directly generalizes to pseudo-disk graphs.

See 1.3

Next, we observe that our techniques apply to not only the specific problem of
Bipartization. In fact, it works for a wide class of vertex-deletion problems
on (pseudo-)disk graphs. Recall that in a vertex-deletion problem, the goal is
to delete a minimum set $S$ of vertices from a graph $G$ such that $G-S$
satisfies some desired property P. In Bipartization, the property P is “being
bipartite”. Our technique applies to any vertex-deletion problem that is (i)
hereditary, i.e., if a graph satisfies P then all its induced subgraphs also
satisfy P, and (ii) triangle-conflicting, i.e., a graph satisfies P only if it
is triangle-free.

######  Theorem 4.3.

If a hereditary and triangle-conflicting vertex-deletion problem admits a
$(3-\delta)$-approximation algorithm on the class of planar graphs for some
$\delta>0$, then it admits a $(3-\alpha)$-approximation algorithm on the class
of (pseudo-)disk graphs for some $\alpha>0$.

###### Proof.

We just replace the PlanarBip sub-routine in Algorithm 1 with the
$(3-\delta)$-approximation algorithm for the problem on planar graphs. As one
can easily verify, our analysis only depends on the fact that the vertex-
deletion problem is hereditary and triangle-conflicting. Thus, the same
analysis shows that this is a $(3-\alpha)$-approximation algorithm for the
problem on (pseudo-)disk graphs. ∎

Well-studied instances of hereditary and triangle-conflicting vertex-deletion
problems (other than Bipartization) include Vertex Cover, Feedback Vertex Set,
Triangle Hitting, etc. Most of these problems already have
$(3-\delta)$-approximation algorithms on disk graphs, and some of them do not
have known $(3-\delta)$-approximation algorithms on planar graphs. Thus, at
this point, we can only obtain interesting results for Bipartization. However,
we believe that this is not the full power of Theorem 4.3. To provide some
evidences, let us consider a vertex-deletion problem,
Planarization&Bipartization, in which the desired property P is “being planar
and bipartite”. This problem is clearly hereditary and triangle-conflicting.
On planar graphs, it is equivalent to Bipartization and thus admits a
$(3-\delta)$-approximation algorithm. Therefore, Theorem 4.3 gives a
$(3-\alpha)$-approximation algorithm for Planarization&Bipartization on
(pseudo-)disk graphs. Although this problem itself is somehow artificial and
not well-studied, it reveals that Theorem 4.3 could possibly have further
applications in the future.

## References

  * [1] Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev.  $O(\sqrt{\log n})$ approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems.  In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 573–581. ACM, 2005.
  * [2] Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue.  Subexponential parameterized algorithms for cut and cycle hitting problems on h-minor-free graphs.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2063–2084. SIAM, 2022.
  * [3] Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue.  True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs.  In 38th International Symposium on Computational Geometry (SoCG 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [4] Nikhil Bansal and Subhash Khot.  Optimal long code test with one free bit.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 453–462. IEEE, 2009.
  * [5] Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, and Stéphan Thomassé.  EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs.  J. ACM, 68(2):9:1–9:38, 2021.
  * [6] Hyeong-Ah Choi, Kazuo Nakajima, and Chong S. Rim.  Graph bipartization and via minimization.  SIAM J. Discret. Math., 2(1):38–47, 1989.
  * [7] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.  A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs.  SIAM J. Comput., 49(6):1291–1331, 2020.
  * [8] Thomas Erlebach, Klaus Jansen, and Eike Seidel.  Polynomial-time approximation schemes for geometric intersection graphs.  SIAM J. Comput., 34(6):1302–1323, 2005.
  * [9] Guy Even, Joseph Naor, Satish Rao, and Baruch Schieber.  Divide-and-conquer approximation algorithms via spreading metrics.  J. ACM, 47(4):585–616, 2000.
  * [10] Samuel Fiorini, Nadia Hardy, Bruce A. Reed, and Adrian Vetta.  Approximate min-max relations for odd cycles in planar graphs.  Math. Program., 110(1):71–91, 2007.
  * [11] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Finding, hitting and packing cycles in subexponential time on unit disk graphs.  Discret. Comput. Geom., 62(4):879–911, 2019.
  * [12] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  ETH-tight algorithms for long path and cycle on unit disk graphs.  J. Comput. Geom., 12(2):126–148, 2021.
  * [13] Matt Gibson and Imran A. Pirwani.  Algorithms for dominating set in disk graphs: Breaking the log _n_ barrier - (extended abstract).  In Mark de Berg and Ulrich Meyer, editors, Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, volume 6346 of Lecture Notes in Computer Science, pages 243–254. Springer, 2010.
  * [14] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  J. ACM, 42(6):1115–1145, 1995.
  * [15] Michel X. Goemans and David P. Williamson.  Primal-dual approximation algorithms for feedback problems in planar graphs.  Comb., 18(1):37–59, 1998.
  * [16] Bart MP Jansen and Stefan Kratsch.  On polynomial kernels for structural parameterizations of odd cycle transversal.  In International Symposium on Parameterized and Exact Computation, pages 132–144. Springer, 2011.
  * [17] Bart MP Jansen, Marcin L Pilipczuk, and Erik Jan Van Leeuwen.  A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs.  SIAM Journal on Discrete Mathematics, 35(4):2387–2429, 2021.
  * [18] Andrew B. Kahng, Shailesh Vaya, and Alexander Zelikovsky.  New graph bipartizations for double-exposure, bright field alternating phase-shift mask layout.  In Satoshi Goto, editor, Proceedings of ASP-DAC 2001, Asia and South Pacific Design Automation Conference 2001, January 30-February 2, 2001, Yokohama, Japan, pages 133–138. ACM, 2001.
  * [19] Ken-Ichi Kawarabayashi and Atsuhiro Nakamoto.  The Erdős–Pósa property for vertex-and edge-disjoint odd cycles in graphs on orientable surfaces.  Discrete Mathematics, 307(6):764–768, 2007.
  * [20] Ken-ichi Kawarabayashi and Bruce A. Reed.  An (almost) linear time algorithm for odd cyles transversal.  In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 365–378. SIAM, 2010.
  * [21] Ken-ichi Kawarabayashi and Bruce A. Reed.  Odd cycle packing.  In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 695–704. ACM, 2010.
  * [22] Klara Kedem, Ron Livne, János Pach, and Micha Sharir.  On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles.  Discrete & Computational Geometry, 1(1):59–71, 1986.
  * [23] Jan Kratochvíl.  Intersection graphs of noncrossing arc-connected sets in the plane.  In International Symposium on Graph Drawing, pages 257–270. Springer, 1996.
  * [24] Stefan Kratsch and Magnus Wahlström.  Compression via matroids: a randomized polynomial kernel for odd cycle transversal.  ACM Transactions on Algorithms (TALG), 10(4):1–15, 2014.
  * [25] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.
  * [26] Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh.  Faster parameterized algorithms using linear programming.  ACM Trans. Algorithms, 11(2):15:1–15:31, 2014.
  * [27] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi.  Subexponential parameterized algorithms on disk graphs (extended abstract).  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2005–2031. SIAM, 2022.
  * [28] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi.  A 1.9999-approximation algorithm for vertex cover on string graphs.  In 40th International Symposium on Computational Geometry (SoCG 2024). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024.
  * [29] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavik.  A framework for approximation schemes on disk graphs.  In 34rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2023\.
  * [30] Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström.  Subexponential parameterized odd cycle transversal on planar graphs.  In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2012.
  * [31] Madhav V. Marathe, Heinz Breu, Harry B. Hunt, S. S. Ravi, and Daniel J. Rosenkrantz.  Simple heuristics for unit disk graphs.  Networks, 25:59–68, 1995.
  * [32] Dániel Marx, Pranabendu Misra, Daniel Neuen, and Prafullkumar Tale.  A framework for parameterized subexponential algorithms for generalized cycle hitting problems on planar graphs.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2085–2127. SIAM, 2022.
  * [33] Mihai Pop, Daniel S Kosack, and Steven L Salzberg.  Hierarchical scaffolding with bambus.  Genome research, 14(1):149–159, 2004.
  * [34] Dieter Rautenbach and Bruce Reed.  The Erdos-Pósa property for odd cycles in highly connected graphs.  Combinatorica, 21(2):267–278, 2001.
  * [35] Dieter Rautenbach and Bruce A. Reed.  The Erdos-Pósa property for odd cycles in highly connected graphs.  Comb., 21(2):267–278, 2001.
  * [36] Bruce Reed, Kaleigh Smith, and Adrian Vetta.  Finding odd cycle transversals.  Operations Research Letters, 32(4):299–301, 2004.
  * [37] Bruce A. Reed.  Mangoes and blueberries.  Comb., 19(2):267–296, 1999.
  * [38] Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.  Finding odd cycle transversals.  Oper. Res. Lett., 32(4):299–301, 2004.
  * [39] Romeo Rizzi, Vineet Bafna, Sorin Istrail, and Giuseppe Lancia.  Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem.  In Roderic Guigó and Dan Gusfield, editors, Algorithms in Bioinformatics, Second International Workshop, WABI 2002, Rome, Italy, September 17-21, 2002, Proceedings, volume 2452 of Lecture Notes in Computer Science, pages 29–43. Springer, 2002.
  * [40] Sartaj Sahni and Teofilo F. Gonzalez.  P-complete approximation problems.  J. ACM, 23(3):555–565, 1976.
  * [41] Carsten Thomassen.  The Erdős–Pósa property for odd cycles in graphs of large connectivity.  Combinatorica, 21(2):321–333, 2001.
  * [42] Erik Jan van Leeuwen.  Better approximation schemes for disk graphs.  In Lars Arge and Rusins Freivalds, editors, Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, volume 4059 of Lecture Notes in Computer Science, pages 316–327. Springer, 2006.
  * [43] Sebastian Wernicke.  On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems.  diplom. de, 2014.

##  Appendix A Derandomization

The only randomized step in Algorithm 1 is Step 6 and hence the set $R$ is a
random variable. Towards derandomization we construct three sets
$R_{1},R_{2}$, and $R_{3}$ such that at least one of them is “good”. Next we
explain the construction of these sets $R_{1},R_{2}$, and $R_{3}$. Let
$H^{\prime}=\\{v\in V({\cal T})~{}:~{}d_{G[V({\cal T})]}(v)>100\\}$ be the set
of “high” degree vertices in $G[V({\cal T})]$. Let ${\cal H}$ be the set of
triangles $T$ in ${\cal T}$ such that $T\cap H^{\prime}\neq\emptyset$. Let
${\cal L}={\cal T}\setminus{\cal H}$. Let $H=V({\cal H})$ and $L=V({\cal
L})=V({\cal T})\setminus H$.

  * •

Let $I$ be a maximal distance-$3$ independent set in $G[L]$ constructed as
follows. Initially, set $I:=\emptyset$ and $C:=L$. As long as
$C\neq\emptyset$, pick a vertex $v$ from $C$ and add it to $I$, and delete
$N_{G[L]}[N_{G[L]}[N_{G[L]}[v]]]$ from $C$.

  * •

Let $I_{1},I_{2},I_{3}$ be arbitrary subsets of $I$ such that they are
pairwise disjoint and $|I_{i}|=\lfloor\frac{I}{3}\rfloor$ for all
$i\in\\{1,2,3\\}$.

Before explaining the construction of $R_{1},R_{2}$, and $R_{3}$, we prove the
following lemma.

######  Lemma A.1.

Let $i\in\\{1,2,3\\}$ and $v\in I_{i}$. Let $T$ be a triangle in ${\cal T}$
such that $N_{G}(v)\cap T\neq\emptyset$. Then, there is at least one vertex
$w\in T$ such that $w\notin N_{G}(v)$.

###### Proof.

If $v\in T$, then $v\notin N_{G}(v)$ and $v$ is the required vertex.
Otherwise, we have that $v\notin T$. Then, if all the vertices of $T$ are
adjacent to $v$, the there is a $K_{4}$ with vertex set $T\cup\\{v\\}$. This
is a contradiction to the fact that $G$ is $K_{4}$-free. This completes the
proof of the lemma. ∎

Now we construct $R_{1},R_{2}$, and $R_{3}$ as follows.

  * (a)

Initially, set $R_{i}:=H\cup N_{G[L]}(I_{i})$ for all $i\in\\{1,2,3\\}$.

  * (b)

Because $I$ is a distance-$3$ independent set, for each triangle $T\in{\cal
L}$, there is at most one index $i\in\\{1,2,3\\}$ such that
$N_{G[L]}(I_{i})\cap T\neq\emptyset$.

  * (c)

Now, for each triangle $T$ in ${\cal L}$ we do the following. Let
$T=\\{x_{1},x_{2},x_{3}\\}$.

    * –

Suppose $T\cap R_{i}=\emptyset$ for all $i\in\\{1,2,3\\}$. Then,
$R_{1}:=R_{1}\cup\\{x_{1},x_{2}\\}$, $R_{2}:=R_{2}\cup\\{x_{2},x_{3}\\}$, and
$R_{3}:=R_{3}\cup\\{x_{3},x_{1}\\}$.

    * –

Otherwise, there is exactly one index $i\in\\{1,2,3\\}$ such that
$N_{G[L]}(I_{i})\cap T\neq\emptyset$. Moreover, since $I_{i}$ is a
distance-$3$ independent set, there is exactly one vertex $v\in I_{i}$ such
that $N_{G[L]}(v)\cap T\neq\emptyset$. Without loss of generality, by Lemma
A.1, let $\\{x_{1},x_{2}\\}\supseteq N_{G[L]}(v)\cap T$. Let
$\\{i_{1},i_{2}\\}=\\{1,2,3\\}\setminus\\{i\\}$. Now, we set
$R_{i}:=R_{i}\cup\\{x_{1},x_{2}\\}$,
$R_{i_{1}}:=R_{i_{1}}\cup\\{x_{2},x_{3}\\}$, and
$R_{i_{2}}:=R_{i_{2}}\cup\\{x_{3},x_{1}\\}$.

This completes the construction of $R_{1},R_{2}$, and $R_{3}$. For each
$i\in\\{1,2,3\\}$, let $R_{i}^{\prime}=R_{i}\cap L$. From the construction of
$R_{1},R_{2},R_{3},R_{1}^{\prime},R_{2}^{\prime}$, and $R^{\prime}_{3}$, the
following properties are satisfied.

  * (i)

For each triangle $T$ in ${\cal L}$, exactly two vertices from $T$ belong to
$R_{i}$ for any $i\in\\{1,2,3\\}$. This implies that $|R_{i}^{\prime}|=2|{\cal
L}|$ for all $i\in\\{1,2,3\\}$.

  * (ii)

For each triangle $T$ in ${\cal L}$ and $x\in T$, there are exactly two
distinct indices $i,j\in\\{1,2,3\\}$ such that $x\in R_{i}$ and $x\in R_{j}$

  * (iii)

For each $i\in\\{1,2,3\\}$, $R_{i}\cap I_{i}=\emptyset$ and
$N_{G[L]}(I_{i})\subseteq R_{i}$.

  * (iv)

For each triangle $T$ in ${\cal H}$ and $i\in\\{1,2,3\\}$, $T\subseteq R_{i}$.

Recall that $S_{\sf opt}$ is an optimum solution. Next, we prove a lemma that
is analogous to Observation 3.5.

######  Lemma A.2.

There is an index $j\in\\{1,2,3\\}$ such that $|R_{j}\cap S_{\sf
opt}|\geq\frac{|R_{j}|}{3}$.

###### Proof.

Notice that $S_{\sf opt}$ contains at least one vertex from each triangle $T$
in ${\cal L}$. This statement along with the property (ii) implies the
inequality

$|R^{\prime}_{1}\cap S_{\sf opt}|+|R^{\prime}_{2}\cap S_{\sf
opt}|+|R^{\prime}_{3}\cap S_{\sf opt}|\geq 2|{\cal L}|.$

This implies that there is an index $j\in\\{1,2,3\\}$ such that
$|R^{\prime}_{j}\cap S_{\sf opt}|\geq\frac{2|{\cal L}|}{3}$. By property (ii)
above, we know that $|R_{j}^{\prime}|=2|{\cal L}|$. Thus, we get that
$|R^{\prime}_{j}\cap S_{\sf opt}|\geq\frac{|R_{j}^{\prime}|}{3}$.

By property (iv) above, we get that $R_{j}\setminus R_{j}^{\prime}=V({\cal
H})$ and $|R_{j}\setminus R_{j}^{\prime}|=3|{\cal H}|$. For each triangle $T$
in ${\cal H}$, there is at least one vertex from $T$ that belongs to $S_{\sf
opt}$. Thus, we get

$|(R_{j}\setminus R_{j}^{\prime})\cap S_{\sf
opt}|\geq|\mathcal{H}|=\frac{|R_{j}\backslash R_{j}^{\prime}|}{3}.$

Finally, we have $|R_{j}\cap S_{\sf opt}|\geq\frac{|R_{j}|}{3}$, as
$|R^{\prime}_{j}\cap S_{\sf opt}|\geq\frac{|R_{j}^{\prime}|}{3}$ and
$|(R_{j}\setminus R_{j}^{\prime})\cap S_{\sf opt}|\geq\frac{|R_{j}\setminus
R_{j}^{\prime}|}{3}$. ∎

Now recall the definition of a dead vertex. We say that a vertex $v\in V({\cal
T})$ is dead with respect to $R_{i}$, where $i\in\\{1,2,3\\}$, if $v\notin
R_{i}$ and $v$ is not contained in any triangle in $G[V({\cal T})\setminus
R_{i}]$. Next we prove that there are $\Omega(|{\cal T}|)$ many dead vertices
with respect to $R_{i}$ for each $i\in\\{1,2,3\\}$. Towards that we prove that
for each $i\in\\{1,2,3\\}$, all the vertices in $I_{i}$ are dead with respect
to $R_{i}$ and $|I_{i}|=\Omega(|{\cal T}|)$.

######  Lemma A.3.

For any $i\in\\{1,2,3\\}$, all the vertices in $I_{i}$ are dead with respect
to $R_{i}$

###### Proof.

Fix an index $i\in\\{1,2,3\\}$. From properties (iii) and (iv) we get that
$I_{i}\subseteq V({\cal T})\setminus R_{i}$ and each vertex in $I_{i}$ is an
isolated vertex in $G[V({\cal T})\setminus R_{i}]$. Therefore, all the
vertices in $I_{i}$ are dead with respect to $R_{i}$. ∎

######  Lemma A.4.

For any $i\in\\{1,2,3\\}$, $|I_{i}|\geq\frac{|{\cal T}|}{400^{3}}$

###### Proof.

First, we prove that $|I|\geq\frac{3|{\cal T}|}{4^{2}\cdot 100^{3}}$. Since
the degree of each vertex in $G[L]$ is at most $100$,
$N_{G[L]}[N_{G[L]}[N_{G[L]}[I]]]\leq|I|+100|I|+100^{2}|I|+100^{3}|I|\leq
4\cdot 100^{3}|I|$. Since $|I|$ is a maximal distance-$3$ independent set in
$G[L]$, $N_{G[L]}[N_{G[L]}[N_{G[L]}[I]]]=L$. This implies that
$|I|\geq\frac{|L|}{4\cdot 100^{3}}$.

Let $n^{\prime}=|V({\cal T})|=3|{\cal T}|$. By Lemma 3.3, we know that $G$ is
$11$-degenerate. Hence $G[V({\cal T})]$ is $11$-degenerate. This implies that
the average degree of a vertex in $G[V({\cal T})]$ is at most $22$. Thus, the
number of vertices with degree at least 100 is at most $\frac{n^{\prime}}{4}$.
This implies that $|H|\leq\frac{3n^{\prime}}{4}$ and
$|L|\geq\frac{n^{\prime}}{4}=\frac{3|{\cal T}|}{4}$. Thus, since
$|I|\geq\frac{|L|}{4\cdot 100^{3}}$, we get that $|I|\geq\frac{3|{\cal
T}|}{4^{2}\cdot 100^{3}}$.

Now, for any $i\in\\{1,2,3\\}$, we know that
$|I_{i}|=\lfloor\frac{|I|}{3}\rfloor\geq\frac{|I|}{3}-2$. Therefore, we get
that for any $i\in\\{1,2,3\\}$, $|I_{i}|\geq\frac{|{\cal T}|}{400^{3}}$. This
completes the proof of the lemma. ∎

To summarize, there exists $i\in\\{1,2,3\\}$ such that $|R_{i}\cap
S_{\mathsf{opt}}|\geq\frac{|R_{i}|}{3}$ and the number of dead vertices in
$V(\mathcal{T})$ with respect to $R_{i}$ is at least
$\frac{|\mathcal{T}|}{400^{3}}$. Without loss of generality, we can assume
$R_{1}$ satisfies this condition (in the algorithm, we do not know which one
is good, but we can try all three and take the best one among the three
resulting solutions). Set $R=R_{1}$ and let $D\subseteq V(\mathcal{T})$ be the
set of dead vertices with respect to $R$. Now Observations 3.5 and 3.6 still
hold. Therefore, we still have Equation (2) (without the expectation notations
$\mathbb{E}[\cdot]$), i.e.,

$|S_{2}|\leq(\rho_{0}+(3-\rho_{0})(a+b))\cdot\mathsf{opt}-(3-\rho_{0})\cdot\frac{|D|}{3}.$

We have
$|D|\geq\frac{|\mathcal{T}|}{400^{3}}=\frac{a\cdot\mathsf{opt}}{400^{3}}$, so
the above inequality implies

$|S_{2}|\leq(\rho_{0}+(1-400^{-3})(3-\rho_{0})a+(3-\rho_{0})b)\cdot\mathsf{opt}.$

Now the only difference between the above inequality and the one in Lemma 3.8
is that the number $(\frac{1}{3})^{\frac{3}{8}d+\frac{1}{4}}$ is replaced with
an even smaller constant $400^{-3}$. But as long as this number is a positive
constant, our analysis in Section 3.3.4 can give us an approximation ratio
better than 3. Also, we can directly see from the inequality that if $b$ is
sufficiently small, no matter what $a$ is, we always have
$|S_{2}|\leq(3-\alpha)\cdot\mathsf{opt}$ for some constant $\alpha>0$.