Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

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:
Export
Look up in GoogleScholar