Journal article

Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions

Published in:
  • Lecture Notes in Computer Science. - 2017, vol. 10185, p. 470-483
English 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.
Faculté des sciences économiques et sociales et du management
Département d'informatique
  • English
Computer science and technology
License undefined
Persistent URL

Document views: 24 File downloads:
  • blockers-rero_0.pdf: 54