Skip to search boxSkip to navigationSkip to main content

Improved lower bounds for graph embedding problems

  • H.L Bodlaender
    ,
  • T.C. van der Zanden
Output:
Contribution to journal
Article
Academic

Open access

Information

Output type

Output:
Contribution to journal
Article
Academic

Original language

English

Article number

1610.09130v1

Journal (Volume, Issue Number)

arXiv

Publication milestones

  • Published - 28/10/2016

Publication status

Published - 28/10/2016

ISSN

2331-8422

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/\log n)}$ 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 $c\geq 16$. $2^{\Theta(n/\log n)}$ 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.

Documents and Links

Final published version, 455.11 KB

Metrics

Metrics

Download statistics
Download count
154