Is there an efficient algorithm for finding edges that are part of all hamiltonian paths?

Question

I'm wondering if there is any algorithm known for finding edges in a graph that are part of all hamiltonian paths (operating under the assumption that the graph has at least one such path). Failing that, is there an algorithm for finding as many of these edges as possible, relaxing the requirement that all such edges are found?

One could find all hamiltonian paths in the graph, and then look at all the edges in those paths, but is there a better way?

One type of edge in this class obvious even to me is edges that are directed to vertices with in-degree 1 (or similarly edges from vertices that have out-degree 1). I'm particularly interested in directed graphs but the insight into the undirected version would also be helpful.

My apologies if this question is overly naive - I ran across this problem while doing microbial genomics, and any help would be greatly appreciated.

Thanks in advance, ben

Answer 1

A polytime algorithm that can find such a collection of edges even in the promise version of this problem can be used as a blackbox to solve the Hamiltonian Path problem in polynomial time, and thus this promise problem is NP-Hard under Cook reductions. The idea here is to use the algorithm for solving the promise problem on a sequence of graphs, many (but not all) of which potentially violate the promise given in the problem statement. Importantly, nothing is assumed of the output of the algorithm when it is fed a promise-violating graph as input, just that it outputs something (perhaps even adversarially). We can, of course, always cut the algorithm off and return the empty set as its solution if its execution is taking longer than some provided time bound (a bound only proven to hold only in promise-satisfying instances) and satisfy this requirement. It is the nature of the change in the algorithm's output (or lack thereof) on the sequence of instances that interests us.

Suppose you have a graph $G=(V,E)$ in which you wish to determine the existence of a Hamiltonian path, and oracle access to a function $\varphi$ such that $\varphi(G) = h(G)$ (where $h$ is defined as in David's post) whenever $G$ contains a Hamiltonian path (and returns an arbitrary answer otherwise). Intuitively, the algorithm searches for a supergraph $H$ of $G$ on which $\varphi(H) = h(H)$ is violated. If such a graph can be found, it must be the case that $H$ (and all of its subgraphs, including $G$) is not Hamiltonian. Conversely, not violating the inequality on any graph in the sequence shows that the original $G$ is Hamiltonian.

Now construct a sequence of graphs $G_0 \cdots G_{n-1}$ as follows:

1. Let $G_0 = G$
2. Pick a permutation $\pi$ of $V$ such that no $(\pi_i, \pi_{i+1})$ is an edge of $\varphi(G_0)$.*
3. For $i = 1$ to $n-1$
   1. Let $e_i = (\pi_i, \pi_{i+1})$
   2. Let $G_i = G_{i-1}$ with edge $e_i$ added (if it did not already exist in $G_{i-1}$)

Note that $h(G_x) \supseteq h(G_y)$ when $x < y$ (i.e. containment of some fixed edge in $h$ is hereditary among the $\{G_i\}$). Thus, if $e_i \in \varphi(G_i)$ for some $i \geq 1$, it must be the case that $G$ does not contain a Hamiltonian Path, since $\varphi(\cdot)$ is not hereditary on this graph family (recall that $e_i$ is not in $\varphi(G_0)$) and thus $\varphi(G_i) \neq h(G_i)$ for some $G_i$.

However, if $e_i \not \in \varphi(G_i)$ for all $i$, no single addition of an edge was necessary in the construction of the first (set of) Hamiltonian Path(s) in the sequence in which we constructed $\{G_i\}$. Since $G_{n-1}$ contains a Hamiltonian path by construction, a simple inductive argument implies $G_0$ must contain one as well.

Thus, Hamiltonian Path can be solved via $O(n)$ queries to an oracle solving this promise problem (assuming they produce an arbitrary output on promise-violating graphs), meaning that any time bound $f(n)$ for an algorithm solving this problem implies a time bound of $O(n f(n))$ for solving Hamiltonian Path, and thus $f(n)$ (and any provable upper bound on the running time for a TM solving this problem) cannot be a polynomial unless $P = NP$.

*This is easy to do because $|h(G_0)| \leq n$ by definition, and we could always of course prematurely determine the nonexistance of a Hamiltonian path if $|\varphi(G_0)|$ is any larger than that.

Answer 2

A partial answer to the easier of my two questions:

If an edge $x\rightarrow y$ is 'obviously' part of all Hamiltonian paths because it is the only edge into vertex $y$, then all other edges from $x$ cannot be in any Hamiltonian cycle, because this would imply the path visits $x$ more than once. Thus, these other edges from $x$ can be removed from the graph, and this may reveal further edges that have in-degree 1 (and thus must also be in all Hamiltonian paths). And so on.

Similar logic can be used where an edge $w \rightarrow z$ is the only edge from $w$, or where the graph is undirected.

I don't think this will find the complete set of edges that are in all Hamiltonian paths, but at least it might find more than just going with the 'obvious' ones mentioned in the question.

Come to think of it if there is some algorithm for finding edges that are not part of any Hamiltonian paths then I'd also be interested in that - this solves a related problem in the field.

Answer 3

If we didn't have the guarantee that there is at least one Hamiltonian path, the following would show NP-hardness.

---

Write $h(G)$ for the set of edges of the digraph $G$ that appear in every Hamiltonian path. The key fact is the following.

Lemma. For a digraph $G$, $h(G)=E(G)$ if, and only if, $G$ is a directed path or $G$ has no Hamiltonian path.

Proof. If $G$ is a directed path, then clearly $h(G)=E(G)$; if $G$ has no Hamiltonian path then, for any edge $e\in G$ there is no Hamiltonian path that does not contain $e$ so $e\in h(G)$.

Conversely, suppose that $h(G)=E(G)$. If $G$ is a directed path, then we are done. If not, then any Hamiltonian path in $G$ would have to be the whole of $G$, which is impossible, since $G$ is not a directed path. Therefore, $G$ has no Hamiltonian path.    $\Box$

As a result, it is NP-hard to compute $h(G)$ since, given $h(G)$, we can determine whether an input graph $G$ has a Hamiltonian path by checking whether $G$ is a path and whether $h(G)=E(G)$. Thus, there is (probably) no polynomial-time algorithm to compute $h(G)$.