<p>In the <strong>Graph Homomorphism</strong> problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\in E(G)$ we have that $h(u) h(v)\in E(H)$.</p>

<p>The problem can be solved in time $O^*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^*$-notation hides factors polynomial in the input size).</p>

<p>However it is open whether it can be solved in time $O^*(c^{|V(H)|+|V(G)|})$, and this appears as an open question in</p>

<ul>
<li>Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
<a href="http://dx.doi.org/10.1007/s00224-007-2007-x">Exact Algorithms for Graph Homomorphisms</a>. Theory Comput. Syst. 41(2): 381-393 (2007)</li>
</ul>

CC BY-SA 3.0
2016-03-15T17:25:57.363Z
In fact, assuming Exponential Time Hypothesis, one can prove that there is no $O^*(c^{|V(H)|+|V(G)|})$ time algorithm:

[Tight Lower Bounds on Graph Embedding Problems](http://arxiv.org/abs/1602.05016)
ivmihajlin
CC BY-SA 3.0
2016-03-16T04:25:36.193Z
Thanks for the pointer! The last section of that paper also contains more concrete embedding problems for which it is not clear whether single-exponential time algorithms can be obtained.
Serge Gaspers
CC BY-SA 3.0
2016-03-15T06:39:19.687Z
2016-03-15T06:39:19.687Z
Serge Gaspers
<p><strong>Update 28 Sep 2020</strong>: This has been resolved by <a href="https://doi.org/10.1137/1.9781611975994.14" rel="nofollow noreferrer">Wiebking in SODA '20</a>, where he gave a <span class="math-container">$2^{O(n)}$</span>-time algorithm, with no remaining dependence on <span class="math-container">$|G|$</span>. (I'll leave up the rest of the answer for historical purposes.)</p>
<p>Permutational Isomorphism of Permutation Groups, aka Permutation Group Conjugacy:</p>
<blockquote>
<p>Input: Two lists of permutations in <span class="math-container">$S_n$</span>, say <span class="math-container">$(\pi_1, \dotsc, \pi_k)$</span> and <span class="math-container">$(\rho_1, \dotsc, \rho_\ell)$</span></p>
<p>Output: A permutation <span class="math-container">$\pi \in S_n$</span> such that <span class="math-container">$\pi^{-1} \langle \pi_1, \dotsc, \pi_k \rangle \pi = \langle \rho_1, \dotsc, \rho_\ell \rangle$</span>, or &quot;NOT ISOMORPHIC&quot;</p>
</blockquote>
<p>(where <span class="math-container">$\langle \pi_1, \dotsc, \pi_k \rangle$</span> means the subgroup generated by the <span class="math-container">$\pi_i$</span>).</p>
<p>As with the Hamiltonian path example, there is a trivial <span class="math-container">$n! = 2^{O(n \log n)}$</span> algorithm. The best <a href="http://dx.doi.org/10.1007/978-3-642-31594-7_5" rel="nofollow noreferrer">currently known</a> is <span class="math-container">$2^{O(n)} |G|^{O(1)}$</span> where <span class="math-container">$G = \langle \pi_1, \dotsc, \pi_k \rangle$</span>. Note that <span class="math-container">$|G|$</span> can be as large as <span class="math-container">$n!$</span> (trivially: <span class="math-container">$G = S_n$</span>) or even <span class="math-container">$n! / n^{O(1)}$</span> for nontrivial <span class="math-container">$G$</span> (see, e.g., the <a href="https://en.wikipedia.org/wiki/O%27Nan%E2%80%93Scott_theorem" rel="nofollow noreferrer">O'Nan-Scott Theorem</a>).* Removing the dependence on <span class="math-container">$|G|$</span> was left there as an important open problem.</p>
<p>* - Despite the fact that <span class="math-container">$G$</span> can be large, so in the worst case this appears to be asymptotically no better than trivial, it turns out that <span class="math-container">$2^{O(n)}|G|^{O(1)}$</span> was exactly what was needed for the polynomial-time isomorphism test of groups with no Abelian normal subgroups.</p>

CC BY-SA 4.0
2016-03-14T18:24:57.267Z
2020-09-28T15:52:13.223Z
2020-09-28T15:52:13.223Z
Joshua Grochow
<p>Computing the crossing number of a graph. Existing exact algorithms involve formulating it as an integer linear program with a number of variables cubic in the number of edges <a href="http://doi.org/10.1007/978-3-540-87744-8_24">[Chimani et al, ESA 2008]</a>. Even for the restricted one-page crossing number, in which the vertices are placed on the boundary of a disk and the edges interior to the disk, known algorithms are exponential in $O(n\log n)$ rather than singly-exponential <a href="http://arxiv.org/abs/1308.5741">[Bannister et al, GD 2013]</a>.</p>

CC BY-SA 3.0
2016-03-14T19:08:31.527Z
2016-03-14T19:08:31.527Z
David Eppstein
<p>Tensor Isomorphism. The best-known algorithm for 3-Tensor Isomorphism over <span class="math-container">$\mathbb{F}_q$</span> takes time <span class="math-container">$q^{\Theta(n^2)}$</span>, and over <span class="math-container">$\mathbb{R}$</span> or <span class="math-container">$\mathbb{C}$</span> takes times <span class="math-container">$2^{\Theta(n^2)}$</span>. (The same is true for <span class="math-container">$d$</span>-Tensor Isomorphism for <span class="math-container">$d \geq 3$</span>, where a factor of <span class="math-container">$d-2$</span> is hidden in the <span class="math-container">$\Theta(\cdot)$</span> in the exponent. But the <span class="math-container">$d=3$</span> case <a href="https://arxiv.org/abs/1907.00309" rel="nofollow noreferrer">is already TI-complete</a>.) In the first case: brute force over <span class="math-container">$GL_n(\mathbb{F}_q)$</span>, which has size roughly <span class="math-container">$q^{n^2}$</span>, and in the second case using quantifier elimination to find the <span class="math-container">$n^2$</span> unknowns of an element of <span class="math-container">$GL_n(\mathbb{R})$</span>, which takes time simply-exponential in the number of unknowns.</p>
<p>Solving TI over <span class="math-container">$\mathbb{F}_p$</span> in time <span class="math-container">$p^{\Theta(n)}$</span> instead would put isomorphism of for some of the <a href="https://cstheory.stackexchange.com/q/42537/129">hardest cases of Group Isomorphism</a> into <span class="math-container">$\mathsf{P}$</span> (namely, <span class="math-container">$p$</span>-groups of exponent <span class="math-container">$p$</span> and nilpotency class <span class="math-container">$2$</span>). The reductions between these problems imply that getting time <span class="math-container">$p^{\Theta(n^c)}$</span> for TI corresponds to solving isomorphism for this class of groups in time <span class="math-container">$|G|^{\Theta((\log |G|)^{c-1})}$</span>, and the current record for Group Iso for this class of groups stands at <span class="math-container">$c=2$</span>, which is the same as the best for general GroupIso.</p>
<p>I don't know direct surprising/difficult consequences of solving in <span class="math-container">$2^{\Theta(n)}$</span> time over <span class="math-container">$\mathbb{R}$</span> or <span class="math-container">$\mathbb{C}$</span>, except that doing so would be seen as a significant step towards getting <span class="math-container">$q^{\Theta(n)}$</span>-time over finite fields.</p>
<p>This same issue arises in many other <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#ti" rel="nofollow noreferrer"><span class="math-container">$\mathsf{TI}$</span>-complete</a> problems.</p>

CC BY-SA 4.0
2020-09-28T01:28:05.507Z
2020-09-28T01:28:05.507Z
Joshua Grochow
<p>The problem of testing whether a given integer linear program <span class="math-container">$L$</span> with <span class="math-container">$n$</span> variables has a feasible solution can be solved using <span class="math-container">$n^{2.5n+o(n)}\cdot |L|$</span> arithmetic operations. It is a major open problem in combinatorial optimization and parameterized algorithms whether this can be improved to a running time of <span class="math-container">$2^{O(n)}\cdot |L|^{O(1)}$</span>.</p>
<p>It can be easily seen that a running time of <span class="math-container">$(2-\epsilon)^n \cdot |L|^{O(1)}$</span> would imply that the Strong Exponential Time Hypothesis (SETH) is false. I am not aware of any better conditional lower bounds for the problem.</p>

CC BY-SA 4.0
2020-09-30T13:49:53.213Z
2020-09-30T13:49:53.213Z
Christian Komusiewicz
<p>In a recent paper by Fomin et al. (<a href="https://arxiv.org/abs/2004.11621" rel="nofollow noreferrer">Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds</a>) it is shown that computing the Hadwiger number of a graph has the complexity profile this question is looking for. Namely, the problem can be solved in <span class="math-container">$n^{O(n)}$</span> fairly easily, but cannot be solved in <span class="math-container">$n^{o(n)}$</span> unless the ETH is false. The Hadwiger number of a graph <span class="math-container">$G$</span> is the size of the largest clique minor contained in <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2020-09-30T18:42:44.307Z
2020-09-30T18:42:44.307Z
Michael Lampis
<p>I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c&gt;1$ but for which it is not known whether there is an algorithm running in time $2^{O(n)}$. </p>

<p>I'm mostly interested on graph theoretic problems, but other nice examples would also be welcome.</p>

<p>For instance, it is trivial to develop an algorithm running in time 
$O(n!) = 2^{O(n\log n)}$ for the Hamiltonian path problem. Just test all permutations. Using dynamic programming however, one can achieve time $2^{O(n)}$. Are there other natural connectivity problems, or variations of the Hamiltonian path problem for which no algorithm running in time $2^{O(n)}$
is known? </p>

<exp-time-algorithms><hamiltonian-paths>
Problems with Unknown Single Exponential Time Agorithms
verifying
# Problems with Unknown Single Exponential Time Agorithms

(Asked by: username_0 on 2016-03-14)

I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c>1$ but for which it is not known whether there is an algorithm running in time $2^{O(n)}$.

I'm mostly interested on graph theoretic problems, but other nice examples would also be welcome.

For instance, it is trivial to develop an algorithm running in time
$O(n!) = 2^{O(n\log n)}$ for the Hamiltonian path problem. Just test all permutations. Using dynamic programming however, one can achieve time $2^{O(n)}$. Are there other natural connectivity problems, or variations of the Hamiltonian path problem for which no algorithm running in time $2^{O(n)}$
is known?

**Tags:** exp-time-algorithms, hamiltonian-paths


---

## 6 answers

### Answer by username_1 on 2016-03-15. Score: 13

In the **Graph Homomorphism** problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\in E(G)$ we have that $h(u) h(v)\in E(H)$.

The problem can be solved in time $O^\*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^\*$-notation hides factors polynomial in the input size).

