Geodesic
Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014 , Tome 18 (2014) no. 4, pp. 603-631.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2014_18_4_a6,
     author = {Jiong Guo and Yash Raj Shrestha},
     title = {Complexity of {Disjoint} {\ensuremath{\Pi}-Vertex} {Deletion} for {Disconnected} {Forbidden} {Subgraphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {603--631},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2014},
     doi = {10.7155/jgaa.00339},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00339/}
}
TY  - JOUR
AU  - Jiong Guo
AU  - Yash Raj Shrestha
TI  - Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 603
EP  - 631
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00339/
DO  - 10.7155/jgaa.00339
LA  - en
ID  - JGAA_2014_18_4_a6
ER  - 
%0 Journal Article
%A Jiong Guo
%A Yash Raj Shrestha
%T Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs
%J Journal of Graph Algorithms and Applications
%D 2014
%P 603-631
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00339/
%R 10.7155/jgaa.00339
%G en
%F JGAA_2014_18_4_a6
Jiong Guo; Yash Raj Shrestha. Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
					, Tome 18 (2014) no. 4, pp. 603-631. doi : 10.7155/jgaa.00339. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00339/

Cité par Sources :