Parameterized Complexity Dichotomy for (r, ℓ)-Vertex Deletion

Abstract

For two integers r, ℓ ≥ 0, a graph G = (V, E) is an (r, ℓ)-graph if V can be partitioned into r independent sets and ℓ cliques. In the parameterized (r, ℓ)-Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an (r, ℓ)-graph. This problem is NP-hard if r + ℓ ≥ 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of (r, ℓ)-Vertex Deletion was known for all values of (r, ℓ) except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of (r, ℓ)-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

1 Introduction

Motivation

Let r, ℓ ≥ 0 be two fixed integers. A graph G = (V, E) is an (r, ℓ )-graph if V can be partitioned into r independent sets and ℓ cliques. In the parameterized (r, ℓ)-Vertex Deletion problem, we are given a graph G and an integer parameter k, and the task is to decide whether at most k vertices can be removed from G so that the resulting graph is an (r, ℓ)-graph. The optimization version of this problem is known to be NP-hard for r + ℓ ≥ 1 by a classical result of Lewis and Yannakakis [17]. The (r, ℓ)-Vertex Deletion problem has a big expressive power as it captures several relevant problems for particular cases of the pair (r, ℓ). Indeed, for instance, the case (1,0) corresponds to Vertex Cover, the case (2,0) to Odd Cycle Transversal, the case (1,1) to Split Vertex Deletion, and the case (3,0) to whether at most k vertices can be removed so that the resulting graph is 3-colorable.

In this article we are interested in the parameterized complexity of (r, ℓ)-Vertex Deletion; see [7, 9, 21] for introductory textbooks to the field. We just recall that a problem defined on an n-vertex graph is fixed-parameter tractable (FPT for short) with respect to a parameter k if it can be solved in FPT-time, i.e., in time f(k)⋅n ^O(1). An FPT-algorithm that runs in time 2^O(k)⋅n ^O(1) is called single-exponential. For the case of Vertex Cover (VC for short), a simple branching algorithm yields an FPT-algorithm in time 2^k⋅n ^O(1). The currently fastest algorithm [3] runs in time 1.27^k⋅n ^O(1). For Odd Cycle Transversal (OCT for short), the problem was not known to be FPT until Reed et al. [23] introduced the celebrated technique of iterative compression and solved OCT in time 3^k⋅n ^O(1). The current fastest algorithm [18] uses linear programming and runs in time 2.31^k⋅n ^O(1). The Split Vertex Deletion problem can be easily seen to be solvable in single-exponential time since split graphs can be characterized by a finite set of forbidden induced subgraphs [2, 10]. The current fastest algorithm is by Cygan and Pilipczuk [5] and runs in time $\mathcal {O}(1.2738^{k}k^{\mathcal {O}(\log k)}+n^{3})$ using Vertex Cover as a subroutine. It improves the previously fastest algorithm that runs in time 2^k⋅n ^O(1) and uses iterative compression [11], which in turn improves another algorithm using linear programming [18] that runs in time 2.31^k⋅n ^O(1). (See also [16] for parameterized algorithms for (r, ℓ)-Vertex Deletion on perfect graphs.)

Note that solving (r, ℓ)-Vertex Deletion on a graph G is equivalent to solving (ℓ, r)-Vertex Deletion on the complement of G. This observation implies that the case (0,2) can also be solved in time 2.31^k⋅n ^O(1). Note also that if max{r, ℓ}≥3, then (r, ℓ)-Vertex Deletion is para-NP-complete, hence unlikely to be FPT, as for k = 0 the problem corresponds to the recognition of (r, ℓ)-graphs, which is NP-complete if and only if max{r, ℓ}≥3 [1, 8].

Therefore, concerning the parameterized complexity of the (r, ℓ)-Vertex Deletion problem on general graphs, the above discussion implies that the only open cases are (2,1), (1,2), and (2,2). Note also that all the cases that are known to be FPT can be solved in single-exponential time.

Our Results

In this article we prove that each of the above three open cases is FPT and can also be solved in single-exponential time, thus completely settling the parameterized complexity of (r, ℓ)-Vertex Deletion. That is, excluding the trivial case where r + ℓ = 0, we obtain the following dichotomy: the problem is FPT and solvable in single-exponential time if max{r, ℓ} ≤ 2, and para-NP-complete otherwise. As discussed later, a single-exponential running time is asymptotically best possible in terms of k unless the Exponential Time Hypothesis (ETH) fails. A summary of the parameterized complexity of (r, ℓ)-Vertex Deletion is shown in Table 1, where for each value of (r, ℓ), the name of the problem (if any), the function f(k), and the appropriate references are given. We denote by $\overline {\textsc {VC}}$ and $\overline {\textsc {OCT}}$ the complementary problems of VC and OCT, respectively. The results of this article correspond to the gray boxes, ‘p-NP-c’ stands for ‘para-NP-complete’, and ‘P’ means that the corresponding problem is polynomial-time solvable.¹

Table 1 Summary of results for the (r, ℓ)-Vertex Deletion problem

We also consider the version of (r, ℓ)-Vertex Deletion where the set S of at most k vertices to be removed has to further satisfy that G[S] is an independent set. We call this problem Independent (r, ℓ)-Vertex Deletion. Note that, in contrast to (r, ℓ)-Vertex Deletion, the cases (r, ℓ) and (ℓ, r) may not be symmetric anymore. This problem has received little attention in the literature and, excluding the most simple cases, to the best of our knowledge only the case (2,0) has been studied by Marx et al. [20], who proved it to be FPT. Similarly to (r, ℓ)-Vertex Deletion, the problem is para-NP-complete if max{r, ℓ}≥3. As an additional motivation for studying this problem, note that solving Independent (r, ℓ)-Vertex Deletion on an input (G, k) corresponds exactly to deciding whether G is an (r+1, ℓ)-graph where one of the independent sets has size at most k.

We manage to provide a complete characterization of the parameterized complexity of Independent (r, ℓ)-Vertex Deletion. The complexity landscape turns out to be richer than the one for (r, ℓ)-Vertex Deletion, and one should rather speak about a trichotomy: the problem is polynomial-time solvable if r≤1 and ℓ≤2, NP-hard and FPT if r = 2 and ℓ≤2, and para-NP-complete otherwise. In particular, as discussed at the end of the previous paragraph, it follows from our results that for ℓ∈{0,1,2}, the recognition of the class of (3, ℓ)-graphs such that one of the independent sets has size at most k is in FPT with parameter k. A summary of the complexity of Independent (r, ℓ)-Vertex Deletion is shown in Table 2, where our results correspond to the gray boxes. We would like to note that some of the polynomial cases, such as the case (1,0), are not difficult to prove and may be already known, although we are not aware of it.

Table 2 Results for Independent (r, ℓ)-Vertex Deletion

Our Techniques

As most of the previous work mentioned before, our algorithms for (r, ℓ)-Vertex Deletion (Section 4) are based on iterative compression. We provide an algorithm for (2,2)-Vertex Deletion, and we show that (1,2)-Vertex Deletion and (2,1)-Vertex Deletion can be easily reduced to (2,2)-Vertex Deletion. For completeness, we include in Section 3 some well-known properties of iterative compression. As a crucial ingredient in our algorithms, we prove (Lemma 1 in Section 2) that given two (r, ℓ)-partitions of an n-vertex (r, ℓ)-graph, these two (r, ℓ)-partitions differ by at most 2rℓ vertices, where an (r, ℓ)-partition of an (r, ℓ)-graph G is a partition (R, L) of V(G) such that G[R] is an (r,0)-graph and G[L] is a (0, ℓ)-graph. Furthermore, if max{r, ℓ} ≤ 2, it is known that we can find an (r, ℓ)-partition of an (r, ℓ)-graph in polynomial time [1]. This implies, in particular, that an n-vertex (r, ℓ)-graph has at most (n+1)^2rℓ distinct (r, ℓ)-partitions that can be generated in polynomial time if max{r, ℓ} ≤ 2. This result generalizes the fact that a split graph has at most n+1 split partitions [12], which was used in the algorithms of [11].

Our algorithms for Independent (r, ℓ)-Vertex Deletion (Section 5) are slightly more involved, and do not explicitly use iterative compression. Again, we provide an algorithm for Independent (2,2)-Vertex Deletion and then show that Independent (2,1)-Vertex Deletion can be reduced to Independent (2,2)-Vertex Deletion. We make use our algorithms for (2,2)-Vertex Deletion to obtain a set of vertices S that allows us to exploit the structure of G−S. A crucial ingredient here is the FPT-algorithm of Marx et al. [20] to solve the Restricted Independent OCT problem (see Section 2 for the definition).

Remarks and Further Research

Having completely settled the parameterized complexity of (r, ℓ)-Vertex Deletion and Independent (r, ℓ)-Vertex Deletion, a natural direction is to improve the running times of our algorithms. We did not focus in this article on optimizing the degree of the polynomial n ^O(1) involved in our running times. Concerning the function f(k), for (r, ℓ)-Vertex Deletion this improvement would be possible, under ETH, only in the basis of the function 3.31^k (see Theorem 3). For Independent (r, ℓ)-Vertex Deletion, there may be room for improvement in the function $2^{2^{O(k^{2})}}$ that we obtain mainly by analyzing the running time of the algorithm of Marx et al. [20] to solve Restricted Independent OCT, which was not explicit in their article.

Concerning the existence of polynomial kernels for (r, ℓ)-Vertex Deletion, a challenging research avenue is to apply the techniques used by Kratsch and Wahlström [15] for obtaining a randomized polynomial kernel for OCT to the cases (2,1), (1,2), and (2,2), or to prove that these problems do not admit polynomial kernels. The ideas for the case (1,1) may also be helpful [11].

Finally, it is worth mentioning that if the input graph is restricted to be planar, there exists a randomized subexponential algorithm for OCT [19] running in time $O(n^{O(1)} + 2^{O(\sqrt {k} \log k)}n)$. As in a planar graph any clique is of size at most 4, by guessing one or two cliques and then applying this algorithm, we obtain randomized algorithms in time $2^{O(\sqrt {k} \log k)}\cdot n^{O(1)}$ for (2,1)-Vertex Deletion, (1,2)-Vertex Deletion, and (2,2)-Vertex Deletion on planar graphs.

2 Preliminaries

We use standard graph-theoretic notation, and the reader is referred to [6] for any undefined term. All the graphs we consider are undirected and contain neither loops nor multiple edges. If S⊆V(G), we define G−S = G[V(G)∖S]. The complement of a graph G = (V, E) is denoted by $\overline {G}$, that is, $\overline {G} = (V,E^{\prime })$ with E ^′ = {{x, y}∈(V×V)∖E}. Throughout the article n denotes the number of vertices of the input graph of the problem under consideration.

It is shown in [12] that a (1,1)-graph has at most n+1 distinct (1,1)-partitions. We generalize this property in the following lemma, whose proof is based on the proof of [8 Theorem 3.1].

Lemma 1

Let r and ℓ be two fixed integers, and let (R,L) and (R ^′ ,L ^′ ) be two (r,ℓ)-partitions of a graph G. Let L _sel =L ^′ ∩R and R _sel =R ^′ ∩L. Then L _sel and R _sel are both of size at most rℓ, R ^′ =(R∖L _sel )∪R _sel , and L ^′ =(L∖R _sel )∪L _sel .

Proof

Let G = (V, E) be an (r, ℓ)-graph, and let (R, L) and (R ^′, L ^′) be two distinct (r, ℓ)-partitions of G. We claim that |R∩L ^′|≤rℓ. Indeed, assume that there exists a set S of rℓ+1 vertices in R∩L ^′. As S⊆L ^′, by the pigeonhole principle there exists a subset S ^′⊆S of size r+1 such that G[S ^′] is a clique. As S ^′⊆R, the (r,0)-graph G[R] contains a clique G[S ^′] of size r+1, that contradict the definition of an (r,0)-graph. Symmetrically, it also holds that |R ^′∩L|≤rℓ, and the lemma follows. □

For our algorithms we need the following restricted versions of OCT.

Lemma 2

Restricted OCT can be solved in time 2.31 ^k ⋅n ^O(1).

Proof

