Ripatti's blog

By Ripatti, 8 years ago, translation, In English,
Author thanks adamax for translation this article into English.

Introduction
After Codeforces Beta Round #11 several participants expressed a wish to read something about problems similar to problem D of that round. The author of this article, for the purpose of helping them, tried searching for such information, but to his surprise couldn't find anything on the Internet. It is not known whether the search was not thorough or there's really nothing out there, but (just in case) the author decided to write his own article on this topic.

In some sense this article may be regarded as a tutorial for the problem D from Beta Round #11.



In this article quite well-known algorithms are considered: the search for optimal Hamiltonian walks and cycles, finding their number, check for existence and something more. The so-called "dynamic programming over subsets" is used. This method requires exponential time and memory and therefore can be used only if the graph is very small - typically 20 vertices or less.

DP over subsets
Consider a set of elements numbered from 0 to N - 1. Each subset of this set can be encoded by a sequence of N bits (we will call this sequence "a mask"). The i-th element belongs to the subset if and only if the i-th bit of the mask equals 1. For instance, the mask 00010011 means that the subset of the set [0... 7] consists of elements 0, 1 and 4. There are totally 2N masks, and so 2N subsets. Each mask is in fact an integer number written in binary notation.

The method is to assign a value to each mask (and, therefore, to each subset) and compute the values for new masks using already computed values. As a rule, to find the value for a subset A we remove an element in every possible way and use values for obtained subsets A'1, A'2, ... , A'k to compute the value for A. This means that the values for Ai' must have been computed already, so we need to establish an ordering in which masks will be considered. It's easy to see that the natural ordering will do: go over masks in increasing order of corresponding numbers.

We will use the following notation:
bit(i, mask) - the i-th bit of mask
count(mask) - the number of non-zero bits in mask
first(mask) - the number of the lowest non-zero bit in mask
(a?b: c) - returns b if a holds, or c otherwise.
The elements of our set will be vertices of the graph. For the sake of simplicity we'll assume that the graph is undirected. Modification of the algorithms for directed graphs is left as an exercise for the reader.

1. Search for the shortest Hamiltonian walk
Let the graph G = (V, E) have n vertices, and each edge have a weight d(i, j). We want to find a Hamiltonian walk for which the sum of weights of its edges is minimal.

Let dp[mask][i] be the length of the shortest Hamiltonian walk in the subgraph generated by vertices in mask, that ends in the vertex i.

The DP can be calculated by the following formulas:
dp[mask][i] = 0, if count(mask) = 1 and bit(i, mask) = 1;
, if count(mask) > 1 and bit(i, mask) = 1;
dp[mask][i] = ∞ in other cases.

Now the desired minimal length is . If pmin = ∞, then there is no Hamiltonian walk in the graph. Otherwise it's easy to recover the walk itself. Let the minimal walk end in the vertex i. Then the vertex j ≠ i, for which , is the previous vertex in the path. Now remove i from the set and find the vertex previous to j in the same way. Continuing this process until only one vertex is left, we'll find the whole Hamiltonian walk.

This solution requires O(2nn) of memory and O(2nn2) of time.

2. Finding the number of Hamiltonian walks
Let the graph G = (V, E) be unweighted. We'll modify the previous algorithm. Let dp[mask][i] be the number of Hamiltonian walks on the subset mask, which end in the vertex i. The DP is rewritten in the following way:
dp[mask][i] = 1, if count(mask) = 1 and bit(i, mask) = 1;
, if count(mask) > 1 and bit(i, mask) = 1;
dp[mask][i] = 0 in other cases.

The answer is .

This solution requires O(2nn) of memory and O(2nn2) of time.

3. Finding the number of simple paths
Calculate the DP from the previous paragraph. The answer is . The coefficient 1 / 2 is required because each simple path is considered twice - in both directions. Also note that only paths of positive length are taken into account. You can add n zero-length paths, of course.

This solution requires O(2nn) of memory and O(2nn2) of time.

4. Check for existence of Hamiltonian walk
We can use solution 2 replacing the sum with bitwise OR. dp[mask][i] will contain a boolean value - whether there exists a Hamiltonian walk over the subset mask which ends in the vertex i. DP is the following:
dp[mask][i] = 1, if count(mask) = 1 and bit(i, mask) = 1;
, if count(mask) > 1 and bit(i, mask) = 1;
dp[mask][i] = 0 in other cases.

This solution, like solution 2, requires O(2nn) of memory and O(2nn2) of time. It can be improved in the following way.

Let dp'[mask] be the mask of the subset consisting of those vertices j for which there exists a Hamiltonian walk over the subset mask ending in j. In other words, we 'compress' the previous DP: dp'[mask] equals . For the graph G write out n masks Mi, which give the subset of vertices incident to the vertex i. That is, .

DP will be rewritten in the following way:
dp'[mask] = 2i, if count(mask) = 1 and bit(i, mask) = 1;
, if count(mask) > 1;
dp'[mask] = 0 in other cases.

