Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs

Abstract

We investigate the computational complexity of Disjoint Π-Vertex Deletion. Here, given an input graph G=(V,E) and a vertex set S ⊆ V, called a solution set, whose removal results in a graph satisfying a non-trivial, hereditary property Π, we are asked to find a solution set S′ with |S′| < |S| and S′∩S = ∅. This problem is partially motivated by the "compression task" occurring in the iterative compression technique. The complexity of this problem has already been studied, with the restriction that Π is satisfied by a graph G iff Π is satisfied by each connected component of G . In this work, we remove this restriction and show that, a few cases which are polynomial-time solvable, almost all other cases of Disjoint Π-Vertex Deletion are NP-hard.