Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized

Abstract

Let $\mathrm{\Pi }$ be a family of graphs. In the classical $\mathrm{\Pi }$-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that $G-S$ is in $\mathrm{\Pi }$. In this paper, we introduce the conflict free version of this classical problem, namely Conflict Free $\mathrm{\Pi }$-Vertex Deletion (CF-$\mathrm{\Pi }$-VD), and study these problems from the viewpoint of classical and parameterized complexity. In the CF-$\mathrm{\Pi }$-VD problem, given two graphs G and H on the same vertex set and a positive integer k, the objective is to determine whether there exists a set $S\subseteq V(G)$, of size at most k, such that $G-S$ is in $\mathrm{\Pi }$ and H[S] is edgeless. Initiating a systematic study of these problems is one of the main conceptual contribution of this work. We obtain several results on the conflict free version of several classical problems. Our first result shows that if $\mathrm{\Pi }$ is characterized by a finite family of forbidden induced subgraphs then CF-$\mathrm{\Pi }$-VD is Fixed Parameter Tractable (FPT). Furthermore, we obtain improved algorithms for conflict free version of several well studied problems. Next, we show that if $\mathrm{\Pi }$ is characterized by a “well-behaved” infinite family of forbidden induced subgraphs, then CF-$\mathrm{\Pi }$-VD is W[1]-hard. Motivated by this hardness result, we consider the parameterized complexity of CF-$\mathrm{\Pi }$-VD when H is restricted to well studied families of graphs. In particular, we show that the conflict free versions of several well-known problems such as Feedback Vertex Set, Odd Cycle Transversal, Chordal Vertex Deletion and Interval Vertex Deletion are FPT when H belongs to the families of d-degenerate graphs and nowhere dense graphs.

1 Introduction

Graph-modification by either deleting vertices, or deleting edges, or adding edges such that the resulting graph satisfies certain properties or becomes a member of some well-understood graph class is one of the basic problems in graph theory and computer science. However, most of these problems are NP-complete [18, 29], and therefore they have been extensively studied in various algorithmic paradigms that are meant to cope with NP-completeness [13, 14, 20], such as restricted classes of inputs, approximation algorithms and parameterized complexity. This paper introduces a new variant of these classical problems, called the conflict free version, and studies them from viewpoint of classical and parameterized complexity.

In the past, the conflict free versions of some classical problems have been studied, e.g. for Shortest Path [16], Maximum Flow [24, 25], Knapsack [26], Bin Packing [11], Scheduling [12], Maximum Matching and Minimum Weight Spanning Tree [9, 10]. It is interesting to note that some of these problems are NP-hard even when their non-conflicting version is polynomial time solvable. The study of conflict free problems has also been recently initiated in computational geometry motivated by various applications (see [2,3,4]). Motivated by these works, we initiate the study of the conflict free versions of several well studied vertex deletion problems in parameterized complexity. This is the main conceptual contribution of this paper. A typical parameterized vertex deletion problem on graphs is of the following form. Let $\mathrm{\Pi }$ be a family of graphs (or property) – such as edgeless graphs, forests, cluster graphs, chordal graphs, interval graphs, bipartite graphs, split graphs or planar graphs. The vertex deletion problem corresponding to $\mathrm{\Pi }$ is formally stated as follows.

That is, given a graph G, can we delete at most k vertices such that the resulting graph belongs to $\mathrm{\Pi }$? The set S is called $\mathrm \Pi$-deletion set. An algorithm for $\mathrm{\Pi }$-Vertex Deletion that runs in time $f(k)\cdot |V(G)|^{{\mathcal O}(1)}$ is called fixed-parameter tractable (FPT) algorithm and the problem itself is said to be FPT. We refer to [8] for more details on parameterized complexity. The study of parameterized graph deletion problems together with their various restrictions and generalizations has been an active area of research recently.

