Rechercher

[PPR17] Blocking Independent Sets for H-free graphs via Edge Contractions and Vertex Deletions

Conférence Internationale avec comité de lecture : Theory and Applications of Models of Computation 2017, January 2017, pp.00-00, Series LNCS, Bern, Suisse,
motcle:
Résumé: 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 variant to be computationally hard even if d = k = 1; – in addition we prove that the vertex deletion variant is co-NP-hard for triangle-free graphs even if d = k = 1; – we prove that the contraction variant is NP-complete 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.

Collaboration: LAMSADE

BibTeX

@inproceedings {
PPR17,
title="{Blocking Independent Sets for H-free graphs via Edge Contractions and Vertex Deletions}",
author=" C. Picouleau and D. Paulusma and B. Ries ",
booktitle="{Theory and Applications of Models of Computation 2017}",
year=2017,
month="January",
series="LNCS",
pages="00-00",
address="Bern, Suisse",
}