The algorithm from Lokshtanov et al. [18] solves OCT in time 2.31^k⋅n ^O(1). For our lemma, we use this algorithm on a modified input. Let G = (V, E) be a graph, D⊆V, and k an integer. We want to solve Restricted OCT on (G, D, k). Let G ^′ = (V ^′, E ^′), where V ^′ = D∪{v _i :v∈V∖D, i∈{0,…, k}} and E ^′ = (E∩(D×D))∪{{v _i , w}:v∈V∖D, i∈{0,…, k}, w∈D,{v, w}∈E}∪{{v _i , w _j }:v, w∈V∖D, i, j∈{0,…, k},{v, w}∈E}. That is, for each vertex v not in D, we make k+1 copies of v with the same neighborhood as v, making its choice for the solution impossible. Then we solve Odd Cycle Transversal on (G ^′, k), giving us a solution of Restricted OCT on (G, D, k). □

By looking carefully at the proof of [20, Theorem 4.3], we have the following theorem. We will analyze the running time of the algorithm in Section 5.3.

Theorem 1 (Marx et al. 20)

Restricted Independent OCT is FPT.

We will also need to deal with the Independent Vertex Cover problem, which given a graph G and an integer k, asks whether G contains a set S⊆V(G) of size at most k that is both a vertex cover of G and an independent set.

Lemma 3

Independent Vertex Cover can be solved in linear time.

Proof

Let G be a graph and let k be a positive integer. Note that for Independent Vertex Cover to admit a solution in G, in particular G needs to be 2-colorable. Hence, if G is not bipartite, we can directly conclude that Independent Vertex Cover on G has no solution.

So we may assume that G = (V, E) is a bipartite graph, and we proceed to construct a solution S of minimum size. For each connected component of G, we define (B ₁, B ₂) as the unique bipartition of its vertex set such that |B ₁|<|B ₂| and B ₁ and B ₂ are two independent sets. (If |B ₁|=|B ₂|, we arbitrarily choose B ₁ being one of them and B ₂ being the other one.) Note that S cannot contain vertices in both B ₁ and B ₂, since in that case by connectivity there would exist an alternating path in G with only the endvertices in S, and then either there is an edge between both endvertices (contradicting the fact that S should be an independent set), or some edge in the path does not contain vertices in S (contradicting the fact that S should be a vertex cover). Thus, if S is a minimum-size solution, necessarily S∩(B ₁∪B ₂) = B ₁. (If |B ₁|=|B ₂|, then S∩(B ₁∪B ₂) is equal to either B ₁ or B ₂, and we assume without loss of generality that the former case holds.) Therefore, we start with S = ∅, and for each connected component of G, we add each element of B ₁ to S. After exploring the whole graph, if |S|≤k then we return S, otherwise we report that no such a set exists. □

We would like to note that Theorem 4 in Section 5 generalizes Lemma 3 above.

The following simple lemma will be exhaustively used in the following sections. A problem π₁ is polynomial-time reducible to a problem π₂ if there exists a polynomial-time algorithm that transforms an instance I ₁ of π₁ into an instance I ₂ of π₂ such that I ₁ is a Yes-instance if and only if I ₂ is.

Lemma 4

Let r and ℓ be two positive integers. Then

• (i) (r,ℓ)-Vertex Deletion is polynomial-time reducible to (r,ℓ+1)-Vertex Deletion,

• (ii) (r,ℓ)-Vertex Deletion is polynomial-time reducible to (r+1,ℓ)-Vertex Deletion,

• (iii) Independent (r,ℓ)-Vertex Deletion is polynomial-time reducible to Independent (r,ℓ+1)-Vertex Deletion, and

• (iv) Independent (r,ℓ)-Vertex Deletion is polynomial-time reducible to Independent (r+1,ℓ)-Vertex Deletion.

Furthermore, in each of the above reductions the parameter remains unchanged.

Proof

let r, ℓ, and k be three positive integers, and let (G = (V, E), k) be an instance of (r, ℓ)-Vertex Deletion (for claims (i) and (ii)) or of Independent (r, ℓ)-Vertex Deletion (for claims (iii) and (iv)), respectively.

Claim (i)::

Let G ^′ = (V ^′, E ^′) such that V ^′ = V∪Q, with Q a set of r + k+1 vertices, disjoint from V, and E ^′ = E∪{{x, y}:x, y∈Q, x≠y}. That is, G ^′ is the disjoint union of G and a clique of size (r + k+1). Let $\mathcal {A}$ be an algorithm solving (r, ℓ+1)-Vertex Deletion on (G ^′, k) in time f(n, k), for some given function f.

Assume first that S is a solution given by $\mathcal {A}$. Then G ^′−S is an (r, ℓ+1)-graph. Let $\mathcal {R}^{\prime }$ be the set of the r independent sets of G ^′−S and let $\mathcal {L}^{\prime }$ be the set of the ℓ+1 cliques. We claim that at least one clique of $\mathcal {L}^{\prime }$ is completely contained in Q. Indeed, as Q is a clique, then each set in $\mathcal {R}^{\prime }$ constains at most one vertex of Q. As |S|≤k and |Q| = k + r+1, at least one vertex of Q is contained in one of the cliques in $\mathcal {L}^{\prime }$. Let K be such a clique. As there are no edges between the vertices of Q and the other vertices of G ^′, it follows that K⊆Q, as we wanted to prove. Thus, G−(S∩V) is an (r, ℓ)-graph, and therefore |S∩V| is a solution of the required size.

Conversely, if we can find S a solution of (r, ℓ)-Vertex Deletion on (G, k), then S is also a solution of (r, ℓ+1)-Vertex Deletion on (G ^′, k).

Summarizing, (r, ℓ)-Vertex Deletion we can solved in time f(n + r + k+1, k).

Claim (ii)::

As solving (r, ℓ)-Vertex Deletion on (G, k) is equivalent to solving (ℓ, r)-Vertex Deletion on $(\overline {G},k)$, where $\overline {G}$ is the complement of G, we can apply claim (i) on $\overline {G}$. Thus, if (r+1, ℓ)-Vertex Deletion can be solved in time f(n, k), then (r, ℓ)-Vertex Deletion can be solved in time f(n + ℓ + k+1, k).

Claim (iii)::

We follow the proof of claim (i), but in this case, as S is an independent set, it follows that |S∩Q|≤1, so we can use a clique Q of size r+2 instead of r + k+1. Hence, if Independent (r, ℓ+1)-Vertex Deletion can be solved in time f(n, k), then Independent (r, ℓ)-Vertex Deletion can be solved in time f(n + r+2, k).

Claim (iv)::

We follow again the proof of claim (i), but we redefine Q to be an independent set whose vertices are completely adjacent to V. It can be easily checked that both instances are equivalent. Thus, if Independent (r+1, ℓ)-Vertex Deletion can be solved in time f(n, k), then Independent (r, ℓ)-Vertex Deletion can be solved in time f(n + ℓ + k+1, k).

□

3 Well-Known Properties of Iterative Compression

As mentioned in the introduction, iterative compression has been successfully used to obtain efficient algorithms for a number of parameterized problems [11, 15, 23]. In a nutshell, the main idea of this technique is to reduce in FPT-time a problem to solving a so-called disjoint version of it, where we assume that we are given a solution of size almost as small as the desired one, and that allows us to exploit the structure of the graph in order to obtain the actual solution, which is required to be disjoint from the given one. This technique usually applies to hereditary properties.

A graph property $\mathcal {Q}$ is hereditary if any subgraph of a graph that satisfies $\mathcal {Q}$ also satisfies $\mathcal {Q}$. Let $\mathcal {Q}$ be a hereditary graph property. We define the following two problems in order to state two general facts about the technique of iterative compression, which we use in Section 4.

The following two results are well-known (cf. for instance [4]) and commonly assumed when using iterative compression. We include the proofs here for completeness.

Lemma 5

If Disjoint $\mathcal {Q}$ -Vertex Deletion can be solved in FPT-time, then $\mathcal {Q}$ -Vertex Deletion can also be solved in FPT -time.

Proof

Let $\mathcal {A}$ be an FPT algorithm which solves Disjoint $\mathcal {Q}$-Vertex Deletion. Let G = (V, E) be a graph and k be an integer. We want to solve $\mathcal {Q}$-Vertex Deletion on (G, k). Let v ₁,…, v _n be an arbitrary ordering of V. For each i∈{0,…, n}, let V _i denote the subset of vertices {v ₁,…, v _i } and G _i = G[V _i ]. We iterate over i from 1 to n as follows. At the i-th iteration, suppose we have a solution S _i ⊆V _i of $\mathcal {Q}$-Vertex Deletion on (G _i , k). At the next iteration, we can define S _i+1 = S _i ∪{v _i+1}. Note that S _i+1 is a solution of $\mathcal {Q}$-Vertex Deletion on (G _i+1, k+1). If S _i+1 is of size at most k then it is a solution of $\mathcal {Q}$-Vertex Deletion on (G _i+1, k). Assume that S _i+1 is of size exactly k+1. We guess a subset S of S _i+1 and we look for a solution W of $\mathcal {Q}$-Vertex Deletion on (G _i+1, k) that does not contain any element of S. For this, we use algorithm $\mathcal {A}$ on (H,|S|−1, S) with H = G _i+1−(S _i+1∖S). If $\mathcal {A}$ returns a solution W then observe that the set W∪(S _i+1∖S) is a solution of $\mathcal {Q}$-Vertex Deletion on (G _i+1, k). If $\mathcal {A}$ on (H,|S|−1, S) does not return a positive answer for any of the possible guesses of S, then $\mathcal {Q}$-Vertex Deletion on (G _i+1, k) has no solution. Since the property $\mathcal {Q}$ is hereditary, $\mathcal {Q}$-Vertex Deletion on (G, k) has no solution either, and therefore the algorithm returns that there is no solution. Thus, we obtain an algorithm solving $\mathcal {Q}$-Vertex Deletion in FPT-time, as we wanted. □

Corollary 1

If Disjoint $\mathcal {Q}$ -Vertex Deletion can be solved in time c ^k ⋅n ^O(1) for some constant c, then $\mathcal {Q}$ -Vertex Deletion can be solved in time (c+1) ^k ⋅n ^O(1).

Proof

Let us argue about the running time of the algorithm of Lemma 5, assuming Disjoint $\mathcal {Q}$-Vertex Deletion can be solved in time c ^k⋅n ^O(1) for some constant c. The time required to execute $\mathcal {A}$ for every subset S at the i-th iteration is ${\sum }_{i=0}^{k+1} {k+1 \choose i} \cdot c^{i}\cdot n^{O(1)} = (c+1)^{k+1}\cdot n^{O(1)}$. We obtain an algorithm that computes $\mathcal {P}(\mathcal {Q})$ in time (c+1)^k⋅n ^O(1), as we wanted. □

4 (r, ℓ)-Vertex Deletion

By Lemma 4, in this section we may focus on the algorithm for (2,2)-Vertex Deletion. As we use the technique of iterative compression, we need to define and solve the disjoint version of the (2,2)-Vertex Deletion problem. Indeed, if we solve the disjoint version, we just need to apply Corollary 1 in Section 3 to obtain a single-exponential FPT-algorithm for (2,2)-Vertex Deletion.

Theorem 2

Disjoint (2,2)-Vertex Deletion can be solved in time 2.31 ^k ⋅n ^O(1) , and therefore (2,2)-Vertex Deletion can be solved in time 3.31 ^k ⋅n ^O(1).

Proof

