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

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?

• Given that it's a heuristics, not sure what kind of theoretical reasoning you expect. There is a simple intuition though. One of the reasons why you may fail to visit a vertex is because it'll have no edges. So to reduce the chance of this happening, selecting a vertex with the minimum degree seems like a good choice. Dec 10 '21 at 23:46
• @Dmitry well to me your reasoning would lead to the opposite conclusion: taking always the vertex with maximum degree. Also not all heuristics have no theoretical reasoning behind, take for example the greedy approximation for the knapsack problem Dec 11 '21 at 12:07
• to me your reasoning would lead to ... taking always the vertex with maximum degree. - Can you explain why? My reasoning is "if the vertex has a small degree, then by not taking it early, we risk visiting all its neighbors, which leads us to have no way to visit it. You may also try to only detect very low-degree vertices, but then you'll have a risk of encountering multiple such vertices at once". Good point about knapsack though (but this particular reasoning probably won't work due to approximation hardness: en.wikipedia.org/wiki/Longest_path_problem#Approximation) Dec 11 '21 at 16:11
• yes, I was wrong because using the maximum I think is a bad choice: using the best assett at the start, while maybe you can use it later and use the bad ones sooner namely the low degree vertices, seems not a good choice. Thank you for the link to the concept of approximation hardness! Dec 11 '21 at 16:35

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.

• Thank you for the answer! I wonder if going more in depth in the graph before choosing can increase the correctness of the algorithm without loosing too much efficiency, for example minimizing the sum of the degrees of a pair of vertices instead of one at a time, this can flip the choice in some cases I think Dec 11 '21 at 16:51
• My answer is not about minimizing the sum of the degrees of a pair of vertices. Two vertices are selected so that the effect of the choosing the first one with the least degree can be analyzed more formally. I would like to believe minimizing the sum of the degrees of a pair of vertices should increase the likelihood further. It should be a small and nice project to gain some empirical evidence for that proposition. Dec 11 '21 at 17:24
• yes yes, I know @John L. that your answer is not about that, I just wanted confirmation about the fact that this should work :-) Dec 11 '21 at 17:27