TY - GEN
T1 - Complexity Framework for Forbidden Subgraphs II
T2 - 35th International Symposium on Algorithms and Computation, ISAAC 2024
AU - Lozin, Vadim
AU - Martin, Barnaby
AU - Pandey, Sukanya
AU - Paulusma, Daniël
AU - Siggers, Mark
AU - Smith, Siani
AU - van Leeuwen, Erik Jan
N1 - Publisher Copyright:
© Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen.
PY - 2024/12/4
Y1 - 2024/12/4
N2 - For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are solvable in polynomial time on graph classes of bounded treewidth, NP-complete on subcubic graphs, and whose NP-hardness is preserved under edge subdivision. While a lot of problems satisfy these conditions, there are also many problems that do not satisfy all three conditions and for which the complexity in H-subgraph-free graphs is unknown. We study problems for which only the first two conditions of the framework hold (they are solvable in polynomial time on classes of bounded treewidth and NP-complete on subcubic graphs, but NP-hardness is not preserved under edge subdivision). In particular, we make inroads into the classification of the complexity of four such problems: Hamilton Cycle, k-Induced Disjoint Paths, C5-Colouring and Star 3-Colouring. Although we do not complete the classifications, we show that the boundary between polynomial time and NP-complete differs among our problems and also from problems that do satisfy all three conditions of the framework, in particular when we forbid certain subdivisions of the “H”-graph (the graph that looks like the letter “H”). Hence, we exhibit a rich complexity landscape among problems for H-subgraph-free graph classes.
AB - For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are solvable in polynomial time on graph classes of bounded treewidth, NP-complete on subcubic graphs, and whose NP-hardness is preserved under edge subdivision. While a lot of problems satisfy these conditions, there are also many problems that do not satisfy all three conditions and for which the complexity in H-subgraph-free graphs is unknown. We study problems for which only the first two conditions of the framework hold (they are solvable in polynomial time on classes of bounded treewidth and NP-complete on subcubic graphs, but NP-hardness is not preserved under edge subdivision). In particular, we make inroads into the classification of the complexity of four such problems: Hamilton Cycle, k-Induced Disjoint Paths, C5-Colouring and Star 3-Colouring. Although we do not complete the classifications, we show that the boundary between polynomial time and NP-complete differs among our problems and also from problems that do satisfy all three conditions of the framework, in particular when we forbid certain subdivisions of the “H”-graph (the graph that looks like the letter “H”). Hence, we exhibit a rich complexity landscape among problems for H-subgraph-free graph classes.
KW - complexity dichotomy
KW - edge subdivision
KW - forbidden subgraph
KW - treewidth
UR - http://www.scopus.com/inward/record.url?scp=85213017368&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2024.47
DO - 10.4230/LIPIcs.ISAAC.2024.47
M3 - Conference contribution
AN - SCOPUS:85213017368
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 35th International Symposium on Algorithms and Computation, ISAAC 2024
A2 - Mestre, Julian
A2 - Wirth, Anthony
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 8 December 2024 through 11 December 2024
ER -