A Tight Approximation Algorithm for the
Cluster Vertex Deletion Problem

In this paper, we close the gap between $2$ and $9/4=2.25$ and prove the following tight result.

All previous approximation algorithms for Cluster-VD are based on the local ratio technique. See the survey of Bar-Yehuda, Bendel, Freund, and Rawitz [22] for background on this standard algorithmic technique. Our algorithm is no exception, see Algorithm 1 below. However, it significantly differs from previous algorithms in its crucial step (see Step 14 below). In fact, almost all our efforts in this paper focus on that particular step of the algorithm (see Theorem 2), which searches for a special type of induced subgraph of $G$, which we now describe.

Let $H$ be an induced subgraph of $G$, and let $c_{H}:V(H)\to\mathbb{Q}_{\geqslant 0}$. The weighted graph $(H,c_{H})$ is said to be $\alpha$-good in $G$ (for some factor $\alpha\geqslant 1$) if $c_{H}$ is not identically $0$ and $c_{H}(X\cap V(H))\leqslant\alpha\cdot\operatorname{\mathrm{OPT}}(H,c_{H})$ holds for every (inclusionwise) minimal hitting set $X$ of $G$. We overload terminology and say that an induced subgraph $H$ is $\alpha$-good in $G$ if there exists a cost function $c_{H}$ such that $(H,c_{H})$ is $\alpha$-good in $G$. We stress that the local cost function $c_{H}$ is defined obliviously of the global cost function $c:V(G)\to\mathbb{Q}_{\geqslant 0}$.

A pair of vertices $u,u^{\prime}$ of $G$ are called twins¹¹1We warn the reader that, in other papers, twins are usually called true twins, whereas two vertices which have the same set of neighbours are called false twins. Since we have no need of false twins in this paper, we have chosen to use twins in place of true twins. if $uu^{\prime}\in E(G)$, and for all $v\in V(G-u-u^{\prime})$, $uv\in E(G)$ if and only if $u^{\prime}v\in E(G)$. We say that $G$ is twin-free if $G$ has no twins. As in [18, 19], if $G$ has a pair of twins $u,u^{\prime}$, then Cluster-VD admits an easy reduction step (see Steps 8–12). The idea is simply to add the cost of $u^{\prime}$ to that of $u$ and delete $u^{\prime}$. This works since $u^{\prime}$ belongs to a minimal hitting set of $G$ if and only if $u$ does (see [18] for a complete proof). Therefore, when searching for $\alpha$-good induced subgraphs, we may assume that $G$ is twin-free, which is crucial for our proofs.

We will use two methods to establish $\alpha$-goodness of induced subgraphs. We say that $(H,c_{H})$ is strongly $\alpha$-good if $c_{H}$ is not identically $0$ and $c_{H}(V(H))\leqslant\alpha\cdot\operatorname{\mathrm{OPT}}(H,c_{H})$. Clearly, if $(H,c_{H})$ is strongly $\alpha$-good then $(H,c_{H})$ is $\alpha$-good in $G$, for every graph $G$ which contains $H$. We say that $H$ itself is strongly $\alpha$-good if $(H,c_{H})$ is strongly $\alpha$-good for some cost function $c_{H}$.

Let $N_{\leqslant i}[v]$ (resp. $N_{i}(v)$) be the set of vertices at distance at most (resp. equal to) $i$ from vertex $v$. We abbreviate $N(v):=N_{1}(v)$ and $N[v]:=N_{\leqslant 1}[v]$. If we cannot find a strongly $\alpha$-good induced subgraph in $G$, we will find an induced subgraph $H$ that has a special vertex $v_{0}$ such that $N[v_{0}]$ is entirely contained in $H$, and a cost function $c_{H}:V(H)\to\mathbb{Z}_{\geqslant 0}$ such that $c_{H}(v)\geqslant 1$ for all vertices $v\in N[v_{0}]$ and $c_{H}(V(H))\leqslant\alpha\cdot\operatorname{\mathrm{OPT}}(H,c_{H})+1$. Notice that no minimal hitting set $X$ can contain all the vertices of $N[v_{0}]$, since if $X$ contains $N(v_{0})$, then $v_{0}$ is an isolated clique. Hence, $c_{H}(X\cap V(H))\leqslant c_{H}(V(H))-1\leqslant\alpha\cdot\operatorname{\mathrm{OPT}}(H,c_{H})$ and so $(H,c_{H})$ is $\alpha$-good in $G$. We say that $(H,c_{H})$ (sometimes simply $H$) is centrally $\alpha$-good (in $G$) with respect to $v_{0}$. Moreover, we call $v_{0}$ the root vertex.

