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

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

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, April). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. Presented at Theory and applications of models of computation, 14th Annual Conference, TAMC 2017, Bern, Switzerland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Theory and applications of models of computation, 14th Annual Conference, TAMC 2017
• 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
• Print ISSN: 0302-9743
• 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