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
Is there an efficient algorithm for finding edges that are part of all hamiltonian paths?
graph theory;hamiltonian paths
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:Let $G_0 = G$Pick a permutation $\pi$ of $V$ such that no $(\pi_i, \pi_{i+1})$ is an edge of $\varphi(G_0)$.*For $i = 1$ to $n-1$Let $e_i = (\pi_i, \pi_{i+1})$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.