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$
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

| cite | improve this answer | |
$\endgroup$
  • 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 '16 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$ – Serge Gaspers Mar 16 '16 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.

| cite | improve this answer | |
$\endgroup$
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].

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.