Let G be a graph, let k be an integer, and let S⊆V be a set of size at most k+1 such that G−S is a (2,2)-graph. We want to find a set S ^′⊆V∖S such that G−S ^′ is a (2,2)-graph with |S ^′|≤k. As the property of being a (2,2)-graph is hereditary, we can assume that G[S] is a (2,2)-graph. If it is not the case, we clearly have a No-instance and we stop. We guess a (2,2)-partition (R ₀, L ₀) of the graph G[S], and we fix a (2,2)-partition (R _S , L _S ) of the graph G−S. We guess L _sel ⊆R _S and R _sel ⊆L _S , both of size at most 4. We define R ₁ = R _S ∪R _sel ∖L _sel and L ₁ = L _S ∪L _sel ∖R _sel . By Lemma 1, there are at most O(k ⁸⋅n ⁸) choices for R ₀, L ₀, R _sel , and L _sel . For each choice, we look for a solution S ^′ = R ^′∪L ^′ of size at most k such that R ^′⊆R ₁ and L ^′⊆L ₁. A representation of this selection is depicted in Fig. 1. We define L ^′ as a smallest subset of L ₁ such that G[L ₀∪(L ₁∖L ^′)] is a (0,2)-graph. In order to find it, we apply k+1 times the algorithm for Restricted OCT from Theorem 1 to ($\overline {G}[L_{0} \cup L_{1}],L_{1}$, i) for i from 0 to k. If the algorithm does not return a solution with input ($\overline {G}[L_{0} \cup L_{1}],L_{1}$, k) then the choice of R ₀, R _sel , L ₀, and L _sel is wrong, and we move to the next choice. Otherwise, let i ₀ be the smallest value of i for which the algorithm returns a solution, and let L ^′ be this solution. We now look for a set R ^′ of size at most k−i ₀. We find it by applying the algorithm for Restricted OCT to (G[R ₀∪R ₁], R ₁, k−i ₀). If for some guess of R ₀, R _sel , L ₀, and L _sel , the algorithm returns a solution R ^′, then we output S ^′ = R ^′∪L ^′ as our solution. Otherwise we return that there is no solution.

Fig. 1

An (r, ℓ)-partition of G[S] and G−S to solve Disjoint (r, ℓ)-Vertex Deletion in the proof of Theorem 2

Let us now analyze the running time of the algorithm. For each of the O(k ⁸⋅n ⁸) guesses, we find L ^′ by applying the algorithm for Restricted OCT k+1 times, and then we find R ^′ by applying the algorithm for Restricted OCT. By Lemma 2, the claimed running time follows.

Now let us argue about the correctness of the algorithm. If it outputs a set S ^′, then, by construction of the algorithm, this set is a solution of Disjoint (2,2)-Vertex Deletion. Indeed, L ₀∪L ₁∖S is a (0,2)-graph and R ₀∪R ₁∖S is a (2,0)-graph. On the other hand, assume that the instance of Disjoint (2,2)-Vertex Deletion has a solution S ^∗. Let (R ^∗, L ^∗) be a (2,2)-partition of G−S ^∗. Then the solution S ^∗ can be found by the algorithm for the guess R ₀ = S∩R ^∗ and L ₀ = S∩L ^∗. For this choice of R ₀ and L ₀, let (R _S , L _S ) be the fixed (2,2)-partition of G−S. Let G ^∗ = (V ^∗, E ^∗) be the graph G−(S∪S ^∗). Then (R _s ∩V ^∗, L _S ∩V ^∗) and (R ^∗∩V ^∗, L ^∗∩V ^∗) are two (2,2)-partitions of G ^∗. By Lemma 1, we can find L _sel ⊆R _S and R _sel ⊆L _S both of size at most 4 such that L ₁∩V ^∗ = L ^∗∩V ^∗ and R ₁∩V ^∗ = R ^∗∩V ^∗, with R ₁ = R _S ∪R _sel ∖L _sel and L ₁ = L _S ∪L _sel ∖R _sel . For this choice of R ₀, L ₀, R _sel , and L _sel , the solution S ^∗ gives a value $i_{0}^{*}$ such that the algorithm for Restricted OCT applied to ($\overline {G}[L_{0} \cup L_{1}],L_{1}$, $i_{0}^{*}$) and the algorithm for Restricted OCT applied to (G[R ₀∪R ₁], R ₁, $k-i_{0}^{*}$) will both return a solution. Thus, if S ^∗ is a solution of Disjoint (2,2)-Vertex Deletion, then there is at least one choice of R ₀, L ₀, R _sel , and L _sel such that the algorithm returns a solution. □

By combining Lemma 4 and Theorem 2, we obtain the following corollary²

Corollary 2

(2,1)-Vertex Deletion and (1,2)-Vertex Deletion can be solved in time 3.31 ^k ⋅n ^O(1).

It is known that (2,0)-Vertex Deletion, also known as OCT, cannot be solved in time 2^o(k)⋅n ^O(1) unless the ETH fails [13, 19]. By combining this result with Lemma 4, we obtain that the running times of Theorem 2 and Corollary 2 are asymptotically best possible in terms of k under ETH.

Theorem 3

Unless the ETH fails, there is no algorithm running in time 2 ^o(k) ⋅n ^O(1) for solving (2,1)-Vertex Deletion, (1,2)-Vertex Deletion, or (2,2)-Vertex Deletion.

5 Independent (r, ℓ)-Vertex Deletion

In this section we consider Independent (r, ℓ)-Vertex Deletion. Recall that the problem consists in finding a solution of (r, ℓ)-Vertex Deletion that induces an independent set. We first provide in Section 5.1 a (classical) complexity dichotomy for the problem. In Section 5.2 we present FPT-algorithms for the cases (2,1) and (2,2). For the sake of the presentation, we postpone the running time analysis of these algorithms to Section 5.3. As we will see, these running times strongly depend on the running time required by the algorithm of Marx et al. [20] to solve the case (2,0), that is Independent OCT, whose bottleneck is to solve Independent Mincut.

5.1 Easy and Hard Cases

We first deal with the polynomially-solvable cases in Theorem 4 and then we present an NP-hardness reduction for the other cases in Theorem 5.

Theorem 4

Let r∈{0,1} and ℓ∈{0,1,2} be two fixed integers. The Independent (r,ℓ)-Vertex Deletion problem can be solved in polynomial time.

Proof

Let us first consider the case r = 1 and ℓ = 2. One can check in polynomial time whether G is a (2,2)-graph [1]. If it is not, then Independent (1,2)-Vertex Deletion on (G, k) has no solution. So assume that G is a (2,2)-graph. By Lemma 1, there are O(n ⁸) (2,2)-partitions of G that can be computed in polynomial time. We guess a (2,2)-partition (R, L) of G, and we aim at partitioning R into two independent sets R ₁ and R ₂ such that |R ₂|≤k. If Independent Vertex Cover on (G[R], k) has a solution S, then R ₁ = R∖S and R ₂ = S is the partition we want, and we return S. Note that by Lemma 4, Independent Vertex Cover can be solved in linear time on the graph G[R]. If Independent Vertex Cover does not return a solution for any of the guesses of (R, L), we return that our problem has no solution.

