# Design of exact algorithms for non-local hard problems

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?

• Steiner trees can be found fast in polynomial space, see ii.uib.no/~daniello/papers/steinerPolySpace.pdf. Commented Jan 8, 2014 at 16:04
• 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: cstheory.stackexchange.com/questions/10815/… . That is a good try to deal with larger class of graphs for non local problems. Specially last paragraph. Commented Jan 8, 2014 at 21:31

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.
• Hamiltonicity. It was also open for decades whether a $o(2^k)$ algorithm exists.
• You can solve $k$-path in $O^*(2.851^k)$ deterministic time, see arxiv.org/pdf/1304.4626v3.pdf. Commented Jan 8, 2014 at 16:07
• 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.) Commented Jan 8, 2014 at 19:27