In order to illustrate these ideas, consider the following two examples (see Figure 1). First, let $H$ be a $C_{4}$ (that is, a $4$-cycle) contained in $G$ and $\mathbf{1}_{H}$ denote the unit cost function on $V(H)$. Then $(H,\mathbf{1}_{H})$ is strongly $2$-good, since $\sum_{v\in V(H)}\mathbf{1}_{H}(v)=4=2\operatorname{\mathrm{OPT}}(H,\mathbf{1}_{H})$. Second, let $H$ be a $P_{3}$ contained in $G$, starting at a vertex $v_{0}$ that has degree-$1$ in $G$. Then $(H,\mathbf{1}_{H})$ is centrally $2$-good with respect to $v_{0}$, but it is not strongly $2$-good.

Each time we find a $2$-good weighted induced subgraph $H$ in $G$, the local ratio technique allows us to recurse on an induced subgraph $G^{\prime}$ of $G$ in which at least one vertex of $H$ is deleted from $G$. For example, the $2$-good induced subgraphs mentioned above allow us to reduce to input graphs $G$ that are $C_{4}$-free and have minimum degree at least $2$.

The crux of our algorithm, Step 14, relies on the following structural result.

We also study Cluster-VD from the polyhedral point of view. In particular we investigate how well linear programming (LP) relaxations can approximate the optimal value of Cluster-VD. As in [16, 13, 9], we use the following notion of LP relaxations which, by design, allows for extended formulations.

Fix a graph $G$. Let $d\in\mathbb{Z}_{\geqslant 0}$ be an arbitrary dimension. A system of linear inequalities $Ax\geqslant b$ in $\mathbb{R}^{d}$ defines an LP relaxation of Cluster-VD on $G$ if the following hold: (i) For every hitting set $X\subseteq V(G)$, we have a point $\pi^{X}\in\mathbb{R}^{d}$ satisfying $A\pi^{X}\geqslant b$; (ii) For every cost function $c:V(G)\to\mathbb{Q}_{\geqslant 0}$, we have an affine function $f_{c}:\mathbb{R}^{d}\to\mathbb{R}$; (iii) For all hitting sets $X\subseteq V(G)$ and cost functions $c:V(G)\to\mathbb{Q}_{\geqslant 0}$, the condition $f_{c}(\pi^{X})=c(X)$ holds.

The size of the LP relaxation $Ax\geqslant b$ is defined as the number of rows of $A$. For every cost function $c$, the quantity $\operatorname{\mathrm{LP}}(G,c):=\min\{f_{c}(x)\mid Ax\geqslant b\}$ gives a lower bound on $\operatorname{\mathrm{OPT}}(G,c)$. The integrality gap of the LP relaxation $Ax\geqslant b$ is defined as $\sup\{\operatorname{\mathrm{OPT}}(G,c)/\operatorname{\mathrm{LP}}(G,c)\mid c\in\mathbb{Q}_{\geqslant 0}^{V(G)}\}$.

Letting $\mathcal{P}_{3}(G)$ denote the collection of all vertex sets $\{u,v,w\}$ that induce a $P_{3}$ in $G$, we define

We let $\operatorname{\mathsf{SA}}_{r}(G)$ denote the relaxation obtained from $P(G)$ by applying $r$ rounds of the Sherali-Adams hierarchy [33], a standard procedure to derive strengthened LP relaxations of binary linear programming problems. If a cost function $c:V(G)\to\mathbb{Q}_{\geqslant 0}$ is provided, we let