Finally, applying Lemma 4 we obtain that Independent (r, ℓ)-Vertex Deletion problem can be solved in polynomial time for every r∈{0,1} and ℓ∈{0,1,2}. □

Theorem 5

Let ℓ∈{0,1,2} be a fixed integer. The Independent (2, ℓ)-Vertex Deletion problem is NP-hard.

Proof

We first prove that Independent (2,0)-Vertex Deletion is NP-hard. We reduce from (2,0)-Vertex Deletion, commonly called Odd Cycle Transversal. The problem is proved to be NP-complete in [17].

Let G = (V, E) be a graph, let k be an integer, and let n = |V|. We want to solve (2,0)-Vertex Deletion on (G, k). We define G ^′ = (V ^′, E ^′), such that $V^{\prime } = V \cup \{{v_{e}^{i}}, {w_{e}^{i}} : e=\{v,w\} \in E, i \in \{0,\ldots , k\}\}$ and $E^{\prime } = \{\{v,{v_{e}^{i}}\}, \{w,{w_{e}^{i}}\} : e=\{v,w\} \in E, i \in \{0 ,\ldots , k\}\} \cup \{\{{v_{e}^{i}},{w_{e}^{i}}\} : v \in V, w \in V, e=\{v,w\} \in E, i \in \{0 ,\ldots , k\}\}$. That is, we replace each edge e = {v, w} of E by n+1 paths $v,{v_{e}^{i}}, {w_{e}^{i}},w$ of length 3, for i∈{0,…, k}. Assume we have a solution S⊆V of (2,0)-Vertex Deletion on (G, k). In G ^′, there is no edge between two vertices of V. So S is also a solution of Independent (2,0)-Vertex Deletion on (G ^′, k). Now, we assume that S is a solution of Independent (2,0)-Vertex Deletion on (G ^′, k). We have that S∩V is also a solution of Independent (2,0)-Vertex Deletion on G ^′. Indeed, assume ${v_{e}^{i}} \in V^{\prime }$ is in S for some e = {v, w}∈E and i∈{0,…, k}; the same analysis will apply to ${w_{e}^{i}}$. If v∈S then ${v_{e}^{i}}$ has only one neighbor in G ^′−{v}, so if G ^′−S is bipartite, then so is $G^{\prime }- (S \setminus \{{v_{e}^{i}}\})$ and thus $S \setminus \{{v_{e}^{i}}\}$ is also a solution. If w∈S, then ${v_{e}^{i}}$ has only two neighbors in G ^′−{w}, namely v and ${w_{e}^{i}}$, with ${w_{e}^{i}}$ being of degree 1 in G ^′−{w}. So if G ^′−S is bipartite, then so is $G^{\prime }- (S \setminus \{{v_{e}^{i}}\})$, and thus $S \setminus \{{v_{e}^{i}}\}$ is also a solution. So assume now that v and w are not in S. Then there exists at least one index i ^′∈{0,…, k} such that $v_{e}^{i^{\prime }}$ and $w_{e}^{i^{\prime }}$ are not in S. This implies that in the bipartite graph G ^′−S, v and w have to be on opposite sides of the bipartition of G ^′−S. We can safely add ${v_{e}^{i}}$ to G−S such that the graph remains bipartite by adding ${v_{e}^{i}}$ to the side of the bipartition containing w. So $S \setminus \{{v_{e}^{i}}\}$ is also a solution.

By deleting all the vertices of the form ${v_{e}^{i}}$ from S, we obtain a set S ^′ such that S ^′⊆V and |S ^′|≤k. As we preserve the property in G ^′ that if {v, w}∈E, with v and w not in S ^′, then v and w should be on opposite sides of the bipartition of G ^′−S ^′, we have that S ^′ is a solution of (2,0)-vertex deletion on G. This concludes the proof.

The NP-hardness of Independent (2,1)-Vertex Deletion and Independent (2,2)-Vertex Deletion follow from the NP-hardness of Independent (2,0)-Vertex Deletion by applying Lemma 4. □

5.2 FPT-Algorithms

We deal with the cases (2,2) and (2,1) in Theorem 6 and Corollary 3, respectively.

Theorem 6

Independent (2,2)-Vertex Deletion is FPT.

Proof

The proof uses similar ideas than the proof of Theorem 2. Let G = (V, E) be a graph and let k be an integer. Let S be a solution of the (2,2)-vertex Deletion problem on (G, k). Theorem 2 gives us in FPT time such a set S, or a report that such a set does not exist. If there is no solution for (2,2)-Vertex Deletion, then Independent (2,2)-Vertex Deletion has no solution either. So we can assume that such a set S exists. Using S, we proceed to construct a solution S ^′ of our problem as follows. We first guess an independent subset I of S. We want to construct a solution S ^′ of Independent (2,2)-Vertex Deletion such that I⊆S ^′ and S ^′∩S = I. If G[S∖I] is not a (2,2)-graph, then our choice of I is wrong. So assume G[S∖I] is a (2,2)-graph. We guess a (2,2)-partition (R ₀, L ₀) of G[S∖I], and we fix a (2,2)-partition (R _S , L _S ) of G−S. We guess L _sel ⊆R _S of size at most 4 and R _sel ⊆L _S of size at most 4. We define R ₁ = R _S ∪R _sel ∖L _sel and L ₁ = L _S ∪L _sel ∖R _sel . By Lemma 1, there are at most O(k ⁸⋅n ⁸) choices for R ₀, L ₀, R _sel , and L _sel . We want to find R ^′⊆R ₁ and L ^′⊆L ₁ such that S ^′ = I∪L ^′∪R ^′. A representation of this selection is depicted in Fig. 2. As we want the solution to induce an independent set, at most two elements of L ₁ are in S ^′, that is, |L ^′|≤2. We guess these at most two vertices that define L ^′ such that L ^′∪I is an independent set and such that G[(L ₀∪L ₁)∖L ^′] is a (0,2)-graph. If it is not the case then our choice is wrong. We now have to find R ^′ of size at most k−|I|−|L ^′|. For this, we apply the algorithm for Restricted Independent OCT on (G[R ₀∪R ₁], D, k−|I|−|L ^′|) with D = {x∈R ₁:∀y∈I∪L ^′,{x, y}∉E}. If it returns a solution R ^′ then we can output the solution S ^′ = I∪L ^′∪R ^′. If it does not return a solution for any of the guesses of I, R ₀, L ₀, R _sel , and L _sel , then we return that there is no solution of Independent (2,2)-Vertex Deletion.

