Paulusma, Daniël Picouleau, Christophe Ries, Bernard 2017 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 deletion variant to be co-NP- 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 edge contraction variant is NP-hard 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. application/pdf https://folia.unifr.ch/global/documents/307821 https://folia.unifr.ch/documents/307821/files/blockers-rero_0.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-55911-7_34 info:eu-repo/semantics/openAccess License undefined Lecture Notes in Computer Science. - 2017, vol. 10185, p. 470-483 edge contraction vertex deletion independent set blocker info:eu-repo/classification/udc/004 Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions http://purl.org/coar/resource_type/c_6501