To formulate the conflict free version of these classical problems, let us begin with an example. Consider Set Cover, that has the following conflict free version. We are given a universe $\mathcal U$ and a family $\mathcal S$ of subsets of $\mathcal {U}$, a positive integer k and a graph H (with $V(H)=\mathcal{S}$). The objective is to check whether there exists a $\mathcal{S}'\subset \mathcal S$ of size at most k whose union is $\mathcal U$ and $H[\mathcal{S}']$ is edgeless. Now, we may similarly combine the classical vertex deletion problems on graphs, with the conflict free model described in [2,3,4] and arrive at the following generic conflict free problem. Let $\mathrm{\Pi }$ be a family of graphs. The conflict free vertex deletion problem corresponding to $\mathrm{\Pi }$ is formally stated as follows.

We define CF-$\mathrm{\Pi }$-VD for hypergraphs and directed graphs, appropriately. In this paper, we focus on CF-$\mathrm{\Pi }$-VD problems corresponding to several well studied problems in parameterized complexity, namely Vertex Cover, d-Hitting Set, Split Vertex Deletion, Feedback Vertex Set in Tournaments (FVST) and Feedback Vertex Set (FVS). Observe that when H is an edgeless graph, CF-$\mathrm{\Pi }$-VD is same as $\mathrm{\Pi }$-Vertex Deletion and thus it generalizes the non-conflict free version of the problem. Furthermore, when H is same as G it corresponds to independent version of these problems which are also well studied, such as Independent Feedback Vertex Set [19, 23]. Thus, CF-$\mathrm{\Pi }$-VD is a generalization of well studied problems in algorithms and complexity.

Our Results. Apart from introducing an interesting family of problems, we obtain the following results in the realm of parameterized and classical complexity. We note that several of these results are in sharp contrast to the non-conflict version of the same problem.

A graph property $\mathrm{\Pi }$ is a set of graphs, and a graph in $\mathrm{\Pi }$ is called a $\mathrm{\Pi }$-graph. We say that $\mathrm{\Pi }$ is hereditary if for any graph G in $\mathrm{\Pi }$, every induced subgraph of G is also in $\mathrm{\Pi }$. A graph property $\mathrm{\Pi }$ has a forbidden set characterization if there is a set $\mathcal F$ of graphs such that a graph is a $\mathrm{\Pi }$-graph if and only if it does not contain any graph in $\mathcal F$ as an induced subgraph, and further, it has a finite forbidden characterization if $\mathcal F$ is a finite set. We study the complexity of CF-$\mathrm{\Pi }$-VD based on the forbidden set of the property $\mathrm{\Pi }$.

Graph properties with finite forbidden characterization. The starting point of our results is a generic result by Cai [5] about graph properties which have a finite forbidden characterization. We show an analogous result for CF-$\mathrm{\Pi }$-VD. In particular we show that CF-$\mathrm{\Pi }$-VD is FPT whenever $\mathrm{\Pi }$ has a finite forbidden set characterization. Indeed, we show that this problem admits an algorithm with running time ${\mathcal O}(\alpha ^k \cdot n \cdot T(m, n))$, where T(m, n) is time to recognize a graph in $\mathrm{\Pi }$ and $\alpha$ is the size of largest graph in the finite forbidden set $\mathcal F$. Furthermore, it also admits a kernel with $\mathcal {O}(\alpha ^2 \alpha !k^{\alpha })$ vertices.

Next, we study the conflict free version of several well-studied cases of $\mathrm{\Pi }$-Vertex Deletion, where $\mathrm{\Pi }$ is characterized by the finite family of forbidden induced subgraphs. These results improve upon the generic result stated above.

• 1. Conflict Free Vertex Cover (CF-VC) admits a 2k-vertex kernel, a factor 2-approximation algorithm, an ${\mathcal O}^{\star }(1.2738^{k})$ FPT algorithm¹ and a ${\mathcal O}^{\star }(1.1996^{n})$ exact algorithm. Further, CF-VC is NP-complete even when graph G is of degree at most 2. This holds even when G is disjoint union of $P_3$ ($P_\ell$ denotes path on $\ell$ vertices). Furthermore, CF-VC is polynomial time solvable when G has degree at most one, or when both G and H have a perfect matching.

• 2. The Conflict Free $d$-Hitting Set ($d$-CF-HS) problem can be solved in ${\mathcal O}^{\star }(((d-1)+.2738)^k)={\mathcal O}^{\star }((d-0.7262)^k)$ time.