Fig. 2

An (r, ℓ)-partition of G[S∖I] and G−S to solve Independent (r, ℓ)-Vertex Deletion

Now let us argue about the correctness of the algorithm. If it outputs a set S ^′, then, by construction of the algorithm this set is a solution of Independent (2,2)-Vertex Deletion. Indeed, L ₀∪L ₁∖L ^′ is a (0,2)-graph, R ₀∪R ₁∖R ^′ is a (2,0)-graph, and S ^′ is an independent set. Now, assume that our instance of Independent (2,2)-Vertex Deletion has a solution S ^∗. Let (R ^∗, L ^∗) be an (2,2)-partition of G−S ^∗. Then the solution S ^∗ can be found by the algorithm for the guess I = S∩S ^∗, R ₀ = S∩R ^∗, and L ₀ = S∩L ^∗. For this choice of R ₀ and L ₀, let (R _S , L _S ) be the fixed (2,2)-partition of G−S. Let G ^∗ = (V ^∗, E ^∗) be the graph G−(S∪S ^∗). Then (R _s ∩V ^∗, L _S ∩V ^∗) and (R ^∗∩V ^∗, L ^∗∩V ^∗) are two (2,2)-partitions of G ^∗. By Lemma 1, we can find L _sel ⊆R _S and R _sel ⊆L _S both of size at most 4 such that L ₁∩V ^∗ = L ^∗∩V ^∗ and R ₁∩V ^∗ = R ^∗∩V ^∗, with R ₁ = R _S ∪R _sel ∖L _sel and L ₁ = L _S ∪L _sel ∖R _sel . For this choice of R ₀, L ₀, R _sel , and L _sel , the algorithm will define L ^′ = S ^∗∩L ₁. Then the existence of the solution S ^∗ certifies that the algorithm for Restricted Independent OCT on (G[R ₀∪R ₁], D, k−|I|−|L ^′|), with D = {x∈R ₁:∀y∈I∪L ^′,{x, y}∉E}, will return a solution. Thus, if S ^∗ is a solution of Independent (2,2)-Vertex Deletion, then there is at least one choice I, R ₀, L ₀, R _sel , L _sel , and L ^′ such that the algorithm returns a solution. □

By combining Lemma 4 and Theorem 6, we obtain the following corollary.

Corollary 3

Independent (2,1)-Vertex Deletion is FPT, with the same running time as Independent (2,2)-Vertex Deletion.

5.3 Analysis of the Running Time

In this subsection we provide an upper bound on the running times of the FPT-algorithms for Independent (2,2)-Vertex Deletion and Independent (2,1)-Vertex Deletion given by Theorem 6 and Corollary 3, respectively. Note that in these algorithms, the only non-explicit running time is the one of the algorithm for Restricted Independent OCT given by Theorem 1. To obtain this upper bound, we will go through the main ideas of the algorithm of Marx et al. [20] for Independent OCT, and then by using the same tools used in the proof of Lemma 2 we will obtain the same upper bound for the restricted version of Independent OCT.

We need to define the following problem, where an s−t cut in a graph G is a set of vertices C such that s is not connected to t in the graph G−C.

We provide here a sketch of proof of the following simple lemma. We first recall for completeness the definition of treewidth. A tree-decomposition of width w of a graph G = (V, E) is a pair (T, σ), where T is a tree and σ = {B _t :B _t ⊆V, t∈V(T)} such that:

• $\bigcup _{t \in V(T)} B_{t} = V$,

• For every edge {u, v}∈E there is a t∈V(T) such that {u, v}⊆B _t ,

• B _i ∩B _k ⊆B _j for all {i, j, k}⊆V(T) such that j lies on the path i,…, k in T, and

• maxi∈V(T)|B _t | = w+1.

The sets B _t are called bags. The treewidth of G, denoted by tw(G), is the smallest integer w such that there is a tree-decomposition of G of width w. An optimal tree-decomposition is a tree-decomposition of width tw(G).

Lemma 6

Independent Mincut can be solved in time 3 ^tw ⋅n ^O(1) , where tw stands for the treewidth of the input graph.

Proof

(Sketch) For each bag B of the tree-decomposition, we store all quadruples (S, T, D, ℓ) such that we have already found a cut C ^′ of size at most ℓ in the explored graph such that B∩C ^′ = D, such that there is no edge between S and T, and such that s∈B if and only if s∈S and t∈B if and only if t∈T . There are at most 3^tw⋅k such quadruples, and so the lemma follows. □

Note that Lemma 6 is a special case of the problems covered by the result of Pilipczuk [22], who proves that such problems can be solved in time c ^tw⋅n ^O(1) for some constant c>0. We also need the following result, where the key idea is to obtain an equivalent graph whose treewidth is bounded by a function of k.

Theorem 7 (Marx et al. 20)

Let G=(V,E) be a graph, let S⊆V(G), and let k be an integer. Let C be the set of all vertices of G participating in a minimal s−t cut of size at most k for some s,t∈S. Then there is an algorithm running in time $2^{O(k^{2})} \cdot |S|^{2} \cdot n^{O(1)}$ that computes a graph G ^∗ and a tree-decomposition of G ^∗ of width at most $2^{O(k^{2})} \cdot |S|^{2}$ having the following properties:

• C∪S⊆V(G ^∗),

• For every s,t∈S, a set K⊆V(G ^∗ ) with |K|≤k is a minimal s−t cut of G ^∗ if and only if K⊆C∪S and K is a minimal s−t cut of G,

• The treewidth of G ^∗ is at most $2^{O(k^{2})}\cdot |S|^{2}$ , and

• For any K⊆C, G ^∗ [K] is isomorphic to G[K].

Lemma 7

Restricted Independent Mincut can be solved in time $2^{2^{O(k^{2})}}\cdot n^{O(1)}$.

Proof

