Computing Subset Transversals in H-Free Graphs

DOI10.1016/J.TCS.2021.12.010MaRDI QIDQ6341605arXivFDO

Authors Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma

Publication date 28 May 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2021.12.010

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

arXiv classification

cs.DSmath.COcs.DM

Abstract: We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed graph~$H$ as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on $H$-free graphs for every graph $H$ except when $H=s{P}_1+P_4$ for some $sgeq1$. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for $(s{P}_1+P_4)$-free graphs for every $sgeq1$.

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

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