2
$\begingroup$

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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
2
$\begingroup$

Well, Hamiltonicity was $\Omega(2^n)$ problem till recently, when it was shown 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Is that really for TSP or just Hamiltonicity? $\endgroup$
    – Austin Buchanan
    Jan 8, 2014 at 0:55
  • 1
    $\begingroup$ Hamiltonicity. It was also open for decades whether a $o(2^k)$ algorithm exists. $\endgroup$
    – R B
    Jan 8, 2014 at 7:13
  • $\begingroup$ as far as I know this algorithm (and the other fast ones) are randomized. A fast deterministic one is still open. $\endgroup$
    – M. kanté
    Jan 8, 2014 at 8:24
  • 1
    $\begingroup$ You can solve $k$-path in $O^*(2.851^k)$ deterministic time, see arxiv.org/pdf/1304.4626v3.pdf. $\endgroup$
    – Andreas Björklund
    Jan 8, 2014 at 16:07
  • 2
    $\begingroup$ Just to set the record straight: The first improvement on Hamiltonicity beyond 2^n was Björklund, 2010: 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: arxiv.org/abs/1007.1161. (And yes, these results are both randomized.) $\endgroup$
    – Magnus Wahlström
    Jan 8, 2014 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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