Improved lower bounds for graph embedding problems

DOI10.1007/978-3-319-57586-5_9zbMATH Open1486.68123DBLPconf/ciac/BodlaenderZ17arXiv1610.09130OpenAlexW2539662787WikidataQ59567377 ScholiaQ59567377MaRDI QIDQ5283358FDOQ5283358

Authors: Tom C. van der Zanden, Hans L. Bodlaender 

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In this paper, we give new, tight subexponential lower bounds for a number of graph embedding problems. We introduce two related combinatorial problems, which we call String Crafting and Orthogonal Vector crafting, and show that these cannot be solved in time $2^{o(|s|/log|s|)}$, unless the Exponential Time Hypothesis fails. These results are used to obtain simplified hardness results for several graph embedding problems, on more restricted graph classes than previously known: assuming the Exponential Time Hypothesis, there do not exist algorithms that run in $2^{o(n/logn)}$ time for Subgraph Isomorphism on graphs of pathwidth 1, Induced Subgraph Isomorphism on graphs of pathwidth 1, Graph Minor on graphs of pathwidth 1, Induced Graph Minor on graphs of pathwidth 1, Intervalizing 5-Colored Graphs on trees, and finding a tree or path decomposition with width at most $c$ with a minimum number of bags, for any fixed $cgeq16$. $2^{Theta(n/logn)}$ appears to be the "correct" running time for many packing and embedding problems on restricted graph classes, and we think String Crafting and Orthogonal Vector Crafting form a useful framework for establishing lower bounds of this form.

Full work available at URL: https://arxiv.org/abs/1610.09130

Recommendations

• Tight lower bounds on graph embedding problems
• Subexponential time algorithms for embedding \(H\)-minor free graphs
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Publication:2721972
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Bounded degree interval sandwich problems
• Exact algorithms for intervalizing coloured graphs
• The hardness of intervalizing four colored caterpillars
• On intervalizing \(k\)-colored graphs for DNA physical mapping
• Which problems have strongly exponential complexity?
• Bounding the running time of algorithms for scheduling and packing problems
• What's next? Future directions in parameterized complexity
• Subexponential time algorithms for finding small tree and path decompositions
• Subexponential time algorithms for embedding \(H\)-minor free graphs
• Improved lower bounds for graph embedding problems

Cited In (8)

• Improved lower bounds on the randomized complexity of graph properties
• Tight lower bounds on graph embedding problems
• Games, Puzzles and Treewidth
• On the exact complexity of polyomino packing
• On the exact complexity of polyomino packing
• Algorithm Theory - SWAT 2004
• Improved lower bounds for graph embedding problems
• Subexponential time algorithms for embedding \(H\)-minor free graphs

This page was built for publication: Improved lower bounds for graph embedding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283358)