• 3. Conflict Free Split Vertex Deletion (CF-SVD) can be solved in ${\mathcal O}^\star (1.2738^k k^{\mathcal {O}(\log k)})$ time and polynomial space.

• 4. Conflict Free Feedback Vertex Set in Tournaments (CF-FVST) can be solved in ${\mathcal O}^{\star }(2^k)$ time.

Let us note that given an instance (G, H) of CF-VC, we can test whether there exists a conflict free vertex cover (of any size) in polynomial time. However, one can show that testing whether there exists a conflict free feedback vertex set is NP-complete.

Graph properties without finite forbidden characterization. Next, we consider those graph properties that are not characterized by a finite family of forbidden induced subgraphs. We show that if $\mathrm{\Pi }$ is characterized by a “well-behaved” infinite family of forbidden induced subgraphs, then CF-$\mathrm{\Pi }$-VD is W[1]-hard. In particular, we show that Conflict Free Feedback Vertex Set (CF-FVS) is W[1]-hard even when G is disjoint union of cycles. A similar result holds for Conflict Free Odd Cycle Transversal (CF-OCT), Conflict Free Chordal Vertex Deletion (CF-CVD) and Conflict Free Interval Vertex Deletion (CF-IVD).

This motivates us to restrict the families of conflict graphs. We show that conflict free versions of several well-known problems such as Feedback Vertex Set, Odd Cycle Transversal, Chordal Vertex Deletion and Interval Vertex Deletion are FPT when H belongs to the family of d-degenerate graphs, or nowhere dense graphs. It is worth noting that the families of d-degenerate graphs and nowhere dense graphs include trees, graphs of bounded degree, planar graphs, graphs that exclude a fixed graph H as a minor (or a topological minor) and graphs of bounded expansion. These algorithms are based on the notion of “k-independence covering family” introduced in [19].

Due to space constraints, basic graph theoretic preliminaries and proofs of results marked $(\star )$ have been omitted. These will appear in the full version of the paper.

2 Conflict Free Version of Properties with Forbidden Set Characterizations

2.1 Properties with Finite Forbidden Set Characterizations

In this subsection, we study the CF-Finite $\mathrm{\Pi }$-VD problem when $\mathrm{\Pi }$ is hereditary and admits a finite forbidden set characterization.

FPT Algorithm for CF-Finite $\mathrm{\Pi }$-VD. Let $\mathcal F$ be the finite forbidden set corresponding to the property $\mathrm{\Pi }$. Cai [5] showed that the Finite $\Pi$-D is FPT. That is, given a graph G, testing whether there exists a set $S\subseteq V(G)$ of size at most k such that $G-S$ is a $\mathrm{\Pi }$-graph is FPT. The algorithm works as follows. It starts by finding a forbidden vertex set X in G; among which we know that at least one vertex must go in the solution set S. Therefore, we branch on this collection of vertices, and for each vertex $v\in X$, we recursively apply the algorithm to solve the instance $(G-v, k-1)$. If one of these branches returns a $\mathrm{\Pi }$-deletion set S, then clearly $S\cup \{v\}$ is of size at most k and it is a $\mathrm{\Pi }$-deletion set in G. Else, we return that the given instance is a no instance. At every recursive call we decrease the parameter by 1, and thus the height of the search tree does not exceed k. At every step, we branch in at most $\alpha$ subproblems; where $\alpha$ is the size of largest graph in $\mathcal F$. Hence the number of nodes in the search tree does not exceed $\alpha ^k$. Observe that, the algorithm actually enumerates all the minimal $\mathrm{\Pi }$-deletion sets of size at most k. Thus for CF-Finite $\mathrm{\Pi }$-VD, all we need to do in addition, is to check whether H[S] is edgeless or not. We will also need the following result for the above algorithm.

Proposition 1

[5, Theorem 1]. For any hereditary property $\mathrm{\Pi }$, if $\mathrm{\Pi }$ is recognizable in time T(m, n), then for any graph G that is not a $\mathrm{\Pi }$-graph, a minimal forbidden induced subgraph of $\mathrm{\Pi }$ in G can be found in ${\mathcal O}(n \cdot T(m, n))$ time.

