Open Problems and Recent Developments on a Complexity Framework for Forbidden Subgraphs
摘要
For any finite set \(\mathcal {H} = \{H_1,\ldots ,H_p\}\) of graphs, a graph is \(\mathcal {H}\) -subgraph-free if it does not contain any of \(H_1,\ldots ,H_p\) 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 \(\mathcal {H}\) -subgraph-free graphs, depending on \(\mathcal {H}\) . For a broad set of classic graph problems, this framework yields a dichotomy (depending on \(\mathcal {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 \(\mathcal {H}\) -subgraph-free graphs of problems that do not fall within the framework.