Open Problems and Recent Developments on a Complexity Framework for Forbidden Subgraphs

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. In this invited talk, I discuss a recently proposed algorithmic meta classification that precisely classifies if certain problems (sharing specific properties) are “efficiently solvable” or “computationally hard” for H-subgraph-free graphs, depending on H. For a broad set of classic graph problems, this framework yields a dichotomy (depending on H) between polynomial-time solvability and NP-completeness. For other problems, like computing the diameter of a graph, it gives a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). This paper discusses this framework, highlights current developments and open problems, and surveys recent insights into the complexity on H-subgraph-free graphs of problems that do not fall within the framework.