We have a simple undirected connected graph G and two specific nodes s and t. We delete a node and gets to a graph G' that it has a hamiltonian path between s and t. What necessary conditions has to be that we can say the main graph G has a hamiltonian path between s and t too?

For example, take the Petersen graph, shown below:

enter image description here

We have this path between e and f nodes: "eabcdigjhf".

And if we delete node d we have this path: "eabchjgif"

  • $\begingroup$ Do we know the Hamilton path in $G'$ or do we merely know of its existence? $\endgroup$
    – saulspatz
    Jun 8 '20 at 18:42
  • $\begingroup$ @saulspatz we know the path. We actually find the path in graph G' $\endgroup$
    – Z.Gh
    Jun 8 '20 at 18:44
  • $\begingroup$ @saulspatz look at this picture now please. Maybe it'll help you $\endgroup$
    – Z.Gh
    Jun 8 '20 at 19:12
  • $\begingroup$ I understand the problem, but I have no idea how to solve it. It seems rather hopeless to me. The Hamilton path in $G$ that has nothing to do with the one in $G'$, and then we're just looking for a Hamilton path in $G$. $\endgroup$
    – saulspatz
    Jun 8 '20 at 19:16

As a partial (negative) result, the problem of finding a Hamiltonian $s,t$-path in $G$ is NP-complete, even if we are given a Hamiltonian $s,t$-path in $G'$.

(The usual proof in such cases that finding a structure is the same as checking it exists doesn't seem to work, since there's no way to easily use an algorithm for the decision problem to figure out which edges of the Hamiltonian $s,t$-path in $G'$ are necessary.)

To see prove this, we will assume that we have an efficient algorithm that extends a Hamiltonian $s,t$-path in $G'$ to a Hamiltonian $s,t$-path in $G$. Then, we will use it to find Hamiltonian paths in arbitrary graphs.

Let $H$ be any $n$-vertex graph with designated vertices $s$ and $t$, in which we want to find a Hamiltonian $s,t$-path. First, add a vertex $s'$ that must always go right after $s$: replace all edges $sv$ by edges $s'v$, and add an edge $ss'$. Call the resulting graph $H_1$.

Next, we will turn $H_1$ into a graph $H_2$ that's guaranteed to have a Hamiltonian $s,t$-path. To do this, add $n$ extra vertices $v_1, \dots, v_n$ that are adjacent to each vertex of $H_1$, and to each other. To get a Hamiltonian $s,t$-path in $H_2$, just alternate vertices of $H_1$ and vertices from $v_1, \dots, v_n$ in an arbitrary way.

Finally, add the following vertices one at a time, using our putative algorithm to check extend our existing Hamiltonian $s,t$-path if it is possible:

  1. A vertex adjacent only to $s$ and $v_1$.
  2. A vertex adjacent only to $v_1$ and $v_2$.
  3. A vertex adjacent only to $v_2$ and $v_3$.
  4. And so on, up until a vertex adjacent only to $v_{n-1}$ and $v_n$.
  5. A vertex adjacent only to $v_n$ and $s'$.

These additions are essentially equivalent to declaring, one at a time, that we are forced to use the edges $sv_1, v_1v_2, \dots, v_{n-1}v_n$, $v_ns'$.

If $H_1$ had a Hamiltonian $s,t$-path (which must contain the edge $ss'$) then $H_2$ has a path which uses all of these edges, and therefore at every step of the procedure above, we will keep finding a Hamiltonian path. Conversely, if we do find a Hamiltonian path that uses all these edges, then replacing these edges by the edge $ss'$ gives us a Hamiltonian path in $H_1$.

Therefore our algorithm will find a Hamiltonian $s,t$-path in $H_1$ - and then in $H$, which was arbitrary.


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.