StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In general, as the (decision version of the) Hamiltonian Path problem is NP-complete, you cannot hope to get a polynomial-time algorithm for finding Hamiltonian paths. You can slightly speed it up with the usual N! → N<sup>2</sup>2<sup>N</sup> dynamic programming trick (compute hp[v][w][S] = "is there a path that has endpoints v and w and whose vertices are the subset S" for every subset S and every two vertices v and w in it using DP), but that's still exponential.</p> <p>However, there are many special kinds of graphs for which Hamiltonian paths will always exist, and they can be found easily (see work of Posa, Dirac, Ore, etc.)</p> <p>For instance, the following is true: <em>If every vertex of the graph has degree at least n/2</em>, then the graph has a Hamiltonian path. You can in fact find one in O(n<sup>2</sup>), or IIRC even O(n log n) if you do it more cleverly.<br/> [Rough sketch: First, just connect all vertices in some "Hamiltonian" cycle, nevermind if the edges are actually in the graph. Now for every edge (v,w) of your cycle that is not actually in the graph, consider the rest of the cycle: v...w. As deg(v)+deg(w)>=n, there exist consecutive x,y in your list (in that order) such that w is a neighbour of x and v is a neighbour of y. [Proof: Consider {the set of all neighbours of w} and {the set of all successors in your list of neighbours of v}; they must intersect.] Now change your cycle [v...xy...wv] to [vy...wx...v] instead, it has at least one less invalid edge, so you'll need at most n iterations to get a true Hamiltonian cycle. More details <a href="http://cgm.cs.mcgill.ca/~perouz/cs251/documents/solutions6/solutions6.html" rel="noreferrer">here</a>.]</p> <p>BTW: if what you are looking for is just a walk that includes every <em>edge</em> once, it's called an Eulerian walk and for graphs that have it (number of vertices of odd degree is 0 or 2), one can quite easily be found in polynomial time (fast).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload