Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
DOI: 10.7155/jgaa.00339
Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs
Jiong Guo and Yash Raj Shrestha
Vol. 18, no. 4, pp. 603-631, 2014. Regular paper.
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.
Submitted: March 2014.
Reviewed: October 2014.
Revised: October 2014.
Accepted: October 2014.
Final: December 2014.
Published: December 2014.
Communicated by Sudebkumar Prasant Pal and Kunihiko Sadakane
article (PDF)
BibTeX