Blocking Independent Sets for HFree Graphs via Edge Contractions and Vertex Deletions
Published in:
 Lecture Notes in Computer Science.  2017, vol. 10185, p. 470483
English
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 socalled blocker problems. It is known to be coNPhard 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 coNP hard even if d = k = 1; – in addition we prove that the vertex deletion variant is coNP hard for trianglefree graphs even if d = k = 1; – we prove that the edge contraction variant is NPhard for bipartite graphs but lineartime solvable for trees. By combining our new results with known ones we are able to give full complexity classifications for both variants restricted to Hfree graphs.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/307821
Statistics
Document views: 11
File downloads: