Complexity Framework For Forbidden Subgraphs I: The Framework

MaRDI QIDQ6418235zbMATH OpenFDO

Authors Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Publication date 23 November 2022

Abstract: For any finite set $mathcalH=H_1,ldots,H_p$ of graphs, a graph is $mathcalH$-subgraph-free if it does not contain any of $H_1,ldots,H_p$ as a subgraph. We give a meta-classification for $mathcalH$-subgraph-free graphs: assuming a problem meets some three conditions, then it is ``efficiently solvable if $mathcalH$ contains a disjoint union of one or more paths and subdivided claws, and is ``computationally hard otherwise. The conditions are that the problem should be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness is preserved under edge subdivision. We illustrate the broad applicability of our meta-classification by obtaining a dichotomy between polynomial-time solvability and NP-completeness for many well-known partitioning, covering and packing problems, network design problems and width parameter problems. For other problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Along the way, we uncover and resolve several open questions from the literature, while adding many new ones.

This page was built for publication: Complexity Framework For Forbidden Subgraphs I: The Framework

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