We first deal with Independent Mincut. Let G = (V, E) be a graph and k be an integer. Let G ^∗ be the graph satisfying the requirements of Theorem 7 for S = {s, t}. Following the proof of [20, Theorem 3.1], it follows that (G, s, t, k) has a solution of Independent Mincut if and only if (G ^∗, s, t, k) has one. We can now apply Lemma 6, and solve Independent Mincut on $(G^{*},s,t,k)$ in time $3^{\textbf {tw}(G^{*})}\cdot n^{O(1)}$. By Theorem 7, $\textbf {tw}(G^{*}) = 2^{O(k^{2})}$ and the lemma follows.

Finally, note that the restricted version of Independent Mincut can be solved within the same running time by making enough copies of each “undesired” vertex, as in the proof of Lemma 2. □

Theorem 8

Restricted Independent OCT can be solved in time $2^{2^{O(k^{2})}}\cdot n^{O(1)}$.

Proof

In the following, we give a proof for Independent OCT. In order to obtain the algorithm for Restricted Independent OCT, we just take again, as we did for Restricted OCT in Lemma 2, a larger instance by making enough copies of each “undesired” vertex, and apply Independent OCT.

Let G = (V, E) be a graph and let X be a solution of OCT on (G, k), which we can assume to exist. Let (S ₁, S ₂) be a partition of G−X into two independent sets. We define an auxiliary graph G ^′ = (V ^′, E ^′) as defined in [23]. So we have V ^′ = (V∖X)∪{x ₁, x ₂:x∈X} and E ^′ = {{v, w}∈E:v, w∈V∖X}∪{{y, x _3−i }:y∈S _i , x∈X, i∈{1,2},{x, y}∈E}∪{{x ₁, y ₂},{x ₂, y ₁}:x, y∈X,{x, y}∈E}. Given Y⊆X, we say that a partition of Y ^′ = {y ₁, y ₂:y∈Y} into two sets (Y _A , Y _B ) is valid if for all y∈Y, exactly one of y ₁, y ₂ is in Y _A . We let S = S ₁∪S ₂.

To continue, we need the next reformulation of [23, Lemma 1] and its proof.

Claim 1

There is an independent odd cycle transversal Z of size at most k in G if and only if there exists Y⊆X and a valid partition (Y _A ,Y _B ) of Y ^′ such that there is an independent mincut C⊆S that separates Y _A from Y _B in G ^′ and such that Z=C∪(X∖Y) is an independent set of size at most k in G.

Proof

(⇒) Let Z be an independent odd cycle transversal of size at most k in G. We assume that Z is of minimum size and that its removal produces two independent sets ${S^{Z}_{1}}$ and ${S^{Z}_{2}}$. Let K = Z∩X, let J = Z∖K, and let Y = X∖K. We define (Y _A , Y _B ), a valid partition of Y ^′ such that $Y_{A} = \{y_{1} : y \in Y \cap {S_{1}^{Z}}\} \cup \{y_{2} : y \in Y \cap {S_{2}^{Z}}\}$ and $Y_{B} = \{y_{2} : y \in Y \cap {S_{1}^{Z}}\} \cup \{y_{1} : y \in Y \cap {S_{2}^{Z}}\}$.

We claim that J is a cutset of G ^′[Y _A ∪Y _B ∪S] separating Y _A from Y _B . Take a minimal path P from Y _A to Y _B in G ^′[(Y _A ∪Y _B ∪S)∖J]. Let u and v be the two endpoints of P. By minimality of P, P∩(Y _A ∪Y _B )={u, v}. We assume without loss of generality that either $u,v \in Y \cap {S_{1}^{Z}}$ or $u \in Y \cap {S_{1}^{Z}}$ and $v \in Y \cap {S_{2}^{Z}}$. In the former case, we have that u = y ₁ for some y∈Y and v = w ₂ for some w∈Y. As, by construction, G ^′[Y _A ∪Y _B ∪S] is bipartite and y ₁ and w ₂ are on opposite sides of the bipartition of G ^′[(Y _A ∪Y _B ∪S)∖J], necessarily P has odd size. But as $u,v \in {S_{1}^{Z}}$, u and v are on the same side of the bipartition of G−Z, and so of G ^′[(Y _A ∪Y _B ∪S)∖J] as well. Thus P should have even size, a contradiction. We obtain a similar contradiction in the latter case.

(⇐) Under the condition of Claim 1, Z is an independent set, and we need to prove that it is an odd cycle transversal as well. Assume that there is an odd cycle O in G−Z. Then by definition of X, O intersects X at least once. Let O ⁰,…, O ^m−1 be the m times O intersects X and we define O ^m = O ⁰. We have that O ⁱ≠O ^j for all i<j<m. For each i∈{0,…, m−1}, let P _i be the path from O ⁱ to O ⁱ⁺¹. As O never intersects Z, then in G ^′ the path P _i never goes from Y _A to Y _B . It means that for each i such that P _i is of even size, ${O^{i}_{1}}$ and $O^{i+1}_{1}$ are in the same set Y _A or Y _B , and for each i such that P _i is of odd size, ${O^{i}_{1}}$ and $O^{i+1}_{2}$ are in the same set Y _A or Y _B . But O is an odd cycle, so there is an odd number of paths P _i such that P _i is of odd size. We deduce that such an odd cycle O cannot exist, implying that Z is an independent odd cycle transversal. □

We now apply the algorithm for Independent Mincut for all Y⊆X and all valid partitions (Y _A , Y _B ) of Y ^′. Note that we need to consider a restricted version of Independent Mincut because we do not want the neighborhood of X∖Y to be in the solution. By Claim 1, if we obtain a solution, then we have found our independent odd cycle transversal, and otherwise we can safely return that such a set does not exist. The claimed running time follows from Lemma 7. □

By using the same argument of Lemma 2, we obtain the following corollary.

Corollary 4

Restricted Independent OCT can be solved in time $2^{2^{O(k^{2})}}\cdot n^{O(1)}$ , and therefore Independent (r,ℓ)-Vertex Deletion can also be solved in time $2^{2^{O(k^{2})}}\cdot n^{O(1)}$ for r=2 and ℓ∈{0,1,2}.

Note that the previous results would be automatically improved if one could find a faster algorithm for Independent Mincut.