Quadratic Kernel for Cliques or Trees Vertex Deletion

The literature on $\mathrm{\Pi }$-deletion problems has studied several variants of Feedback Vertex Set and Cluster Vertex Deletion. Examples of extensions of Feedback Vertex Set are the cases where $\mathrm{\Pi }$ consists of graphs with treewidth at most $\eta$ [16, 31] and graphs that are at most $l$ edges away from forests [37]. Examples of variants of Cluster Vertex Deletion are the cases where $\mathrm{\Pi }$ consists of $s$-plexes [35], $s$-clubs [22], and graphs with a small dominating set number [2].

Jacob et al. [26] introduced the notion of deletion to scattered graph classes. In that paper, they obtained two general tractability results, stating that $({\mathrm{\Pi }}_1,\mathrm{\dots },{\mathrm{\Pi }}_p)$-Vertex Deletion (i) is fixed-parameter tractable when each ${\mathrm{\Pi }}_i$-Vertex Deletion is fixed-parameter tractable, and (ii) admits a $2^{poly(k)}$-time algorithm when each ${\mathrm{\Pi }}_i$ is defined by a finite set of forbidden subgraphs. Jansen et al. [30] improved the time complexity of result (ii) to $2^{O(k)}$. In the subsequent work [27], Jacob et al. considered several specific cases and obtained efficient FPT algorithms and approximation algorithms. In particular, for Cliques or Trees Vertex Deletion, they obtained an $O^{\ast }(4^k)$-time FPT algorithm and a polynomial-time $4$-approximation algorithm. Jacob et al. [28] provided a kernel with $O(k^5)$ vertices for this problem. Tsur [40] improved both of FPT and kernelization results by presenting a deterministic algorithm running in $O({3.46}^k)$ time, a randomized algorithm running in $O({3.103}^k)$ time, and a kernel with $O(k^4)$ vertices.

Several studies have investigated the parameterized complexity of Longest Cycle and its special case, Hamiltonian Cycle, under structural parameterizations. Parameterized by the cluster vertex deletion number, Doucha and Kratochvíl [10] presented an FPT algorithm for Hamiltonian Cycle. Parameterized by the clique-width, Fomin et al. [13, 14] showed that no $n^{o(k)}$-time algorithm for Hamiltonian Cycle exists unless ETH fails. Bergougnoux et al. [3] proved this bound is tight by giving an $n^{O(k)}$-time algorithm. The cases parameterized by treewidth [9], pathwidth [8], twin-cover number [19], and proper interval deletion number [21] are also investigated, as well as directed tree-width [33] and directed feedback vertex set number [29] for the directed version.

Here, we provide a technical overview of Theorems 1 and 2. Section 1.2.1 also contains a brief explanation of how our kernelization algorithm differs from the existing kernelization algorithms by Jacob et al. [28] and Tsur [40].

Here, we briefly explain our ideas toward Theorem 2. Let $G=(V,E)$ be a graph and $X\subseteq V$ be a given vertex subset with $|X|=k$ such that each connected component of $G-X$ is either a clique or a tree. We begin by brute-force the order in which the desired cycle $P$ visits the vertices in $X$. If $P$ is disjoint from $X$, the problem is trivial, so we may assume that $P$ intersects $X$, and denote the vertices in $X\cap P$ by $v_1,\mathrm{\dots },v_l$ in the order they appear along $P$. Let $P_i$ be the $v_i,v_{i+1}$-path appearing on $P$ (indices modulo $l$). Then, unless $P_i$ has length $1$, the internal vertices of $P_i$ belong to a single connected component $C_i$ of $G-X$.

The next step is limiting the candidates of $C_i$. Here, we can state that, as candidates of $C_i$, it is sufficient to consider the top $k$ components that admit the longest $v_i,v_{i+1}$-paths. Then, we can brute-force over all tuples $(C_1,\mathrm{\dots },C_l)$ within a total cost of $2^{O(k\log k)}$. Now, the problem is reduced to solving the following problem for each connected component $H$ of $G-X$, where we set $J_H:=\{i:C_i=H\}$.

Given a list of vertex subset pairs ${\{(V_{i1}:=N(v_i)\cap C_i,V_{i2}:=N(v_{i+1})\cap C_i)\}}_{i\in J_H}$, compute the maximum total length of vertex-disjoint paths ${\{P_i\}}_{i\in J_H}$ such that each $P_i$ is a path from a vertex in $V_{i1}$ to a vertex in $V_{i2}$.

We give FPT algorithms for this problem on both cliques and trees. First, we explain the algorithm for cliques. We brute-force over flags $f\in {\{0,1\}}^{J_H}$, where $f_i=0$ represents that $P_i$ consists of a single vertex, and $f_i=1$ indicates that $P_i$ contains at least two vertices. The problem of whether a family of paths satisfying the conditions defined by $f$ exists can be reduced to the bipartite matching problem and, thus, solved in polynomial time. If such a family of paths exists for some flag $f$ such that $f_i=1$ holds for some $i\in J_H$, we can extend the family to cover all vertices in $H$ by appropriately adding internal vertices to the paths. Thus, in this case, the answer is $|H|-|J_H|$. If such a family of paths exists only for $f=(0,\mathrm{\dots },0)$, the answer is zero. If no such family of paths exists for any $f$, then the problem is infeasible. The time complexity is $O^{\ast }(2^k)$.

