Computing subset vertex covers in H-free graphs

Theoretical Computer Science, vol. 1032, pp. 115088

Abstract

We consider a natural generalization of Vertex Cover : the Subset Vertex Cover problem, which is to decide for a graph G = ( V , E ) , a subset T ⊆ V and integer k , if V has a subset S of size at most k , such that S contains at least one end-vertex of every edge incident to a vertex of T . A graph is H -free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that Subset Vertex Cover is NP -complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2 P 3 -free weakly chordal graphs. Our results show for the first time that Subset Vertex Cover is computationally harder than Vertex Cover (under P ≠ NP ). We also prove new polynomial time results, some of which follow from a reduction to Vertex Cover restricted to classes of probe graphs. We first give a dichotomy on graphs where G [ T ] is H -free. Namely, we show that Subset Vertex Cover is polynomial-time solvable on graphs G , for which G [ T ] is H -free, if H = s P 1 + t P 2 and NP -complete otherwise. Moreover, we prove that Subset Vertex Cover is polynomial-time solvable for ( s P 1 + P 2 + P 3 ) -free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for Subset Vertex Cover on H -free graphs.

Authors 5

1. Nick Brettell

   Victoria University of Wellington

   Affiliation as printed

   Victoria University of Wellington, Wellington, New Zealand

2. Jelle J. Oostveen

   Utrecht University

   Affiliation as printed

   Utrecht University, Utrecht, the Netherlands

3. Sukanya Pandey Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

4. Daniël Paulusma

   Durham University

   Affiliation as printed

   Durham University, Durham, United Kingdom

5. Erik Jan van Leeuwen corresponding