0
$\begingroup$

Suppose I have a complete directed graph G(E,V). If I have acces to a subroutine that calculates the shortest path from s to t (both in V). Can I use this to find an algorithm that determines a Hamiltonian path from s to t in graph G minimizing the sum of the edge costs of the edges used in the path? The edge costs are nonnegative real numbers.

$\endgroup$
0
$\begingroup$

Yes, you can, but the algorithm will still run in exponential time. The shortest path problem is different from the Hamilton path problem: one can be calculated in time $O(|V|\cdot |E|)$, while the other is NP-Complete. So it is easy to compute the $n\times n$ matrix $C$ where $C[u,v]$ is the cost of the shortest path from $u$ to $v$ (easy in the sense that the number of operations required to do this is bounded by a polynomial in $|V|$, namely $|V|^5$). However, it is not easy to do this if you add the requirement that the path not only be the shortest, but also that it visits all the other nodes first. These costs don't allow you to compute a Hamilton path.

For example, one may naively start with the shortest path from $s$ to $t$. But this path may not visit all edges. So we demand that the path visit node $u$, too, so we might simply concatenate the shortest paths $s-u-t$. But this may not be the shortest path that visits all these nodes; maybe it's $s-t-u$, or $u-t-s$; there are $3!=6$ possibilities to choose from. But none of these paths necessarily visit all the nodes, either, so you add another node $v$, and $\ldots$ and then you have $n!$ sequences to choose from, and you are not better off than the brute force algorithm.

In fact, even if the edge weights are $0,1$, determining whether a Hamilton path of weight at least $k$ exists is NP-Complete. Why is this problem so difficult? Nobody knows for sure! We will know why when we settle $P\overset{?}{=}NP$, but until then, we can say that it looks like brute force enumeration is close to the optimal algorithm.

$\endgroup$
  • $\begingroup$ Thanks for your reply! If we now assume that for some reason my shortest path subroutine is O(1), does that allow me to solve it in polynomial time? $\endgroup$ – Blackjaguar Oct 13 '16 at 21:31
  • $\begingroup$ @Blackjaguar: No (unless P=NP), because if you have a polynomial number of those steps, then implementing them by actually computing each shortest path by the usual polynomial-time algorithm would increase the running time by at most a polynomial factor. $\endgroup$ – Henning Makholm Oct 13 '16 at 21:34
  • $\begingroup$ @Blackjaguar Suppose it did. Then you algorithm with a shortest path oracle runs in $n^k$ for some $k\in \mathbb{N}$ on graphs with $n$ nodes. But in reality, the shortest path algorithm runs in at most $n^3$ time, so in reality your algorithm would run in $n^{k+3}$ time. But we had assumed that in reality, your algorithm was exponential! We have a contradiction. In general composing polynomials leaves you only with more polynomials $\endgroup$ – Lieuwe Vinkhuijzen Oct 13 '16 at 21:35

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.