Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions
- Paulusma, Daniël Durham University
- Picouleau, Christophe Conservatoire National des Arts et Métiers
- Ries, Bernard University of Fribourg
-
2017
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 324552
- DOI 10.1007/978-3-319-55911-7_34
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307821
Statistics
Document views: 38
File downloads:
- blockers-rero_0.pdf: 82