Pay special attention to the expression . The first part of the expression is the subset of vertices j, for which there exists a Hamiltonian walk over the subset mask minus vertex i, ending in j. The second part of the expression is the set of vertices incident to i. If these subsets have non-empty intersection (their bitwise AND is non-zero), then it's easy to see that there exists a Hamiltonian walk in mask ending in the vertex i.

The final test is to compare dp[2n - 1] to 0.

This solution uses O(2n) of memory and O(2nn) of time.

5. Finding the shortest Hamiltonian cycle
Since we don't care at which vertex the cycle starts, assume that it starts at 0. Now use solution 1 for the subset of vertices, changing the formulas in the following way:
dp[1][0] = 0;
, if i > 0, bit(0, mask) = 1 and bit(i, mask) = 1;
dp[mask][i] = ∞ in other cases.

So dp[mask][i] contains the length of the shortest Hamiltonian walk over the subset mask, starting at 0 and ending at i.

The required minimum is calculated by the formula . If it equals , there is no Hamiltonian cycle. Otherwise the Hamiltonian cycle can be restored by a method similar to solution 1.

6. Finding the number of Hamiltonian cycles
Using ideas from solutions 5 and 2 one can derive a DP calculating the number of Hamiltonian cycles requiring O(2nn2) of time and O(2nn) of memory.

7. Finding the number of simple cycles
Let dp[mask][i] be the number of Hamiltonian walks over the subset mask, starting at the vertex first(mask) and ending at the vertex i. DP looks like this:
dp[mask][i] = 1, if count(mask) = 1 and bit(i, mask) = 1;
, if count(mask) > 1, bit(i, mask) = 1 and i ≠ first(mask);
dp[mask][i] = 0 otherwise.

The answer is .

This solution requres O(2nn2) of time and O(2nn) of memory.

8. Checking for existence of Hamiltonian cycle
We can modify solution 5 and, using the trick from solution 4, obtain an algorithm requiring O(2nn) of time and O(2n) of memory.

Exercises
CFBR11D
CCTOOLS

P.S. This article may be extended and fixed in future. The author would be grateful for supplementing the Exercises section and for pointing out any mistakes and inaccuracies.
 
 
 
 
  • Vote: I like it  
  • +22
  • Vote: I do not like it  

8 years ago, # |
  Vote: I like it +3 Vote: I do not like it
http://www.spoj.pl/problems/ASSIGN/

For example
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    спасибо, задача очень понравилась)) действительно, дп по подмножествам, только вот без графов и маршрутов в них. поэтому пока не знаю, стоит добавлять ее в статью или нет.

    пусть пока повисит тут. потом, возможно, добавлю. возможно в новый раздел:)
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice tutorial. You could also add an explanation on how to count hamiltonian circuits on a grid of size n x m with (n <= 7 and m <= 10^9) for example which is also fairly classical.
  • 8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Counting hamiltonian circuits on a grid is quite different from problems which was viewed there. In article I view foremost masks over subsets and paths in graphs. But in your problem motzkin words and matrix multiplication are used:)

    Maybe I will view your problem in fiture article:)
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    CouDo you have a reference to such a problem?
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      http://www.cs.ust.hk/mjg_lib/Library/Kwong_Ham_94.pdf
      it is very old paper:)
  • 7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If the size of grid is 12*12 . Can we use DP over Subsets
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
http://www.codechef.com/problems/TOOLS
is an example problem for part 5.
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please further explain the recurrence in the first example (finding a shortest Hamiltonian walk)?

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The following paper is potentially useful as reference:

"A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, 1962. [citation, download]

It contains lots of preliminary analysis and at least the DP approaches described in 1. and 5. of your post. I believe the algorithm is actually called "Held–Karp algorithm" in academic literature, but it was described independently by Bellman et al. in another paper.

A list of optimal algorithms for TSP with better runtime complexity can be found here.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 4th section's second dp formulation second part, the condition stated is count(mask)>1 only. Isn't bit(mask, i) == 1 condition should also be included?

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody give me link to its implemented code for any of the above part. Rest I got stuck at bit masking in implementation. Thanks in advance whoever will give link.

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My solution for task D of CF beta round 11.

    Btw,am i the only one who can't see the solution of others in this contest?i can't even open my solution.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      me too, something is wrong today, I can't open submission code, including myself, now I can only open my "official" submissions.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes also just encountered this problem. Why I try to open my own solution I get "You are not allowed to view the requested page" error.

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I actually have theory now for why this is. I think problem D might have been used in the VK Cup Finals — Trial Contest, and so they blocked solutions so we could not see submission from people in that contest.

»
15 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In first Section, consider a graph with only two vertices and one edge of weight say w then the answer computed by the process, comes to be w but expected asnwer is 2*w as for a hamiltonian walk the starting and ending vertices must be same.

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

In the 7th section, how are those paths included in the answer where we use vertices v < first(mask). This means, if our bit representation of mask is 1101000, and we want to count no. of paths starting at first(mask)=3(3rd bit, 0-based indexing from right to left) and ending at vertex v=5(0-based indexing from right to left), how will paths like the one starting from vertex 3 to vertex 5 with vertex 0 on the way(and similar) be counted if we use the dp meaning given in section 7?