Computing subset vertex covers in H-free graphs
Nick Brettell, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen · Theoretical Computer Science · 2025
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.