denote the optimum value of the corresponding linear programming relaxation.

It is not hard to see that the straightforward LP relaxation $P(G)$ has worst case integrality gap equal to $3$ (by worst case, we mean that we take the supremum over all graphs $G$). Indeed, for a random $n$-vertex graph, $\operatorname{\mathrm{OPT}}(G,\mathbf{1}_{G})=n-O(\log^{2}n)$ with high probability. This can be easily proved via the probabilistic method. A similar proof can be found, for instance, in the introduction of [2]). On the other hand, $\operatorname{\mathrm{LP}}(G,\mathbf{1}_{G})\leqslant n/3$, since the vector with all coordinates equal to $\frac{1}{3}$ is feasible for $P(G)$.

On the positive side, we show how applying one round of the Sherali-Adams hierarchy gives a relaxation with integrality gap at most $5/2=2.5$, see Theorem 3. To complement this, we prove that the worst case integrality gap of the relaxation is precisely $5/2$, see Theorem 4. We then show that the integrality gap decreases to $2+\varepsilon$ after applying $\mathrm{poly}(1/\varepsilon)$ rounds, see Theorem 5.

On the negative side, applying known results on Vertex Cover [9], we show that no polynomial-size LP relaxation of Cluster-VD can have integrality gap at most $2-\varepsilon$ for some $\varepsilon>0$. As is the case for similar lower bounds (see [31, 8]), this result is unconditional: it does not rely on P $\neq$ NP nor the Unique Games Conjecture.

We now revisit all previous approximation algorithms for Cluster-VD [39, 18, 19]. The presentation given here slightly departs from [39, 18], and explains in a unified manner what is the bottleneck in each of the algorithms.

Fix $k\in\{3,4,5\}$, and let $\alpha:=(2k-1)/(k-1)$. Notice that $\alpha=5/2$ if $k=3$, $\alpha=7/3$ if $k=4$ and $\alpha=9/4$ if $k=5$. In [19, Lemma 3], it is shown that if a twin-free graph $G$ contains a $k$-clique, then one can find an induced subgraph $H$ containing the $k$-clique and a cost function $c_{H}$ such that $(H,c_{H})$ is strongly $\alpha$-good.

Therefore, in order to derive an $\alpha$-approximation for Cluster-VD, one may assume without loss of generality that the input graph $G$ is twin-free and has no $k$-clique. Let $v_{0}$ be a maximum degree vertex in $G$, and let $H$ denote the subgraph of $G$ induced by $N_{\leqslant 2}[v_{0}]$. In [19], it is shown by a tedious case analysis that one can construct a cost function $c_{H}$ such that $(H,c_{H})$ is $2$-good in $G$, using the fact that $G$ has no $k$-clique.

The simplest case occurs when $k=3$. Then $N(v_{0})$ is a stable set. Letting $c_{H}(v_{0}):=d(v_{0})-1$, $c_{H}(v):=1$ for $v\in N(v_{0})$ and $c_{H}(v):=0$ for the other vertices of $H$, one easily sees that $(H,c_{H})$ is (centrally) $2$-good in $G$ . For higher values of $k$, one has to work harder.

In this paper, we show that one can always, and in polynomial time, construct a cost function $c_{H}$ on the vertices at distance at most $2$ from $v_{0}$ that makes $(H,c_{H})$ $2$-good in $G$, provided that $G$ is twin-free, see Theorem 2. This result was the main missing ingredient in previous approaches, and single-handedly closes the approximability status of Cluster-VD.

