Computing Subset Vertex Covers in H-Free Graphs

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 2P3-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. 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 = sP1 + tP2 and NP-complete otherwise.
Moreover, we prove that Subset Vertex Cover is polynomial-time
solvable for (sP1 +P2 +P3)-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