# [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.