Cluster-VD has also been widely studied from the perspective of fixed parameter tractability. Given a graph $G$ and parameter $k$ as input, the task is to decide if $G$ has a hitting set $X$ of size at most $k$. A $2^{k}n^{\mathcal{O}(1)}$-time algorithm for this problem was given by Hüffner, Komusiewicz, Moser, and Niedermeier [24]. This was subsequently improved to a $1.911^{k}n^{\mathcal{O}(1)}$-time algorithm by Boral, Cygan, Kociumaka, and Pilipczuk [11], and a $1.811^{k}n^{\mathcal{O}(1)}$-time algorithm by Tsur [37]. By the general framework of Fomin, Gaspers, Lokshtanov, and Saurabh [20], these parametrized algorithms can be transformed into exponential algorithms which compute the size of a minimum hitting set for $G$ exactly, the fastest of which runs in time $\mathcal{O}(1.488^{n})$.

For polyhedral results, Hosseinian and Butenko [23] gives some facet-defining inequalities of the Cluster-VD polytope, as well as complete linear descriptions for special classes of graphs.

Another related problem is the feedback vertex set problem in tournaments (FVST). Given a tournament $T$ with costs on the vertices, the task is to find a minimum cost set of vertices $X$ such that $T-X$ does not contain a directed cycle.

For unit costs, note that Cluster-VD is equivalent to the problem of deleting as few elements as possible from a symmetric relation to obtain a transitive relation, while FVST is equivalent to the problem of deleting as few elements as possible from an antisymmetric and complete relation to obtain a transitive relation.

In a tournament, hitting all directed cycles is equivalent to hitting all directed triangles, so FVST is also a hitting set problem in a $3$-uniform hypergraph. Moreover, FVST is also UGC-hard to approximate to a constant factor smaller than $2$. Cai, Deng, and Zang [14] gave a $5/2$-approximation algorithm for FVST, which was later improved to a $7/3$-approximation algorithm by Mnich, Williams, and Végh [30]. Lokshtanov, Misra, Mukherjee, Panolan, Philip, and Saurabh [29] recently gave a randomized $2$-approximation algorithm, but no deterministic (polynomial-time) $2$-approximation algorithm is known. For FVST, one round of the Sherali-Adams hierarchy actually provides a $7/3$-approximation [5].

Among other related covering and packing problems, Fomin, Le, Lokshtanov, Saurabh, Thomassé, and Zehavi [21] studied both Cluster-VD and FVST from the kernelization perspective. They proved that the unweighted versions of both problems admit subquadratic kernels: $\mathcal{O}(k^{\frac{5}{3}})$ for Cluster-VD and $\mathcal{O}(k^{\frac{3}{2}})$ for FVST.

We give a sketch of the proof of Theorem 2. Recall that $H=G[N_{\leqslant 2}[v_{0}]]$. If the subgraph induced by $N(v_{0})$ contains a hole (that is, an induced cycle of length at least $4$), then $H$ is strongly $2$-good by Lemma 2.1. If the subgraph induced by $N(v_{0})$ contains an induced $2P_{3}$ (that is, two disjoint copies of $P_{3}$ with no edges between each other), then $H$ is strongly $2$-good by Lemma 2.1. This allows us to reduce to the case where the subgraph induced by $N(v_{0})$ is chordal and $2P_{3}$-free.

Lemma 2.2 then gives a direct construction of a cost function $c_{H}$ which certifies that $(H,c_{H})$ is centrally $2$-good, provided that the subgraph induced by $N[v_{0}]$ is twin-free. This is the crucial step of the proof. It serves as the base case of the induction. Here, we use a slick observation due to Lokshtanov [28]: since the subgraph induced by $N(v_{0})$ is chordal and $2P_{3}$-free, it has a hitting set that is a clique. In a previous version, our proof of Theorem 2 was slightly more complicated.

We show inductively that we can reduce to the case where the subgraph induced by $N[v_{0}]$ is twin-free. The idea is to delete vertices from $H$ to obtain a smaller graph $H^{\prime}$, while preserving certain properties, and then compute a suitable cost function $c_{H}$ for $H$, given a suitable cost function $c_{H^{\prime}}$ for $H^{\prime}$. We delete vertices at distance $2$ from $v_{0}$. When this creates twins in $H$, we delete one vertex from each pair of twins. At the end, we obtain a twin-free induced subgraph of $H[N[v_{0}]]$, which corresponds to our base case.