With the above theorem in hand, we obtain the following theorem.

Theorem 1

CF-Finite $\mathrm{\Pi }$-VD is FPT and admits an algorithm with running time ${\mathcal O}(\alpha ^k \cdot n \cdot T(m, n))$, where T(m, n) is the time to recognize a graph in $\mathrm{\Pi }$ and $\alpha$ is the size of largest graph in the finite forbidden set $\mathcal F$.

We also obtain a polynomial kernel with at most $\mathcal {O}(\alpha ^2 \alpha !k^{\alpha })$ vertices for CF-Finite $\mathrm{\Pi }$-VD. The details will appear in the full version of the paper.

2.2 Properties that Do Not Admit Finite Forbidden Characterization

It is well know that a property $\mathrm{\Pi }$ is hereditary if and only if $\mathrm{\Pi }$ admits a forbidden set characterization [5]. Let $\mathcal F$ denote the forbidden set corresponding to $\mathrm{\Pi }$. Following the previous section, a natural question that arises is what happens when $\mathcal F$ is infinite. We call the corresponding vertex deletion problem as Conflict Free $\mathrm{\Pi }$-Vertex Deletion (CF-$\mathrm{\Pi }$-VD). For example, suppose that $\mathrm{\Pi }$ is a family of forests, or chordal graphs, or interval graphs, or bipartite graphs. Then the corresponding classical problems of $\mathrm{\Pi }$-Vertex Deletion ($\mathrm{\Pi }$-VD) problems are known as Feedback Vertex Set (FVS), Chordal Vertex Deletion (CVD), Interval Vertex Deletion (IVD) and Odd Cycle Transversal (OCT) and these problems are known to be FPT [6, 17, 21, 27]. However, we will show now that conflict free version of these problems is W[1]-hard. Indeed, Conflict Free Feedback Vertex Set (CF-FVS) is W[1]-hard even when G is disjoint union of cycles.

Towards this, we present a parameter preserving reduction from the W[1]-hard Multicolored Independent Set (MCIS) problem to CF-FVS. See [8] for further details on the notion of W[1]-hardness and for the fact that MCIS is W[1]-hard. In MCIS, given a graph G, an integer k, and a partition of V(G) into k sets, say $V_1,\dots ,V_k$, the objective is to check whether there exists a set $X\subseteq V(G)$ such that it contains exactly one element from every set $V_i$ and is an independent set in G. We call such an independent set as multicolored independent set.

Theorem 2

${\varvec{(\star ).}}$ CF-FVS is $\mathsf{W[1]}$-hard.

Proof

(Sketch). Let $(G,(V_1,\cdots ,V_k),k)$ be an instance of MCIS. Given this, we construct an instance $(G',H,k)$ of CF-FVS as follows. The vertices of $G'$ and H are same as V(G). For each set $V_i$, we construct a cycle $C_{|V_i|}$ in $G'$ ($C_\ell$ denotes cycle on $\ell$ vertices) on vertex set $V_i$ in $G'$. The graph H is identical to graph G. Now we can show that G has a multicolored independent set of size k, if and only if, $(G',H)$ has a conflict free feedback vertex set of size k.    $\square$

The proof of Theorem 2 requires nothing specific about CF-FVS, except that G is a disjoint union of forbidden sets where each forbidden set is identified with a color class $V_i$. If $\mathcal F$ is infinite and well behaved in the following sense: given an integer n we can output a forbidden set F of size polynomial in n (in fact size $f(k)\cdot n^{{\mathcal O}(1)}$ will also work for our purpose) in time $\tau (k)\cdot n^{{\mathcal O}(1)}$, then we can mimic the proof of Theorem 2 and show that the corresponding CF-$\mathrm{\Pi }$-VD is $\mathsf{W[1]}$-hard. Let us note that in certain cases, e.g. for bipartite graphs where the family of forbidden subgraphs are odd cycles, we may need to augment a color class $V_i$ with additional vertices to obtain a forbidden set in $\mathcal F$ in the graph G. This is easily handled by making the additional vertices adjacent to all vertices in the conflict graph H, which ensures that they cannot be selected in any solution of cardinality greater than one. In particular, this holds for $\mathrm{\Pi }$ being the family of chordal graphs, or interval graphs, or bipartite graphs. Here, f and $\tau$ are computable functions.

2.3 Results on Properties Without Finite Forbidden Characterization

In Sect. 2.2, we have shown that if $\mathcal F$ is infinite, CF-$\mathrm{\Pi }$-VD is W[1]-hard in general, even though the corresponding classical problem is FPT, e.g. CF-FVS, CF-OCT, CF-CVD etc. In light of this, a natural question that arises is what happens if H is restricted to certain graph classes. In this section, we show that CF-$\mathrm{\Pi }$-VD is FPT when H is restricted to the class of d-degenerate graphs or no-where dense graphs.

The degeneracy of an n-vertex graph $G^\star$ is defined as the minimum integer d such that there exists an ordering where every vertex v has at most d neighbors u for which $\sigma (u)>\sigma (v)$. Such an ordering $\sigma$ is called a d-degeneracy sequence of graph $G^\star$. We fix one such sequence, and then for any vertex $v \in V(G^*)$, we define its forward and backward neighbors in $G^*$ with respect to this ordering. Our algorithm is based on the construction of a k-independence covering family of a graph, using the Independence Covering Lemma of [19]. For a graph $H^\star$ and an integer k, a k-independence covering family, denoted by $\mathscr {F}(H^\star ,k)$, is a family of independent sets of graph $H^\star$ such that for any independent set X in $H^\star$ of size at most k there exists a set Y in $\mathscr {F}(H^\star ,k)$ such that $X\subseteq Y$. We will use the following propositions to construct a k-independence covering family for H.

Proposition 2

[19, Lemma 1.1]. There exists a linear time randomized algorithm, that given as input a d-degenerate graph $H^\star$ and $k\in \mathbb {N}$, outputs an independent set Y, such that for every independent set X in $H^\star$ of size at most k the probability that X is a subset of Y is at least $(\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) k(d+1))^{-1}$.

Proposition 3

[19, Lemmas 3.2 and 3.3]. There are two deterministic algorithms, that given a d-degenerate graph $H^\star$ and $k\in \mathbb {N}$, outputs independence covering families $\mathscr {F}_1(H^\star ,k)$ of size at most $\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) 2^{o(k(d+1))}\log n$ and $\mathscr {F}_2(H^\star ,k)$ of size at most $\left( {\begin{array}{c}k^2{(d+1)}^2\\ k\end{array}}\right) (k(d+1))^{\mathcal {O}(1)}\log n$ respectively. These algorithms run in time ${\mathcal O}(|\mathscr {F}_1(H^\star ,k)|(n+m))$ and ${\mathcal O}(|\mathscr {F}_1(H^\star ,k)|(n+m))$, respectively.

Now we present our algorithm for CF-$\mathrm{\Pi }$-VD problems, when the conflict graph is d-degenerate. The algorithm is based on the observation that, given a independence covering family of conflict graph, the conflict free solution of the problem lies inside one of the sets in this family. By construction, each set in this family is an independent set in H, and therefore the problem of finding a solution to the given instance of CF-$\mathrm{\Pi }$-VD boils down to finding a solution of $\mathrm{\Pi }$-VD in the graph G that also lies in a chosen set in the family. In particular, it reduces to solving the following annotated version of CF-$\mathrm{\Pi }$-VD.

Theorem 3

${\varvec{(\star ).}}$ Let $\varPi$ be a property such that A-$\mathrm{\Pi }$-VD admits an algorithm with running time $\tau (k)n^{{\mathcal O}(1)}$. Then CF-$\mathrm{\Pi }$-VD admits a randomized algorithm with running time $\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) k(d+1)\tau (k) n^{{\mathcal O}(1)}$, and a deterministic algorithm with running time $\min \Big \{\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) 2^{o(k(d+1))} \log n$, $\left( {\begin{array}{c}k^2{(d+1)}^2\\ k\end{array}}\right) (k(d+1))^{\mathcal {O}(1)} \log n \Big \} \tau (k) n^{{\mathcal O}(1)},$ on the family of conflict graphs that are d-degenerate.

Proof

(Sketch). Given an instance (G, H, k) of CF-$\mathrm{\Pi }$-VD we do as follows. Run the following two step procedure $(\left( {\begin{array}{c}k(1+d)\\ k\end{array}}\right) k(d+1))$ times.

• 1. Run the algorithm in Proposition 2 on (H, k), and obtain the set Y.

• 2. Solve A-$\mathrm{\Pi }$-VD on the instance (G, H, Y, k) using the algorithm running in time $\tau (k)n^{{\mathcal O}(1)}$.

The algorithm will output yes if, Step 2 returns yes at least once, else algorithm returns no. Now we prove the correctness of algorithm. Since in Step 1, the output set Y is an independent set in conflict graph H, if the algorithm returns yes then the input instance is a yes instance. Now suppose that the input instance is a yes instance and X be its solution. By Proposition 2, probability that $X\subseteq Y$ is at least $p=(\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) k(d+1))^{-1}$. We repeat the procedure 1/p times, so the probability that in all executions $X\nsubseteq Y$ is at most $(1-p)^{1/p}\le 1/e$. Therefore algorithm returns yes with probability at least $1-1/e$. Running time follows from Proposition 2 and the assumed running time of the algorithm for A-$\mathrm{\Pi }$-VD.

Now we give the deterministic algorithm. Given an instance (G, H, k) of CF-$\mathrm{\Pi }$-VD the algorithm works as follows. Algorithm first constructs k-independence covering family $\mathscr {F}(H,k)$ of conflict graph H, using Proposition 3. Now for all sets $Y \in \mathscr {F}(H,k)$, algorithm solve A-$\mathrm{\Pi }$-VD on instance (G, H, Y, k) using the algorithm assumed in the statement of the theorem. The algorithm outputs yes if for some set $Y \in \mathscr {F}(H,k)$, the A-$\mathrm{\Pi }$-VD returns yes, otherwise returns no. The correctness of algorithm follows from the definition of k-independence covering family. The running time follows from Proposition 3, and the assumed running time of the algorithm for A-$\mathrm{\Pi }$-VD. This completes the proof.    $\square$

The above theorem naturally leads to the question that when can A-$\mathrm{\Pi }$-VD be FPT. We give an affirmative answer for several cases when the integer weighted version (W-$\mathrm{\Pi }$-VD) of the corresponding $\mathrm{\Pi }$-VD is FPT.

Lemma 1

Let $\varPi$ be a property such that W-$\mathrm{\Pi }$-VD admits an algorithm with running time $\gamma (k)n^{{\mathcal O}(1)}$. Then A-$\mathrm{\Pi }$-VD also admits an algorithm with running time $\gamma (k)n^{{\mathcal O}(1)}$.

Proof

