Computing Subset Vertex Covers in H-Free Graphs

DOI10.1007/978-3-031-43587-4_7MaRDI QIDQ6443388zbMATH OpenFDO

Authors Nick Brettell, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Erik Jan van Leeuwen

Publication date 11 July 2023

Full work available at URL https://doi.org/10.1007/978-3-031-43587-4_7

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 $TsubseteqV$ 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 $2P_3$-free weakly chordal graphs. Our results show for the first time that Subset Vertex Cover is computationally harder than Vertex Cover (under P $eq$ 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=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.

This page was built for publication: Computing Subset Vertex Covers in $H$-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443388)