We conclude the introduction with a brief description of the different sections of the paper. Section 2 is entirely devoted to the proof of Theorem 2. The proof of Theorem 1 is given in Section 3, together with a complexity analysis of Algorithm 1. Section 4 presents our polyhedral results. A conclusion is given in Section 5. There, we state a few open problems for future research.

A vertex of $G$ is apex if it is adjacent to all the other vertices of $G$. A wheel is a graph obtained from a cycle by adding an apex vertex (called the center).

As pointed out earlier in the introduction, $4$-cycles are strongly $2$-good. This implies that the wheel on $5$ vertices is strongly $2$-good (putting a zero cost on the center). We now show that all wheels on at least $5$ vertices are strongly $2$-good. This allows our algorithm to restrict to input graphs such that the subgraph induced on each neighborhood is chordal. In a similar way, we show that we can further restrict such neighborhoods to be $2P_{3}$-free.

Throughout this section, we assume that $H$ is a twin-free graph with an apex vertex $v_{0}$ such that $H-v_{0}$ is chordal and $2P_{3}$-free. Our goal is to construct a cost function $c_{H}$ that certifies that $H$ is centrally $2$-good.

It turns out to be easier to define the cost function on $V(H-v_{0})=N(v_{0})$ first, and then adjust the cost of $v_{0}$. This is the purpose of the next lemma. Below, $\omega(G,c)$ denotes the maximum weight of a clique in weighted graph $(G,c)$.

We now deal with the general case where $G[N[v_{0}]]$ contains twins. We start with an extra bit of terminology relative to twins. Let $G$ be a twin-free graph, and $v_{0}\in V(G)$. Suppose that $u,u^{\prime}$ are twins in $G[N[v_{0}]]$. Since $G$ is twin-free, there exists a vertex $v$ that is adjacent to exactly one of $u$, $u^{\prime}$ in $G$. We say that $v$ is a distinguisher for the edge $uu^{\prime}$ (or for the pair $\{u,u^{\prime}\}$). Notice that either $uu^{\prime}v$ or $u^{\prime}uv$ is an induced $P_{3}$. Notice also that $v$ is at distance $2$ from $v_{0}$.

Now, consider a graph $H$ with a special vertex $v_{0}\in V(H)$ (the root vertex) such that

1. (H1)

   every vertex is at distance at most $2$ from $v_{0}$, and

2. (H2)

   every pair of vertices that are twins in $H[N[v_{0}]]$ has a distinguisher.

Let $v$ be any vertex that is at distance $2$ from $v_{0}$. Consider the equivalence relation $\equiv$ on $N[v_{0}]$ with $u\equiv u^{\prime}$ whenever $u=u^{\prime}$ or $u,u^{\prime}$ are twins in $H-v$. Observe that the equivalence classes of $\equiv$ are of size at most $2$ since, if $u,u^{\prime},u^{\prime\prime}$ are distinct vertices with $u\equiv u^{\prime}\equiv u^{\prime\prime}$, then $v$ cannot distinguish every edge of the triangle on $u$, $u^{\prime}$ and $u^{\prime\prime}$. Hence, two of these vertices are twins in $H$, which contradicts (H2).

From what precedes, the edges contained in $N[v_{0}]$ that do not have a distinguisher in $H-v$ form a matching $M:=\{u_{1}u^{\prime}_{1},\ldots,u_{k}u^{\prime}_{k}\}$ (possibly, $k=0$). Let $H^{\prime}$ denote the graph obtained from $H$ by deleting $v$ and exactly one endpoint from each edge of $M$. Notice that the resulting subgraph is the same, up to isomorphism, no matter which endpoints are chosen.

The lemma below states how we can obtain a cost function $c_{H}$ that certifies that $H$ is centrally $2$-good from a cost function $c_{H^{\prime}}$ that certifies that $H^{\prime}$ is centrally $2$-good. It is inspired by [19, Lemma 3]. See Figure 3 for an example.