Erik Jan van Leeuwen is an assistant professor at Utrecht University in The Netherlands. He researches and teaches algorithms for the analysis of networks, particularly graph algorithms. He was previously a Senior Researcher at the MPI.

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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

Roohani Sharma

+49 681 9325 1116

--email hidden