However it is open whether it can be solved in time $O^\*(c^{|V(H)|+|V(G)|})$, and this appears as an open question in

* Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
  [Exact Algorithms for Graph Homomorphisms](http://dx.doi.org/10.1007/s00224-007-2007-x). Theory Comput. Syst. 41(2): 381-393 (2007)

> **Comments:**
> **username_2**: In fact, assuming Exponential Time Hypothesis, one can prove that there is no $O^*(c^{|V(H)|+|V(G)|})$ time algorithm:  [Tight Lower Bounds on Graph Embedding Problems](http://arxiv.org/abs/1602.05016)  
> **username_1**: Thanks for the pointer! The last section of that paper also contains more concrete embedding problems for which it is not clear whether single-exponential time algorithms can be obtained.  

---

### Answer by username_3 on 2016-03-14. Score: 11

**Update 28 Sep 2020**: This has been resolved by [Wiebking in SODA '20](https://doi.org/10.1137/1.9781611975994.14), where he gave a $2^{O(n)}$-time algorithm, with no remaining dependence on $|G|$. (I'll leave up the rest of the answer for historical purposes.)

Permutational Isomorphism of Permutation Groups, aka Permutation Group Conjugacy:

> Input: Two lists of permutations in $S\_n$, say $(\pi\_1, \dotsc, \pi\_k)$ and $(\rho\_1, \dotsc, \rho\_\ell)$
>
> Output: A permutation $\pi \in S\_n$ such that $\pi^{-1} \langle \pi\_1, \dotsc, \pi\_k \rangle \pi = \langle \rho\_1, \dotsc, \rho\_\ell \rangle$, or "NOT ISOMORPHIC"

(where $\langle \pi\_1, \dotsc, \pi\_k \rangle$ means the subgroup generated by the $\pi\_i$).

As with the Hamiltonian path example, there is a trivial $n! = 2^{O(n \log n)}$ algorithm. The best [currently known](http://dx.doi.org/10.1007/978-3-642-31594-7_5) is $2^{O(n)} |G|^{O(1)}$ where $G = \langle \pi\_1, \dotsc, \pi\_k \rangle$. Note that $|G|$ can be as large as $n!$ (trivially: $G = S\_n$) or even $n! / n^{O(1)}$ for nontrivial $G$ (see, e.g., the [O'Nan-Scott Theorem](https://en.wikipedia.org/wiki/O%27Nan%E2%80%93Scott_theorem)).\* Removing the dependence on $|G|$ was left there as an important open problem.

\* - Despite the fact that $G$ can be large, so in the worst case this appears to be asymptotically no better than trivial, it turns out that $2^{O(n)}|G|^{O(1)}$ was exactly what was needed for the polynomial-time isomorphism test of groups with no Abelian normal subgroups.


---

### Answer by username_4 on 2016-03-14. Score: 10

Computing the crossing number of a graph. Existing exact algorithms involve formulating it as an integer linear program with a number of variables cubic in the number of edges [[Chimani et al, ESA 2008]](http://doi.org/10.1007/978-3-540-87744-8_24). Even for the restricted one-page crossing number, in which the vertices are placed on the boundary of a disk and the edges interior to the disk, known algorithms are exponential in $O(n\log n)$ rather than singly-exponential [[Bannister et al, GD 2013]](http://arxiv.org/abs/1308.5741).


---

### Answer by username_3 on 2020-09-28. Score: 4

Tensor Isomorphism. The best-known algorithm for 3-Tensor Isomorphism over $\mathbb{F}\_q$ takes time $q^{\Theta(n^2)}$, and over $\mathbb{R}$ or $\mathbb{C}$ takes times $2^{\Theta(n^2)}$. (The same is true for $d$-Tensor Isomorphism for $d \geq 3$, where a factor of $d-2$ is hidden in the $\Theta(\cdot)$ in the exponent. But the $d=3$ case [is already TI-complete](https://arxiv.org/abs/1907.00309).) In the first case: brute force over $GL\_n(\mathbb{F}\_q)$, which has size roughly $q^{n^2}$, and in the second case using quantifier elimination to find the $n^2$ unknowns of an element of $GL\_n(\mathbb{R})$, which takes time simply-exponential in the number of unknowns.

Solving TI over $\mathbb{F}\_p$ in time $p^{\Theta(n)}$ instead would put isomorphism of for some of the [hardest cases of Group Isomorphism](https://cstheory.stackexchange.com/q/42537/129) into $\mathsf{P}$ (namely, $p$-groups of exponent $p$ and nilpotency class $2$). The reductions between these problems imply that getting time $p^{\Theta(n^c)}$ for TI corresponds to solving isomorphism for this class of groups in time $|G|^{\Theta((\log |G|)^{c-1})}$, and the current record for Group Iso for this class of groups stands at $c=2$, which is the same as the best for general GroupIso.

I don't know direct surprising/difficult consequences of solving in $2^{\Theta(n)}$ time over $\mathbb{R}$ or $\mathbb{C}$, except that doing so would be seen as a significant step towards getting $q^{\Theta(n)}$-time over finite fields.

This same issue arises in many other [$\mathsf{TI}$-complete](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#ti) problems.


---

### Answer by username_5 on 2020-09-30. Score: 4

The problem of testing whether a given integer linear program $L$ with $n$ variables has a feasible solution can be solved using $n^{2.5n+o(n)}\cdot |L|$ arithmetic operations. It is a major open problem in combinatorial optimization and parameterized algorithms whether this can be improved to a running time of $2^{O(n)}\cdot |L|^{O(1)}$.

It can be easily seen that a running time of $(2-\epsilon)^n \cdot |L|^{O(1)}$ would imply that the Strong Exponential Time Hypothesis (SETH) is false. I am not aware of any better conditional lower bounds for the problem.


---

### Answer by username_6 on 2020-09-30. Score: 2

In a recent paper by Fomin et al. ([Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds](https://arxiv.org/abs/2004.11621)) it is shown that computing the Hadwiger number of a graph has the complexity profile this question is looking for. Namely, the problem can be solved in $n^{O(n)}$ fairly easily, but cannot be solved in $n^{o(n)}$ unless the ETH is false. The Hadwiger number of a graph $G$ is the size of the largest clique minor contained in $G$.


---