We give a polynomial time reduction from A-$\mathrm{\Pi }$-VD to W-$\mathrm{\Pi }$-VD. Towards this given an instance (G, Y, k) of A-$\mathrm{\Pi }$-VD we construct an instance $(G',w,k)$ of W-$\mathrm{\Pi }$-VD as follows. We take graph $G'$ identical to graph G. We define weight function w as follows. We assign $w(v)=k+1$ if $v\in V(G)\setminus Y$, otherwise $w(v)=1$. We now show that (G, Y, k) is a yes instance of A-$\mathrm{\Pi }$-VD if and only if $(G',w,k)$ is a yes instance of W-$\mathrm{\Pi }$-VD. Let $S\subseteq Y$ be a minimal vertex subset of size at most k such that $G-S$ is a $\varPi$-graph, then we claim that S is also solution $G'$. Since $S\subseteq Y$, we have that $w(v)=1$ for all vertices in S. Therefore, the weight of S is at most k. Since $G'$ is same as G, $G'-S$ is also a $\varPi$-graph.

Conversely, let $S'$ be a set of weight at most k such that $G'-S'$ is a $\varPi$-graph. We claim that $S'$ is a solution of G. Note that all the vertices in $V(G')\setminus Y$ have weight $k+1$, therefore $S'\subseteq Y$. Since each vertex in $S'$ has weight one, $|S'|\le k$. Furthermore, since graph G is identical to graph $G'$, we have that $G-S'$ is a $\varPi$-graph. This completes the proof.    $\square$

It is known that Weighted Feedback Vertex Set (WFVS) can be solved in time ${\mathcal O}(3.618^kn^{{\mathcal O}(1)})$ [1] and thus by Lemma 1 we have that A-FVS can be solved in time ${\mathcal O}(3.618^kn^{{\mathcal O}(1)})$. Now by applying Theorem 3 we get the following.

Corollary 1

CF-FVS either admits a randomized algorithm with running time $\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) k(d+1)\tau (k) n^{{\mathcal O}(1)}$ or a deterministic algorithm with running time $\min \big \{ \left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) 2^{o(k(d+1))} \log n, \left( {\begin{array}{c}k^2{(d+1)}^2\\ k\end{array}}\right) (k(d+1))^{\mathcal {O}(1)} \log n \big \} \tau (k) n^{{\mathcal O}(1)},$ on the family of conflict graphs that are d-degenerate. Here, $\tau (k)=3.618^k$.

We may similarly obtain the results for Conflict Free Odd Cycle Transversal, Conflict Free Chordal Vertex Deletion and Conflict Free Interval Vertex Deletion.

Corollary 2

${\varvec{(\star ).}}$ CF-OCT, CF-CVD and CF-IVD admit a randomized algorithm with running time $\left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) k(d+1) \tau (k) n^{{\mathcal O}(1)}$, and a deterministic algorithm with running time $\min \left\{ \left( {\begin{array}{c}k(d+1)\\ k\end{array}}\right) 2^{o(k(d+1))} \log n, \left( {\begin{array}{c}k^2{(d+1)}^2\\ k\end{array}}\right) (k(d+1))^{\mathcal {O}(1)} \log n \right\} \tau (k) n^{{\mathcal O}(1)},$ on the family of conflict graphs that are d-degenerate. Here, $\tau (k)$ is $4^kk^6$, $2^{{\mathcal O}(k\log k)}$ and $8^k$ for each of these problems respectively.

The above results can be also extended to the class of nowhere dense graphs. The details will appear in the full version of the paper.

3 Well Studied Special Cases of CF-Finite $\mathrm{\Pi }$-VD

We can obtain improved algorithms for the conflict free version of several well-studied cases of $\Pi$-Vertex Deletion whenever $\Pi$ is characterized by the finite family of forbidden induced subgraphs. In this section, we give improved algorithms for Conflict Free Vertex Cover, Conflict Free $d$-Hitting Set, Conflict Free Split Vertex Deletion and Conflict Free Feedback Vertex Set in Tournaments.

3.1 Conflict Free Vertex Cover

In this section, we study the conflict free version of the classical Vertex Cover, namely Conflict Free Vertex Cover (CF-VC). In particular, we study the following problem.

We call the set X a conflict free vertex cover. Next, we show that CF-VC can be solved as fast as the classical Vertex Cover problem. Towards this, we present a polynomial time reduction from CF-VC to Min Ones 2-SAT which preserves both parameter k and number of variables n. In Min Ones 2-SAT, we are given a formula $\varPhi$ such that every clause consists of at most two literals and an integer k, and the aim is to check whether there exists a satisfying assignment $\tau$ of $\varPhi$ where at most k variables are set to 1. Given a formula $\varPhi$, let $V(\varPhi )$ and $C(\varPhi )$ denote the set of variables and clauses of $\varPhi$, respectively.

Lemma 2

There is a polynomial time parameter preserving reduction from CF-VC to Min Ones 2-SAT. That is, given an instance (G, H, k) of CF-VC, in polynomial time, we can construct an instance $(\varPhi ,k)$ of Min Ones 2-SAT, such that (G, H, k) is a yes instance of CF-VC if and only if $(\varPhi ,k)$ is a yes instance of Min Ones 2-SAT. Furthermore, $|V(\varPhi )|=|V(G)|=|V(H)|$.

Proof

We begin with the construction of the formula. Let (G, H, k) be an instance of CF-VC. Given this instance, we construct an instance $(\varPhi ,k)$ of Min Ones 2-SAT as follows. For every edge $uv \in E(G)$, introduce a clause $(u\vee v)$ and for every edge $uv\in E(H)$, introduce a clause $(\bar{u}\vee \bar{v})$ in $\varPhi$. More precisely, given the graphs G and H, the CF-VC is formulated as the following instance Min Ones 2-SAT.

