2023/07/11 by Nick Brettell, Brettell, Nick, Jelle J. Oostveen +7 · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2307.05701
openalex publication_date 2023/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, 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=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.