6
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In my post, I already showed that it's trivial to use $h(G)$ to determine whether $G$ has a Hamiltonian path. Also, we both missed that the question states that $G$ is assumed to have at least one Hamiltonian path. $\endgroup$ – David Richerby Jan 3 '14 at 10:35
  • 2
    $\begingroup$ I'm aware of this. Still, any algorithm for a promise problem can be run on an instance violating the promise and produce some (potentially completely arbitrary) output. I try to show that a technique for solving the problem posed can be useful even when the promise may or may not hold. Particularly, if we apply it on a certain sequence of graphs where the promise must hold on at least some subset of the instances, we can glean some information out of when (or if) the algorithm's guess at $h(G)$ changes its value due to the introduction of a single edge. I tried clarifying this in my post. $\endgroup$ – Yonatan N Jan 3 '14 at 12:57
  • 1
    $\begingroup$ While I reckon you are right @Yonatan I don't have the chops to be confident marking my question as answered, unless there is further upvoting. But thanks. And bugger! $\endgroup$ – BenJWoodcroft Jan 4 '14 at 12:40
  • $\begingroup$ Not a problem. If you want any clarification somewhere, let me know! $\endgroup$ – Yonatan N Jan 4 '14 at 23:12
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It certainly doesn't find all the edges. Any bridge (an edge whose removal disconnects the graph) must be in every Hamiltonian path. $\endgroup$ – David Richerby Jan 3 '14 at 9:27
  • $\begingroup$ Hang on, if a graph contains a bridge, then the graph cannot be Hamiltonian. Do you mean bridges cannot be in any Hamiltonian path? $\endgroup$ – BenJWoodcroft Jan 4 '14 at 2:02
  • 2
    $\begingroup$ If a graph contains a bridge, it cannot have a Hamiltonian cycle but it can still contain a Hamiltonian path. For example, if the graph itself is a path, every edge is a bridge and every edge lies on the unique Hamiltnian path. $\endgroup$ – David Richerby Jan 4 '14 at 2:39
1
$\begingroup$

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)$.

$\endgroup$
  • 3
    $\begingroup$ Ben stated that we can assume the input graph to contain at least one hampath, so we can cosider it to be a promise problem. In this case using the promise to show hardness is inappropriate. $\endgroup$ – John D. Jan 3 '14 at 2:14
  • 5
    $\begingroup$ Let me elaborate: as you certainly know the idea behind reducing A to B is that given an algorithm for B we can solve A as well within the same complexity bounds. However, if Ben happens to find an efficient algorithm for his problem which assumes that the input graphs always contain at least one hampath, it doesn't help us to solve Hampath efficiently by only your reasoning(the promise problem still might be NP-hard for other reasons). $\endgroup$ – John D. Jan 3 '14 at 2:16
  • 1
    $\begingroup$ On the other hand, if we drop the promise property your implied reduction doesn't work anymore because we have to check for the existence of a hampath as well. If $h(G)$ returns an empty set this either means there exists no hampath or there is no edge common to all hampaths. $\endgroup$ – John D. Jan 3 '14 at 2:17
  • 1
    $\begingroup$ Thanks for your answer David but I'm with @user17410. $\endgroup$ – BenJWoodcroft Jan 3 '14 at 2:29
  • 2
    $\begingroup$ @user17410 I take the point about the promise problem; I'd not noticed the statement that the graph has at least one Hamiltonian path. However, if the promise is removed then my reduction works just fine: as explained in the proof of the lemma, if $G$ has no Hamiltonian path, $h(G)$ is not the empty set: it is $E(G)$. $\endgroup$ – David Richerby Jan 3 '14 at 9:23

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.