<p>Well, Hamiltonicity was $\Omega(2^n)$ problem till recently, when <a href="http://eccc.hpi-web.de/report/2013/012/download/" rel="nofollow">it was shown</a> that simple k-path can be solved in $O^*(1.657^k)$, which means $O(1.657^n \cdot poly(n))$ for the classical Hamiltonicity.</p>

CC BY-SA 3.0
2014-01-08T00:55:51.170Z
Is that really for TSP or just Hamiltonicity?
Austin Buchanan
CC BY-SA 3.0
2014-01-08T07:13:33.657Z
Hamiltonicity. It was also open for decades whether a $o(2^k)$ algorithm exists.
R B
CC BY-SA 3.0
2014-01-08T08:24:49.970Z
as far as I know this algorithm (and the other fast ones) are randomized. A fast deterministic one is still open.
M. kanté
CC BY-SA 3.0
2014-01-08T08:30:46.230Z
@M.kanté - I think you are correct. 
The best known **deterministic** algorithm for k-path runs in $O^*(4^k)$, and I believe there will be no $o(2^k)$ deterministic algorithm anytime soon (has to do with the need to "memorize" the visited nodes).

The case for Hamiltonicity of a graph (i.e. k=n), might be different.
R B
CC BY-SA 3.0
2014-01-08T16:07:30.507Z
You can solve $k$-path in $O^*(2.851^k)$ deterministic time, see http://arxiv.org/pdf/1304.4626v3.pdf.
Andreas Björklund
CC BY-SA 3.0
2014-01-08T19:27:56.140Z
Just to set the record straight: The first improvement on Hamiltonicity beyond 2^n was Björklund, 2010: http://arxiv.org/abs/1008.0541, getting $O^*(1.657^n)$. An $O^*(1.657^k)$ result for k-path followed just after, with a bigger group of authors: http://arxiv.org/abs/1007.1161. (And yes, these results are both randomized.)
Magnus Wahlström
CC BY-SA 3.0
2014-01-07T22:26:55.947Z
2014-01-08T08:32:20.313Z
2014-01-08T08:32:20.313Z
R B
<p>In the <em>connected dominating set problem</em> (CDS) we are given an <span class="math-container">$n$</span>-vertex undirected graph, and asked to find the smallest connected subset <span class="math-container">$S$</span> of vertices such that each vertex not in <span class="math-container">$S$</span> is adjacent to some vertex in <span class="math-container">$S$</span>. If we drop the connectedness requirement (the usual dominating set problem (DS)), we have exact algorithms that are much faster than the naive brute force method. The trivial algorithm for CDS runs in <span class="math-container">$\Omega(2^n)$</span> time and enumerates all the subsets of vertices. To the best of my knowledge, the fastest known exact algorithm for CDS is the one given by Fomin, Grandoni and Kratsch running in <span class="math-container">$O(1.9407^n)$</span> time.</p>
<p>It seems both intuitively true, and also generally accepted in the literature, that non-local problems (such as CDS) are harder to solve than local problems (such as DS). The reason seems to be that often exact algorithms are exploiting the local structure of the problem whereas say connectivity is a global property. Another non-local problem is TSP, for which as far as I know, the fastest known algorithm dates back to the sixties and runs in <span class="math-container">$\Omega(2^n)$</span> time.</p>
<p>Say for TSP, we do have faster algorithms for special graph classes of course (cubic, bounded-degree, and so on). Also, for many non-local problems on graphs of bounded treewidth we have (I guess possibly even optimal under SETH) algorithms (see the work by Cygan et al). Similarly, I think we can get <span class="math-container">$O(c^{\sqrt{n}})$</span> algorithms for non-local problems on planar graphs using a result of Fomin and Thilikos bounding the treewidth of a planar graph, and showing how a tree decomposition of such width can be found in polynomial time. But what about general (undirected) graphs?</p>
<p>It indeed appears that for many non-local problems the best known algorithms are still trivial. For Steiner tree (i.e. find a minimum size subtree of a given graph spanning a given subset of <span class="math-container">$k$</span> nodes), we have a <span class="math-container">$O(1.4143^n)$</span> time algorithm obtained by combining the <span class="math-container">$O((2+\epsilon)^kn^{O(1)}$</span> DP algorithm (for small <span class="math-container">$k$</span>) with the trivial <span class="math-container">$O(2^{n-k}n^{O(1)})$</span> enumeration of Steiner nodes (for large <span class="math-container">$k$</span>). To the best of my knowledge, finding a polynomial space algorithm faster than <span class="math-container">$2^n$</span> is still open.</p>
<blockquote>
<p><strong>(1)</strong> What other examples of non-local problems besides connected dominating set and Steiner tree do we have such that there is a faster non-trivial exact algorithm for them (on general graphs)?</p>
<p><strong>(2)</strong> Is it possible to extract some kind of general algorithmic design techniques from the known fast exact algorithms for non-local problems?</p>
</blockquote>

CC BY-SA 3.0
2014-01-08T16:04:18.117Z
Steiner trees can be found fast in polynomial space, see http://www.ii.uib.no/~daniello/papers/steinerPolySpace.pdf.
Andreas Björklund
CC BY-SA 3.0
2014-01-08T21:31:29.563Z
I think it's not bad to look at some more works of Fomin etal. I already provide some related information to your question in this answer: http://cstheory.stackexchange.com/questions/10815/decomposing-graphs-of-genus-one/19190#19190 . That is a good try to deal with larger class of graphs for non local problems. Specially last paragraph.
Saeed
<np-hardness><exp-time-algorithms>
Design of exact algorithms for non-local hard problems
Juho
# Design of exact algorithms for non-local hard problems

(Asked by: username_0 on 2014-01-07)

In the *connected dominating set problem* (CDS) we are given an $n$-vertex undirected graph, and asked to find the smallest connected subset $S$ of vertices such that each vertex not in $S$ is adjacent to some vertex in $S$. If we drop the connectedness requirement (the usual dominating set problem (DS)), we have exact algorithms that are much faster than the naive brute force method. The trivial algorithm for CDS runs in $\Omega(2^n)$ time and enumerates all the subsets of vertices. To the best of my knowledge, the fastest known exact algorithm for CDS is the one given by Fomin, Grandoni and Kratsch running in $O(1.9407^n)$ time.

It seems both intuitively true, and also generally accepted in the literature, that non-local problems (such as CDS) are harder to solve than local problems (such as DS). The reason seems to be that often exact algorithms are exploiting the local structure of the problem whereas say connectivity is a global property. Another non-local problem is TSP, for which as far as I know, the fastest known algorithm dates back to the sixties and runs in $\Omega(2^n)$ time.

Say for TSP, we do have faster algorithms for special graph classes of course (cubic, bounded-degree, and so on). Also, for many non-local problems on graphs of bounded treewidth we have (I guess possibly even optimal under SETH) algorithms (see the work by Cygan et al). Similarly, I think we can get $O(c^{\sqrt{n}})$ algorithms for non-local problems on planar graphs using a result of Fomin and Thilikos bounding the treewidth of a planar graph, and showing how a tree decomposition of such width can be found in polynomial time. But what about general (undirected) graphs?

It indeed appears that for many non-local problems the best known algorithms are still trivial. For Steiner tree (i.e. find a minimum size subtree of a given graph spanning a given subset of $k$ nodes), we have a $O(1.4143^n)$ time algorithm obtained by combining the $O((2+\epsilon)^kn^{O(1)}$ DP algorithm (for small $k$) with the trivial $O(2^{n-k}n^{O(1)})$ enumeration of Steiner nodes (for large $k$). To the best of my knowledge, finding a polynomial space algorithm faster than $2^n$ is still open.

> **(1)** What other examples of non-local problems besides connected dominating set and Steiner tree do we have such that there is a faster non-trivial exact algorithm for them (on general graphs)?
>
> **(2)** Is it possible to extract some kind of general algorithmic design techniques from the known fast exact algorithms for non-local problems?

**Tags:** np-hardness, exp-time-algorithms
> **Comments:**
> **username_1**: Steiner trees can be found fast in polynomial space, see http://www.ii.uib.no/~daniello/papers/steinerPolySpace.pdf.  
> **username_2**: I think it's not bad to look at some more works of Fomin etal. I already provide some related information to your question in this answer: http://cstheory.stackexchange.com/questions/10815/decomposing-graphs-of-genus-one/19190#19190 . That is a good try to deal with larger class of graphs for non local problems. Specially last paragraph.  

---

## 1 answers

### Answer by username_3 on 2014-01-07. Score: 2

Well, Hamiltonicity was $\Omega(2^n)$ problem till recently, when [it was shown](http://eccc.hpi-web.de/report/2013/012/download/) that simple k-path can be solved in $O^\*(1.657^k)$, which means $O(1.657^n \cdot poly(n))$ for the classical Hamiltonicity.

> **Comments:**
> **username_4**: Is that really for TSP or just Hamiltonicity?  
> **username_3**: Hamiltonicity. It was also open for decades whether a $o(2^k)$ algorithm exists.  
> **username_5**: as far as I know this algorithm (and the other fast ones) are randomized. A fast deterministic one is still open.  
> **username_3**: @M.kanté - I think you are correct.  The best known **deterministic** algorithm for k-path runs in $O^*(4^k)$, and I believe there will be no $o(2^k)$ deterministic algorithm anytime soon (has to do with the need to "memorize" the visited nodes).  The case for Hamiltonicity of a graph (i.e. k=n), might be different.  
> **username_1**: You can solve $k$-path in $O^*(2.851^k)$ deterministic time, see http://arxiv.org/pdf/1304.4626v3.pdf.  
> **username_6**: Just to set the record straight: The first improvement on Hamiltonicity beyond 2^n was Björklund, 2010: http://arxiv.org/abs/1008.0541, getting $O^*(1.657^n)$. An $O^*(1.657^k)$ result for k-path followed just after, with a bigger group of authors: http://arxiv.org/abs/1007.1161. (And yes, these results are both randomized.)  

---

