Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components

From a parameterized complexity perspective, both Vertex Deletion to $d$-VCC and Edge Deletion to $d$-VCC exhibit rich algorithmic structure. Our main result is an almost-linear-time kernelization for both problems.

In the same report [27] by Dagstuhl, the importance of developing “truly linear-time” FPT algorithms was emphasized – those with running time $𝒪(n+f(k))$ – to handle large-scale network data. While recent advances have made progress in this direction [11, 12], the area remains relatively underexplored. We believe that our kernelization results also contribute meaningfully to this growing body of work.

A central ingredient in our kernelization framework is a structural result concerning the hereditary graph class ${𝒢}_d$, defined as the class of graphs in which every connected component has vertex cover number at most $d$. We show that this class admits a finite forbidden induced subgraph characterization: every minimal obstruction has at most $3d+2$ vertices, and the total number of such obstructions is bounded by $2^{𝒪(d^2)}$. This structural result may be of independent interest and could find applications in other graph modification problems where the goal is to decompose a graph into connected components with bounded vertex cover number.

Let ${\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$ denote the set of minimal forbidden induced subgraphs for ${𝒢}_d$. Observe that, since each graph $H\in {\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$ has at most $3d+2$ vertices, one can design a fixed-parameter tractable (FPT) algorithm for both Vertex Deletion to $d$-VCC and Edge Deletion to $d$-VCC with running time $d^{𝒪(k)}\cdot n^{𝒪(d)}$. The idea is to enumerate all subsets of $V(G)$ of size at most $3d+2$ and check whether any such subset induces a graph in ${\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$. If so, the algorithm branches on how to intersect the obstruction using at most $k$ deletions. A natural question that arises is whether we can identify an obstruction graph $H\in {\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$ more efficiently than by brute-force enumeration. This leads us to the following algorithmic problem.

We design the following algorithm for the Membership or an Obstruction to ${𝒢}_d$ problem.

It is important to note that, while the algorithm of Bentert et al. [5] necessarily incurs an $n^{𝒪(d)}$ dependence in its running time, our results achieve an almost-linear dependence on the input size. At the same time, unless the Exponential Time Hypothesis (ETH) fails, the dependence on $d$ cannot be improved to $2^{o(d)}$ in our setting either. This is because the special case $k=0$ reduces to the classical Vertex Cover problem, which is known to require $2^{\mathrm{\Omega }(d)}$ time under ETH [24].

Finally, we turn to the Edge Deletion to $d$-VCC problem. Observe that for $d=0$, the problem is solvable in polynomial time: in this case, the task reduces to deleting all edges from the input graph, yielding an edgeless graph, which trivially satisfies the vertex cover condition. This stands in contrast to the classical Vertex Cover problem. However, this tractability does not extend beyond $d=0$. In fact, one can show that Edge Deletion to $d$-VCC becomes NP-complete already for $d=1$. Specifically, we can prove that deciding whether one can delete $k$ edges to obtain a graph in which every connected component is a star is NP-complete, via a reduction from the Dominating Set problem.

As a final remark, we observe that the above formulation captures a hierarchy of increasingly general problems. When $d=0$, the vertex-deletion variant reduces to the classical Vertex Cover problem. For $d=1$, each connected component becomes a star. As $d$ increases, the allowed components grow in structural complexity, yet remain bounded by a core of size at most $d$ that governs their internal interactions. This hierarchy offers a smooth trade-off between expressiveness and algorithmic tractability.

To show that ${𝒢}_d$ admits a finite forbidden characterization under the induced subgraph relation, we begin by defining the notion of minimal obstructions for hereditary graph classes. A graph $H$ is called an obstruction for a graph class $ℱ$ if $H\notin ℱ$. We now formally define the family of minimal such obstructions.

The following lemma establishes that all minimal obstructions for the class ${𝒢}_d$ are necessarily connected graphs.

In this section, we present an algorithm for Membership or an Obstruction to ${𝒢}_d$ parameterized by $d$. In particular, we prove the following result.

For our algorithm, we require the following result, which combines a linear-time kernel for the classical Vertex Cover problem [34] with the currently known fastest parameterized algorithm for Vertex Cover [21].

We use this result as a subroutine in our algorithm for Membership or an Obstruction to ${𝒢}_d$, where we need to repeatedly solve Vertex Cover on various induced subgraphs of the input graph. Since the parameter $d$ in Membership or an Obstruction to ${𝒢}_d$ bounds the vertex cover number of each connected component in the target graph, we can apply the proposition with $\eta \le d+1$, ensuring that each call to Vertex Cover runs efficiently with respect to the parameter $d$.
Our proof proceeds in the following steps:

Step 0.

We begin by applying a modified breadth-first search (BFS) that either determines that the total number of edges in $G$ is at most $dn$, or returns a subgraph $G^{\prime }\subseteq G$ with $|E(G^{\prime })|=dn+1$.

Observe that if $G\in {𝒢}_d$, then the number of edges in $G$ is upper bounded by $dn$. Indeed, if a connected component $C$ has vertex cover number at most $d$, then the number of edges in $C$ is at most $d\cdot |V(C)|$. Summing this bound over all connected components yields the claimed global bound of $dn$ on the total number of edges.

In the latter case, when the algorithm returns a subgraph $G^{\prime }\subseteq G$ with $dn+1$ edges, we can immediately proceed to Step 2. This entire step can be executed in time $𝒪(dn)$.

Step 1.

Given a graph $G$, we first use Proposition 17 to check whether ${\text{vc}}_c(G)\le d$. If this test fails, then there exists a connected component $C\subseteq G$ such that $\text{vc}(G[C])>d$. From this point onward, we focus on the subgraph $G[C]$, and aim to output an obstruction $H\in {\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$ with $V(H)\subseteq V(C)$. Without loss of generality, we refer to $G[C]$ as $G$ itself, as we may assume $G$ is connected.

Step 2.

In the second step, we identify a connected induced subgraph $H^{\prime \prime }\subseteq G$ such that $\text{vc}(H^{\prime \prime })=d+1$.

Step 3.

Next, we obtain a subgraph $H^{\prime }\subseteq H^{\prime \prime }$ by making the argument of Lemma 15 constructive. This guarantees that $|V(H^{\prime })|\le 3d+1$. However, $H^{\prime }$ may not yet belong to ${\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$.

Step 4.

Finally, by removing additional vertices from $H^{\prime }$, we obtain a graph $H\in {\text{Obs}}_{{\subseteq }_i}({𝒢}_d)$.

This completes the description of the algorithm for Membership or an Obstruction to ${𝒢}_d$. Next, we show the implementation of some of the non-trivial steps below. The implementation of Steps 2, 3 and 4 will be provided in the full version of the paper.

From this point onward, we assume that we are given a set $S\subseteq V(G)$ of size at most $(3d+2)k$ such that ${\text{vc}}_c(G-S)\le d$. We now examine the connected components of the graph $G-S$. Let $𝒞𝒞(G-S)$ denote the set of connected components of $G-S$. We partition $𝒞𝒞(G-S)$ into two subsets based on the size of the components: We now partition the set of connected components $𝒞𝒞(G-S)$ based on their size:

• $\mathrm{■}$

  Let ${𝒞}_1:=\{C\in 𝒞𝒞(G-S)\mid |V(C)|=1\}$ denote the set of singleton components (i.e., isolated vertices).

• $\mathrm{■}$

  Let ${𝒞}_2:=\{C\in 𝒞𝒞(G-S)\mid |V(C)|>1\}$ denote the set of components with more than one vertex.

We first introduce the following simple reduction rule, which removes all connected components $C$ of $G$ such that $\text{vc}(C)\le d$. The safeness of this rule is immediate.

Next, we aim to bound the number of connected components in $𝒞𝒞(G-S)$ that contain more than one vertex, i.e., the components in the set ${𝒞}_2$. To achieve this, we make use of the Expansion Lemma.

To bound the number of non-trivial connected components in $G-S$, we apply the $q$-Expansion Lemma. Specifically, we aim to upper-bound the number of components in ${𝒞}_2$. To this end, we construct a bipartite graph $B=(S\cup {𝒞}_2,E_B)$ that captures the adjacency between the approximate deletion set $S$ and the components in ${𝒞}_2$. Formally, the bipartition of $B$ is defined as follows:

• $\mathrm{■}$

  The left side of the bipartition corresponds to the set $S\subseteq V(G)$, and

• $\mathrm{■}$

  The right side contains one representative vertex for each connected component $C\in {𝒞}_2$.

We add an edge between a vertex $p\in S$ and a component $C\in {𝒞}_2$ if and only if $p$ is adjacent (in $G$) to at least one vertex in $C$; that is, if $N_G(p)\cap V(C)\ne \mathrm{\varnothing }$. We slightly abuse notation by referring to both a connected component $C\in {𝒞}_2$ and its corresponding vertex in $B$ using the same symbol.

Note that by Reduction Rule 1, every component in ${𝒞}_2$ has at least one neighbor in $S$; hence, there are no isolated vertices on the right side of the bipartite graph $B$. We now apply the Expansion Lemma (Lemma 20) to this bipartite graph to argue that if $|{𝒞}_2|$ is too large relative to $|S|$, then the instance must be a No-instance. This leads to the following reduction rule:

To establish the correctness of Reduction Rule 2, we prove the following lemma.

After exhaustively applying Reduction Rules 1 and 2, we obtain that the number of non-trivial components in ${𝒞}_2$ satisfies the bound $|{𝒞}_2|\le (d+1)(3d+2)k$. However, if we remove these connected components one by one as suggested, the overall running time may no longer remain bounded by $𝒪({(kd)}^{𝒪(1)}n\log n)$.

To address this, we proceed as follows. Let $Q\subseteq S$ be the subset of vertices in $S$ that have at least $k+d+1$ neighbors on the right side of the bipartite graph $B$, i.e., into ${𝒞}_2$. We claim that every solution $Z\subseteq V(G)$ of size at most $k$ must contain all vertices in $Q$.

Indeed, suppose for contradiction that there exists a vertex $v\in Q\setminus Z$. Since $v$ has at least $k+d+1$ neighbors in ${𝒞}_2$, and $Z$ contains at most $k$ vertices, there are at least $d+1$ components in ${𝒞}_2$ that are completely disjoint from $Z$. But then, in the graph $G-Z$, the vertex $v$, along with these $d+1$ components, induces a subgraph that requires a vertex cover of size at least $d+1$, contradicting the assumption that $Z$ is a valid solution (i.e., ${\text{vc}}_c(G-Z)\le d$). This proves that all vertices in $Q$ must belong to any valid solution of size at most $k$.

Since the number of edges in the bipartite graph $B$ is upper bounded by the number of edges in $G$, we can compute the set $Q$ in time $𝒪(n(d+k))$. After removing $Q$, let ${𝒞}_0\subseteq {𝒞}_2$ denote the set of components that become isolated on the right side of $B$. These correspond to all connected components $C\subseteq G-Q$ such that $\text{vc}(C)\le d$. By applying Reduction Rule 1, we can remove all such components in ${𝒞}_0$ simultaneously. This step also takes linear time. Following this reduction, the number of remaining non-trivial components – i.e., the size of ${𝒞}_2$, which corresponds to the non-isolated vertices on the right side of the updated bipartite graph $B$ – is upper bounded by $(3d+2)k(k+d)$. We now apply Reduction Rule 2 exhaustively on this reduced bipartite graph to further shrink ${𝒞}_2$ to at most $(3d+2)kd$ components. The number of times Reduction Rule 2 needs to be applied is at most $𝒪(k^{2}d)$, and each invocation takes time $𝒪(|E(B)|\cdot \sqrt{|V(B)|})$. Since the number of edges in $B$ is at most $𝒪(d^2{k}^3)$ and the number of vertices is at most $𝒪(k^{2}d)$, the total time required for this step is bounded by $𝒪(k^6{d}^{3.5})$. We summarize our results in the following lemma.

Let $(G^{\prime },k^{\prime })$ be the equivalent instance of Vertex Deletion to $d$-VCC obtained from $(G,k)$ by application of Lemma 22. For clarity of presentation, we rename $(G^{\prime },k^{\prime })$ back to $(G,k)$. We now enhance the set $S$ to a new set $S^{\prime }\subseteq V(G)$ such that $G-S^{\prime }$ is an independent set; in other words, $S^{\prime }$ is a vertex cover of $G$. To this end, observe that each connected component in ${𝒞}_2$ has a vertex cover of size at most $d$, and by previous reductions, the number of such components is at most $(3d+2)kd$. In particular, we get the following.

Next, we apply a marking scheme to bound the size of the independent set $G-S^{\prime }$ obtained after augmenting $S$.

Let $\mathrm{𝖬𝖺𝗋𝗄}$ be the set of marked vertices. After marking the vertices of $G-S^{\prime }$ we give the following reduction rule.

To prove the safeness of above Reduction 4, we proof the following lemma.

We now describe an implementation of Reduction Rule 4.

For every pair of vertices $(u,v)\in S^{\prime }\times S^{\prime }$, we maintain a set $\mathrm{𝖬𝖺𝗋𝗄}(u,v)$, where $u$ may be equal to $v$. Along with each such pair, we keep a counter $k_{(u,v)}$ that tracks the size of $\mathrm{𝖬𝖺𝗋𝗄}(u,v)$. Initially, for all $(u,v)\in S^{\prime }\times S^{\prime }$, we set $\mathrm{𝖬𝖺𝗋𝗄}(u,v)=\mathrm{\varnothing }$ and $k_{(u,v)}=0$.

Next, we iterate over each vertex $x\in V(G)\setminus S^{\prime }$ and perform the following operations:

• $\mathrm{■}$

  For every neighbor $y\in 𝖭(x)$, if $k_{(y,y)}\le k+d$, then add $x$ to $\mathrm{𝖬𝖺𝗋𝗄}(y,y)$ and increment the counter: $k_{(y,y)}\leftarrow k_{(y,y)}+1$.

• $\mathrm{■}$

  For every unordered pair $y,z\in 𝖭(x)$ with $y\ne z$, if $k_{(y,z)}\le k$, then add $x$ to $\mathrm{𝖬𝖺𝗋𝗄}(y,z)$ and increment the counter: $k_{(y,z)}\leftarrow k_{(y,z)}+1$.

Note that since $V(G)\setminus S^{\prime }$ is an independent set, each vertex $x\in V(G)\setminus S^{\prime }$ has all of its neighbors in $S^{\prime }$. By earlier bounds, we know that $|S^{\prime }|=𝒪(d^{3}k)$, and hence $|𝖭(x)|\le 𝒪(d^{3}k)$. Therefore, for each vertex $x$, we perform at most $𝒪({|𝖭(x)|}^2)=𝒪(d^6{k}^2)$ operations.

As a result, the entire marking procedure (Marking Scheme 1) and application of Reduction Rule 4 can be carried out in total time $𝒪({(kd)}^{𝒪(1)}n)$.

The size of the kernel is upper bounded by the number of vertices in $S^{\prime }$ and those in the marked sets. Specifically, the total number of vertices is bounded by:

Furthermore, if the number of edges in the reduced graph exceeds $𝒪(d^9{k}^4)$, we can safely return a trivial No-instance, as such a graph cannot admit a solution of size at most $k$ within the class ${𝒢}_d$. The running time of the overall algorithm is computed as follows:

• $\mathrm{■}$

  Approximate solution: Compute the set $S$, an approximate solution, using Lemma 18, in time $𝒪(k\cdot ({1.253}^d{d}^{𝒪(1)}n\log n))$.

• $\mathrm{■}$

  Vertex cover augmentation: Compute a set $S^{\prime }\supseteq S$ such that:

  • –

    $S^{\prime }$ is a vertex cover of $G$, and

  • –

    $|S^{\prime }|\le (3d+2)k+d\cdot (3d+2)kd=𝒪(d^{3}k)$,

  using Lemmas 22 and 23, in time $𝒪({1.253}^d\cdot d^{𝒪(1)}\cdot n+{(kd)}^{𝒪(1)}n)$.

• $\mathrm{■}$

  Applying Reduction Rule 4: This is done using Lemma 25, in time $𝒪({(kd)}^{𝒪(1)}n)$.

Hence, the overall running time of the algorithm is

This gives us the following result.