|
 
|
[PPR17] Blocking Independent Sets for H-free graphs via Edge Contractions and Vertex Deletions
Conférence Internationale avec comité de lecture : Theory and Applications of Models of Computation 2017, April 2017, pp.00-00, Series LNCS, Bern, Suisse,
motcle:
Résumé:
Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these two settings:
– we give a sufficient condition on a graph class for the vertex variant to be computationally hard even if d = k = 1;
– in addition we prove that the vertex deletion variant is co-NP-hard for triangle-free graphs even if d = k = 1;
– we prove that the contraction variant is NP-complete for bipartite graphs but linear-time solvable for trees.
By combining our new results with known ones we are able to give full complexity classifications for both variants restricted to H-free graphs.
Collaboration:
LAMSADE
BibTeX
| @inproceedings { | |||
| PPR17, | |||
| title | = | "{Blocking Independent Sets for H-free graphs via Edge Contractions and Vertex Deletions}", | |
| author | = | " C. Picouleau and D. Paulusma and B. Ries ", | |
| booktitle | = | "{Theory and Applications of Models of Computation 2017}", | |
| year | = | 2017, | |
| month | = | "April", | |
| series | = | "LNCS", | |
| pages | = | "00-00", | |
| address | = | "Bern, Suisse", | |
| } | |||
