Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?

Question

Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the adjacent vertex with the least degree; there are also strategies to manage tiebreaks but I think they are even more difficult to explain.

I would like to ask: are there theoretical reasonings which explain why it's a good heuristic or is the rule just an experimental one?

Answer 1

Here is the simple reason. A graph with more edges is more likely to have a Hamiltonian path.

---

Let us see how that simple reason is applied in detail.

Suppose we want to find a Hamiltonian path in $G$. Suppose we have selected made some initial choices, i.e., we have selected some path $v_0, v_1, \cdots, v_k$.

Suppose we extend the path by two more vertices. There are the two ways of our concern. .

1. Select $r_1$, the vertex of least degree among the vertices adjacent to $v_k$, as $v_{k+1}$. Selected some vertex $r_2$ as $v_{k+2}$.
2. Select $m_1$, a vertex not of least degree among the vertices adjacent to $v_k$, as $v_{k+1}$. Selected some vertex $m_2$ as $v_{k+2}$.

Consider the remaining problem after we have selected $v_{k+1}$ and $v_{k+2}$.

In the first way, the problem is to find a Hamiltonian path in $G$ with vertices $v_0, v_1, \cdots, v_k, r_1$ removed, starting from $r_2$.

In the second way, the problem is to find a Hamiltonian path in $G$ with vertices $v_0, v_1, \cdots, v_k, m_1$ removed, starting from $m_2$.

Since the remaining graph in the first way has more edges than the remaining graph in the second way, we are more likely to succeed in the first way.

Can the difference in the starting point, $r_2$ or $m_2$ affect the likelihood respectively? Of course. However, it is hard to see how we can choose $m_2$ better in the neighborhood of $m_1$ than choose $r_2$ in the neighborhood of $r_1$. So, the choice of $r_2$ and the choice of $m_2$ is unlikely to flip the advantage of the first way.

---

This heuristic, choosing the adjacent vertex with the least degree, can be considered as an application of the principle "Most Constrained Variable first" in the domain of the problem of Constraint Satisfaction.