3
$\begingroup$

I got the following as an interview question:

Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the number of Hamiltonian paths from upper left to lower left: a path such that every vertex is visited only once, and (this follows from the first statement) such that each edge is used at most once.

The grid world is a 4x10 matrix (4 rows and 10 columns).

Is it really this hard?

Matrix method for counting Hamiltonian cycles

And:

Number of Hamiltonian Paths from Lower Left to Upper Right

These papers seem dated--94, 97--but are they really asking a question that qualifies for publishing in a combinatorical journal?

Then I ran into this: SO question: number of Hamiltonian paths

And am thinking dynamic programming, or divide and conquer...but it is really not clear how one would go about doing this. Is there a way to solve this problem in reasonable time?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If it's a non-trivial problem of a combinatorial nature and they make progress on it, then it definitely merits publication in a combinatorics journal. $\endgroup$ – Yuval Filmus Feb 8 '17 at 19:05
-1
$\begingroup$

I think a divide and conquer strategy is going to work here. The asymptotic runtime isn't great, but fortunately our graph is of fixed size. Pick some arbitrary node, $v$, and partition the rest of the nodes into two sets. The number of hamiltonian tours is the number of paths that start at the upper left, go through all nodes in the first side of the partition and end at $v$ multiplied by the number of paths that start at $v$, go through every node in the second half and end at the bottom left corner summed over every possible such partition. Recursively do this for each partition.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ There are $2^{n-2}$ ways to partition the remaing vertices once you have arbitrarily selected one, which means that you will create $2^{n-1}$ subproblems. That doesn't fall into the usual paradigm of divide-and-conquer, which seeks to do less work on each division. Or perhaps I misunderstood you proposed solution. $\endgroup$ – rici Feb 8 '17 at 23:44
  • $\begingroup$ How do you plan to partition the nodes into two sets? Do you plan to use a single partition, or to enumerate all partitions? If you pick a single partition, there's no reason to expect that every Hamiltonian path will spend its first half going through one partition, then the other half going through the other partition. If you enumerate all partitions at each recursive step, won't the running time be enormous, even for this fixed-size graph? $\endgroup$ – D.W.♦ Feb 9 '17 at 3:27
  • $\begingroup$ You have to enumerate all the partitions. Like I said, the asymptotic runtime is really bad, but I think this problem is NP-hard in general and you only have to do it for a fairly small graph. It is divide and conquer because when you recursively solve each partition, your problem size has gone down by roughly 1/2. Albeit, you have to do it exponentially many times. $\endgroup$ – user3543290 Feb 9 '17 at 7:53
  • $\begingroup$ @user3543290 think I'm going to take this to a professor, and return with some insight. $\endgroup$ – donlan Feb 9 '17 at 16:32
  • $\begingroup$ @bordeo please share what he/she says, I'd be interested to know. Particularly if there's a nice combinatoric answer. If you were asked to actually solve this on the spot in the interview for a given graph, I would think there must be, while my answer just gives an algorithm to answer the question in general. $\endgroup$ – user3543290 Feb 9 '17 at 20:33

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.