$$\varPhi = \bigwedge _{uv\in E(G)} (u\vee v)\bigwedge _{uv\in E(H)} (\bar{u}\vee \bar{v}).$$

Now, let X be a conflict free vertex cover of G of size at most k. We construct a truth assignment $\tau$ of $\varPhi$ as follows. If $x \in X$ then $\tau (x)=1$, otherwise it is 0. Clearly this satisfies the formula $\varPhi$ and it is of weight at most k. Conversely, let $\tau$ be a satisfying assignment of $\varPhi$ of weight at most k. We construct a set X as follows. If $\tau (u)=1$, add the vertex u to X. For the clause $(u\vee v)$, at least one of $\tau (u)$ or $\tau (v)$ is 1. This ensures that every edge of G is incident to some vertex $u \in X$. For the clause $(\bar{u}\vee \bar{v})$, at least one of $\tau (u)$ or $\tau (v)$ is 0. This ensures that H[X] is edgeless. Clearly, the size of X is at most k.    $\square$

Lemma 2 implies the following result.

Lemma 3

${\varvec{(\star ).}}$ Let G be a graph and H be a conflict graph of G. Then in polynomial time we can test whether there exists a conflict free vertex cover of the instance (G, H, k).

Misra et al. [22] have shown that Min Ones 2-SAT can be solved as fast as Vertex Cover. This implies that CF-VC can also be solved as fast as Vertex Cover. Further, using results from [7, 15, 28], we obtain the following.

Theorem 4

CF-VC admits a 2k-vertex kernel, a factor 2-approximation algorithm, an ${\mathcal O}^{\star }(1.2738^{k})$ FPT algorithm and a ${\mathcal O}^{\star }(1.1996^{n})$ exact algorithm.

Next, we consider some special cases of CF-VC. It is well known that Vertex Cover is NP-complete in general and polynomial time solvable for graphs with maximum degree at most two. We can prove that CF-VC is NP-complete even when graph G is of degree at most 2. In fact, it is true even when G is disjoint union of $P_3$ ($P_\ell$ denotes path on $\ell$ vertices).

Theorem 5

${\varvec{(\star ).}}$ CF-VC is NP-complete when G is of degree at most 2.

However, certain special cases of CF-VC are polynomial time solvable.

Theorem 6

${\varvec{(\star ).}}$ CF-VC is solvable in polynomial time in the following cases:

• (a) The graph G has degree at most one.

• (b) Both the graphs G and H have a perfect matching.

Further Results. Due to space constraints, detailed description of the following results of Conflict Free $d$-Hitting Set, Conflict Free Split Vertex Deletion and Conflict Free Feedback Vertex Set in Tournaments have been deferred to the full version of the paper.

Theorem 7

• (a) The Conflict Free $d$-Hitting Set problem can be solved in ${\mathcal O}^{\star }(((d-1)+.2738)^k)={\mathcal O}^{\star }((d-0.7262)^k)$ time.

• (b) Conflict Free Split Vertex Deletion can be solved in $\mathcal {O}^\star (1.2738^kk^{\mathcal {O}(\log k)})$ time and polynomial space.

• (c) Conflict Free Feedback Vertex Set in Tournaments can be solved in ${\mathcal O}^{\star }(2^k)$ time.

4 Conclusion

In this paper, we introduced a new variant, called the conflict free version, of classical vertex deletion problems that are studied in graph algorithms. We studied these problems in the realm of parameterized complexity and obtain several results that classify the complexity of these problems in various graph classes. Our work opens up a whole new area of research in obtaining dichotomy results. For every property $\mathrm{\Pi }$, where Conflict Free $\mathrm{\Pi }$-Vertex Deletion is $\mathsf{W[1]}$-hard, it is a natural question to ask for which family of graphs H does the problem becomes FPT. As a concrete question in this direction, for which family of graphs H does Conflict Free FVS and Conflict Free OCT admit FPT algorithms and polynomial kernels.