8
$\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$
8
$\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$
  • 5
    $\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
  • $\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
7
$\begingroup$

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

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.