
arXiv: 2211.12887
Abstract For a set of graphs $${\mathcal {H}}$$ H , a graph G is $${\mathcal {H}}$$ H -subgraph-free if G does not contain any graph from $${{{\mathcal {H}}}}$$ H as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for $${\mathcal {H}}$$ H -subgraph-free graphs. Namely, a graph problem must be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness must be preserved under edge subdivision of subcubic graphs. Our meta-classification says that if a graph problem $$\Pi $$ Π satisfies all three conditions, then for every finite set $${{{\mathcal {H}}}}$$ H , it is “efficiently solvable” on $${{{\mathcal {H}}}}$$ H -subgraph-free graphs if $${\mathcal {H}}$$ H contains a disjoint union of one or more paths and subdivided claws, and $$\Pi $$ Π is “computationally hard” otherwise. We apply our meta-classification on many well-known partitioning, covering and packing problems, network design problems and width parameter problems to obtain a dichotomy between polynomial-time solvability and -completeness. For distance-metric problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Apart from capturing a large number of explicitly and implicitly known results in the literature, we also prove a number of new results. Moreover, we perform an extensive comparison between the subgraph framework and the existing frameworks for the minor and topological minor relations, and pose several new open problems and research directions.
FOS: Computer and information sciences, Meta-classification, Discrete Mathematics (cs.DM), Treewidth, Analysis of algorithms and problem complexity, Forbidden subgraph, Computational Complexity (cs.CC), complexity dichotomy, forbidden subgraph, Computer Science - Computational Complexity, Graph theory (including graph drawing) in computer science, meta-classification, Computer Science - Data Structures and Algorithms, Complexity dichotomy, treewidth, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Meta-classification, Discrete Mathematics (cs.DM), Treewidth, Analysis of algorithms and problem complexity, Forbidden subgraph, Computational Complexity (cs.CC), complexity dichotomy, forbidden subgraph, Computer Science - Computational Complexity, Graph theory (including graph drawing) in computer science, meta-classification, Computer Science - Data Structures and Algorithms, Complexity dichotomy, treewidth, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
