Skip to main content

Research Repository

Advanced Search

Blocking independent sets for H-free graphs via edge contractions and vertex deletions

Paulusma, D.; Picouleau, C.; Ries, B.

Blocking independent sets for H-free graphs via edge contractions and vertex deletions Thumbnail


Authors

C. Picouleau

B. Ries



Contributors

T. Gopal
Editor

G. Jäger
Editor

S. Steila
Editor

Abstract

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=1d=k=1 ; in addition we prove that the vertex deletion variant is co-NP-hard for triangle-free graphs even if d=k=1d=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. D. Paulusma received support from EPSRC (EP/K025090/1).

Citation

Paulusma, D., Picouleau, C., & Ries, B. (2017). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. In T. Gopal, G. Jäger, & S. Steila (Eds.), Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings (470-483). https://doi.org/10.1007/978-3-319-55911-7_34

Conference Name Theory and applications of models of computation, 14th Annual Conference, TAMC 2017
Conference Location Bern, Switzerland
Start Date Apr 20, 2017
End Date Apr 22, 2017
Acceptance Date Mar 1, 2017
Online Publication Date Mar 21, 2017
Publication Date Mar 21, 2017
Deposit Date May 1, 2017
Publicly Available Date Mar 21, 2018
Pages 470-483
Series Title Lecture Notes in Computer Science
Series Number 10185
Series ISSN 0302-9743,1611-3349
Book Title Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings.
ISBN 9783319559100
DOI https://doi.org/10.1007/978-3-319-55911-7_34
Public URL https://durham-repository.worktribe.com/output/1147088

Files





You might also like



Downloadable Citations