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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Erik Jan van Leeuwen

摘要

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.