BARC Talk by Erik Jan van Leeuwen

Complexity Framework For Forbidden Subgraphs and Beyond

Abstract

For any finite set H = H1,...,Hp of graphs, a graph is H-subgraph-free if it does not contain any of H1,...,Hp as a subgraph. Similar to known meta-classifications for the minor and topological minor relations, we give a meta-classification for the subgraph relation. This framework classifies if problems are "efficiently solvable'' or "computationally hard'' for H-subgraph-free graphs.

To illustrate the broad applicability of our framework, we study partitioning, covering and packing problems, network design problems and width parameter problems. We apply the framework to obtain a dichotomy between polynomial-time solvability and NP-completeness. 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 unify and strengthen known results from the literature. We also discuss insights into the complexity of problems on H-subgraph-free graphs that do not fall within the framework.

This talk is based on joint work with Hans Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, and Siani Smith. See https://arxiv.org/abs/2211.12887