1
$\begingroup$

I am trying to prove the following claim:

Given DAG graph, there is Hamilton path iff the following algorithm returns true:

  1. Do topologic sorting.
  2. Move on the graph's vertices one by one (from low to high). In case there is no edge connecting 2 vertices with adjacent values from the topologic sorting then return false. if no false was returned after we check all vertices, return true.

I am stuck of proving one side which is: if there is Hamilton path then the algorithm returns true.

I tried using induction on number of vertices in the graph n:

  • Base case is simple for n==0.

  • Assuming claim is correct for n I want to prove for n+1

So I said, let's exclude the last vertex in the given Hamilton path (let's call it a), and assume by contradiction that the algorithm returned false.

This means one of the 2:

  1. Two vertices with adjacent values had no edge connecting them and both aren't a. this contradictc the assumtion that the claim hold for graph with n vertices.

  2. One of the two vertices is a and the other isn't a.

I am stuck on proving that case (2) will give us a contradiction, How may I continue?

$\endgroup$
2
  • $\begingroup$ To show (1), you first need to show that topological ordering "respects" vertex deletion -- that is, that if $v_{\rho(1)}, \dots, v_{\rho(k-1)}, v_{\rho(k)}, v_{\rho(k+1)}, \dots, v_{\rho(|V|)}$ is a valid TO for $G$, then $v_{\rho(1)}, \dots, v_{\rho(k-1)}, v_{\rho(k+1)}, \dots, v_{\rho(|V|)}$ is a valid TO for $G \setminus \{v_{\rho(k)}\}$. Then you can construct a failing TO for $G \setminus \{a\}$ from the failing TO for $G$ that you have assumed exists. Finally, because the IH holds for all possible TOs of an $n$-vertex graph (I suggest making this explicit), you get your contradiction. $\endgroup$ Apr 24 at 4:20
  • $\begingroup$ For (2), a useful property is that if there is a directed path from $u$ to $v$, $v$ must appear after $u$ in every TO. This should help you constrain the position of $a$ within the TO. Then show (e.g., via induction) that every TO of a HP-having DAG positions the HP's last vertex last in the TO. (Actually, strengthening the IH of this induction to "HP in $n$-vertex DAG $\implies$ TO contains all vertices in HP order with arcs between adjacent vertices" makes it no more difficult and will lead to a simpler direct proof overall.) $\endgroup$ Apr 24 at 4:58
0
$\begingroup$

Try to prove instead (without induction) that if the algorithm returned false, there is no hamilton path.

Hint: there must be two parallel nodes. Can we reach one from the other?

$\endgroup$
7
  • $\begingroup$ your suggestion is even harder, the algorithm returns false if there are 2 adjacent vertices such that there is no edge connecting them I don't see a way from here to prove that this means there is no Hamilton path. $\endgroup$
    – daniel
    Apr 23 at 19:53
  • $\begingroup$ Can you find a path between the two nodes? Since they are parallel in the topological sorting, what does that mean? $\endgroup$
    – nir shahar
    Apr 23 at 19:55
  • $\begingroup$ Also notice that the topological sorting is a DAG. Try to use this fact in your proof $\endgroup$
    – nir shahar
    Apr 23 at 19:55
  • $\begingroup$ there can never be a path connecting them if there is no direct edge. נכון? $\endgroup$
    – daniel
    Apr 23 at 20:07
  • $\begingroup$ And what would that mean about a hamilton path? a hamilton path must always go through all nodes $\endgroup$
    – nir shahar
    Apr 23 at 20:08

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.