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).
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)
|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
|Look up in GoogleScholar|