Now, we explain the algorithm for trees. Our algorithm uses dynamic programming. We omit the formal details here, but the intuition is as follows. Regard $H$ as a rooted tree. For a vertex $v$ and a set $Z\subseteq J_H$, we define $\mathrm{𝖣𝖯}[v][Z]$ denote the maximum total length of a family of paths ${\{P_i\}}_{i\in Z}$ that can be packed into the subtree rooted at $v$. We compute these values in a bottom-up manner. We can analyze that such dynamic programming can be implemented to work in $O^{\ast }(3^k)$ time.

The rest of this paper is organized as follows. In Section 2, we introduce basic notation and well-known techniques in the literature on kernelization. In Section 3, we prove Theorem 1 by constructing a kernel for Cliques or Trees Vertex Deletion with $O(k^2)$ vertices. Due to the space limitation, some proofs are given in the full version. In the full version, we prove Theorem 2 by presenting an FPT algorithm for Longest Cycle parameterized by the cliques or trees vertex deletion number.

We begin by classifying the vertices into three categories. Let

The vertices belonging to the first, second, and third groups are referred to as large-sparse, large-dense, and small, respectively. The following lemma states that, for any feasible solution $X$, large-sparse vertices are included in either $X$ or a tree component of $G-X$.

The following lemma states a result symmetric to Lemma 5, that is, for any feasible solution $X$, large-dense vertices are included in either $X$ or a clique component of $G-X$.

Several times throughout this paper, we use the following type of alternative evidence for a vertex belonging to a clique component or a tree component.

In the rest of this paper, we will use Lemmas 5, 6, and 7 as basic tools without specifically mentioning them.

In this section, we reduce the size of $N(v)$ for large-sparse vertices $v\in V_{\mathrm{ls}}$. Most of the reduction rules in this section are the same as the quadratic kernelization of Feedback Vertex Set by Thomassé [39], while some details in the analysis require additional care in proofs. We begin with the following.

Let $v$ be a large-sparse vertex and assume Lemma 3 finds a vertex set $B$ with size at most $2k$ that hits all cycles containing $v$. Let ${𝒞}_{\mathrm{tree}}$ be the family of connected components of $G-v-B$ that are trees and adjacent to $v$. Similarly, let ${𝒞}_{\mathrm{nontree}}$ be the family of connected components of $G-v-B$ that are not trees and adjacent to $v$. Since $G-B$ contains no cycle containing $v$, for each $C\in {𝒞}_{\mathrm{tree}}\cup {𝒞}_{\mathrm{nontree}}$, we have $|N(v)\cap C|=1$. Particularly, $|N(v)|=|{𝒞}_{\mathrm{tree}}|+|{𝒞}_{\mathrm{nontree}}|+|N(v)\cap B|$. We bound $|N(v)|$ by bounding these three terms. Obviously, $|N(v)\cap B|\le |B|\le 2k$. To bound $|{𝒞}_{\mathrm{nontree}}|$, we use the following reduction rule.

Now we bound $|{𝒞}_{\mathrm{tree}}|$ by $4k$ using the expansion lemma. We construct an auxiliary bipartite graph $H$. The vertex set of $H$ is $B\dot{\cup }{𝒞}_{\mathrm{tree}}$ with bipartition $(B,{𝒞}_{\mathrm{tree}})$. We add an edge between $b\in B$ and $C\in {𝒞}_{\mathrm{tree}}$ if and only if $N_G(b)\cap C\ne \mathrm{\varnothing }$. We use the following reduction rule to ensure the part ${𝒞}_{\mathrm{tree}}$ does not contain isolated vertices.

Assume $|{𝒞}_{\mathrm{tree}}|\ge 4k$. We apply $2$-expansion lemma to $H$ and obtain vertex sets ${𝒞}^{\prime }\subseteq {𝒞}_{\mathrm{tree}}$ and $B^{\prime }\subseteq B$ such that there is a $2$-expansion of $B^{\prime }$ into ${𝒞}^{\prime }$. We have $|B^{\prime }|\le k$ because otherwise we obtain a $v$-flower of order $k+1$. We apply the following reduction.

Since all the above reduction rules reduce the number of pairs of vertices connected by at least one edge, the reduction rules in this section can be applied only a polynomial number of times. Thus, we have the following.

In this section, we reduce the number of vertices in $V_{\mathrm{ld}}$. This part is the main technical contribution of this paper. As in [28], we apply a $4$-approximation algorithm for Cliques or Trees Vertex Deletion given in [27] and obtain an approximate solution $S\subseteq V$. We apply the following reduction rule to ensure $|S|\le 4k$, which is clearly safe.

Let ${𝒞}_{\mathrm{clique}}$ be the family of connected components of $G-S$ that are cliques of size at least $3$. Similarly, let ${𝒞}_{\mathrm{tree}}$ be the family of connected components of $G-S$ that are trees. The following rule ensures that each vertex $v\in V_{\mathrm{ld}}$ is contained in a clique component of $G-S$ unless $v\in S$.

Now, we finish the overall analysis by bounding the number of vertices in $V\setminus V_{\mathrm{ld}}$. We first bound the number of edges between $S$ and the tree components of $G-S$ (remember, $S$ is a $4$-approximate solution). Let $V_{\mathrm{tree}}:={\bigcup }_{C\in {𝒞}_{\mathrm{tree}}}C$. We begin by the following.

Thus, we can bound the number of vertices in $V_{\mathrm{tree}}$ adjacent to some vertex in $S$.

We apply the following reduction rules by local structures. Most of them appear in [28], but Reduction Rule 19 is new.

Now, we bound $|V_{\mathrm{tree}}|$. We begin with the following.

Now, we can prove the following.

Now, we can bound the size of the whole graph, which directly proves Theorem 1.