Paulusma, Daniël and Picouleau, Christophe and Ries, Bernard (2017) 'Blocking independent sets for H-free graphs via edge contractions and vertex deletions.', in Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings. Cham: Springer, pp. 470-483. Lecture Notes in Computer Science. (10185).
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).
Item Type: | Book chapter |
---|---|
Full text: | (AM) Accepted Manuscript Download PDF (290Kb) |
Status: | Peer-reviewed |
Publisher Web site: | https://doi.org/10.1007/978-3-319-55911-7_34 |
Publisher statement: | The final publication is available at Springer via https://doi.org/10.1007/978-3-319-55911-7_34 |
Date accepted: | 01 March 2017 |
Date deposited: | 02 May 2017 |
Date of first online publication: | 21 March 2017 |
Date first made open access: | 21 March 2018 |
Save or Share this output
Export: | |
Look up in GoogleScholar |