14
$\begingroup$

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?

$\endgroup$

6 Answers 6

13
$\begingroup$

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

$\endgroup$
2
  • 7
    $\begingroup$ 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 $\endgroup$
    – ivmihajlin
    Mar 15, 2016 at 17:25
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 16, 2016 at 4:25
11
$\begingroup$

Update 28 Sep 2020: This has been resolved by Wiebking in SODA '20, 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 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).* 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.

$\endgroup$
0
10
$\begingroup$

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]. 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].

$\endgroup$
4
$\begingroup$

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.) 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 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 problems.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

In a recent paper by Fomin et al. (Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds) 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$.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .