Talk #3 - Hamiltonian Paths & bitDP Description: Discussing algorithms on finding Hamiltonian Paths in graphs efficiently Slogan: This time... it's personal. Presenters: Clara Nguyễn & Natalie Bogda Type: Class Presentation Date Originally Presented: 2019/04/04 Downloads: [ Slides (Formal) ] [ Slides (Original) ]

Hamiltonian Paths are paths that traverse through every vertex in graph exactly once. A particular problem, RainbowGraph, has put a huge emphasis on finding these. Finding them is trivial, but very timely if done via DFS. When considering Topcoder's 2 second timeout, brutal for this problem, we have to resort to another solution, the Held-Karp Algorithm implemented with a technique called bitDP.

bitDP (ビット動的計画法(どうてきけいかくほう) bitto dōteki keikakuhō, Lit. Bit Dynamic Programming) is only discussed in Japanese as a technique to solve variations of the Travelling Salesman Problem. It's used to implement the Dynamic Programming version of the Held-Karp Algorithm to run in O(2^N × N²) time, opposed to DFS's O(N!).

I like to think of this talk as a way of me telling a story. I had a challenge, and I tell the struggle of solving it. This is not an easy problem. Since I know Japanese, I went and desperately translated several webpages on information about bitDP in an effort to understand a more efficient solution. As of the day I gave this talk, there are no sites (searchable via Google) that give details on bitDP in English.

RainbowGraph is a graph problem that has you counting up the number of Hamiltonian Paths throughout the entire graph. There are a few things that make this a worthy challenge:

• Every vertex must be visited exactly once.
• Every vertex has a colour assigned to it. When you reach a colour in the graph, you must visit all vertices of the same colour before you can go to one of another colour.
• There can be 10 vertices that have a specific colour, and there can be a maximum of 10 possible colours. 100 vertices total.

Here is an example of what a graph might look like for this problem:
120 possible paths...

The "colour" aspect means that the typical DFS method of traversing the entire graph and counting paths will not work on this problem.

Solving RainbowGraph suddenly changes from being a simple DFS problem to being a two-step problem where:

1. You have to solve sub-graphs of vertices of each colour, finding the number of possible paths between all vertices in them.
2. Compute the number of possible combinations from all vertices in one colour to another.

This talk mainly focuses on the first part of the problem. I do not discuss the second part, as it would give an entire solution. This is also a lab assignment for Graduate Students taking Dr. James S. Plank's CS594 (Advanced Algorithms) course. He has a detailed way to complete the second half of the problem on this page.

Depth-First Search (DFS), or rather a particular modification of it, will let us solve this problem. But it is very slow.

We can think of this as a basis of DFS pseudocode:

function dfs(a) {
	visited[a] = true;

	if we visited all nodes in graph,
		return true;

	for b is 0 to n - 1
		if (visited[b] == false)
			dfs(b)

	//backtrack
	visited[a] = false;
}

DFS, in this sense, isn't O(|V + E|) like you may be used to. We are traversing every possible path combination from one vertex to every other. And we are calling this on every single vertex. This explodes into a factorial problem with a time complexity of O(N!).

Its performance doesn't look too good either...



At 10 nodes, you start to see how this is a problem. At 15, I'm fairly certain that this talk would end before that actually gets done. But when it does eventually get done, it'll give the right answer.

Oh! And it fails on Topcoder.

We need to look into the faults of DFS in order to improve on it. Let's look at slide 18:



Let's address these...

• "Multiple repeated function calls"
  
  DFS calls itself everytime you traverse the graph. Function calls provide overhead that may seem innocent at first, but eventually can bring your program to its doom.
  
  
• "Have to check whether we visited a vertex or not"
  
  It sounds silly, considering this is actually part of DFS itself, but look at the pseudocode for DFS. Most of it is about the visited variable. In a small function like this, which is being called potentially millions of times, removing a single line of code can show quite the impressive speedup. But what if we have a way to traverse all nodes without keeping track of visiting them?
  
  
• "Recursion"
  
  See point 1.
  
  
• "There are properties of these graphs we aren't taking advantage of"
  
  I'll get to this later on. But DFS is a naïve algorithm that doesn't care about the properties of a graph. It just brute-forces its way through all possible combinations.
  
  

Brainstorming a fast implementation

Lovely. So I'm done bashing DFS. Now let's talk about ways to try to make it faster... way faster:

• Dynamic Programming & Memoisation: Break the problem down into sub-problems and solve those. Store results in a "cache" of sorts.
  
  
• If A can go to B, than B can go to A: Cut traversals in half. The graph is undirected, so nodes can go to each other.
  
  
• Use Adjacency Matrix for O(1) lookups. Use Adjacency List for iteration: Store both an Adjacency Matrix and an Adjacency List. Use the appropriate one at the appropriate time.
  
  
• Eliminate recursion as much as possible: Get rid of function overhead. But can we eliminate recursion entirely?
  
  

Can we check all of the boxes? Sure why not.

There exists an algorithm written by Richard Bellman, Michael Held, and Richard Karp that can solve this kind of problem in non-factorial time. In this case, it hits O(2^N × N²) time. It is known as the Held-Karp Algorithm. It is also known as the "Bellman-Held-Karp Algorithm".



It's a dynamic programming algorithm that takes advantage of a property of graphs we test against, where we can split it up into sub-problems, solve those, and then merge the sub-problems together to make a single result.

Think about this. If we have a graph where A --> B, and B --> C, then there exists a path where A --> B --> C exists. This is how we will break the problem apart. Solve pairs, then solve groups of 3 nodes, then 4, etc all the way until we have all nodes in the graph. Obviously if a path exists that has all nodes in it, there is at least one Hamiltonian Path in the graph.

Representing sub-problems via bitDP

To fully take advantage of the Held-Karp algorithm, we need an effective means to represent sub-problems. Looking at the graph in slide posted above, there are 4 nodes. We can represent sub-problems in binary where 0 means the node doesn't exist and 1 means the node does exist. Since there are 4 nodes, there are 4 bits, which makes for 16 possible sub-problems (0000 to 1111). This is where bit masks are introduced. If I was dealing with 1001, that means that I have a graph with only the first and last nodes. If I was on 1111, I'd have a sub-problem that has all 4 nodes in it. Simple right?

What I have just explained is how to represent sub-problems as binary. However, we need to store them too. Introducing the bitDP table...

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

The rows are the vertices and the columns are the bit masks.

Now... there is a lot of information that can be stored here. And it can get to be confusing very fast. Therefore, I will demonstrate how to read an existing table first. Then I will explain how to generate one by hand.

Behold the filled out bitDP table for the graph above:

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	1	0	1	0	0	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	0	0	0	1	1
2	0	0	0	0	1	1	1	1	0	0	0	0	1	0	1	1
3	0	0	0	0	0	0	0	0	1	0	1	1	1	1	1	1

So, how exactly can we read this? Let's refer to Slide 25:


Each column is its own sub-problem. Values are set to 1 if there is a path that visits all nodes in the sub-problem once and ends at that node.

When looking at 0xB (which is 1011 in binary), we have a sub-problem consisting of 0, 1, and 3 nodes. But there are only 2 cells in that column that are set to "1". Look at the graph and consider those 3 nodes:

• There exists a path that ends at Node 0 (3 -> 1 -> 0).
• There is not a path that ends at Node 1.
• There exists a path that ends at Node 3 (0 -> 1 -> 3).

Thus, 0 and 3's cells are set to 1, while 1's cell is set to 0.

Let's start out with a clean table. Here we go.

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Step 1: Initial Setup

The first step is to look at columns where the binary Hamming Weight (number of bits set to 1) is 1. Since those sub-problems only have 1 node in them, they are "1" by default. This is for 0001, 0010, 0100, and 1000.

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

Step 2: Column Generation

Next, we will start generating cell values on a column-by-column basis. This will apply for all columns where the binary Hamming Weight is 2 or more. Therefore, we will skip 0-2 and start at mask 0x3 (0011). Here is how our graph will look:


The nodes that are not in the mask are transparent. Since it's mask 0x3, only nodes 0 and 1 are involved.

Remember how we talked about how if A --> B and B --> C, then there exists a path of A --> B --> C? We can take advantage of this property by using this table.

For all nodes involved (0 and 1), rather than check paths by using a DFS or brute force method, we can cheat and use previous columns to check if there is a path that exists and goes to the cell in question. This is better taught by example so...

For Node 0:

• Go to mask of same value except without node 0 (0011 XOR 0001 = 0010)
• At mask 0010, check all cells set to 1 and see if those vertices can go to 0.
• Vertex 1 at mask 0010 is set to "1" and it can go to 0. Set the cell to 1.

This is our table currently. Notice something new?

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

Why this works: We go to a mask where we know there is a path between certain nodes that exist, but doesn't include the one we are checking (mask 0010 doesn't have node 0). Then we see if any of the nodes in that mask can go to that node. If there is a path from any node to it, set it to 1.

Even more simply put: If we were checking for a path for C, and we know there's a path of A --> B and B --> C, go to the mask that doesn't have C and check if either A or B go to C. If either does, we know a path exists between all 3.

So we did the part for Node 0, but mask 3 also involves Node 1. So let's do that one too.

For Node 1:

• Go to mask of same value except without node 1 (0011 XOR 0010 = 0001)
• At mask 0001, check all cells set to 1 and see if those vertices can go to 1.
• Vertex 0 at mask 0001 is set to "1" and it can go to 1. Set the cell to 1.

And here's our updated table:

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

Perfect! Repeat the procedure for all cells of all columns where the Hamming Weight is 2 or more and you're done. This means you'll be doing this procedure for the following columns: 5, 6, 7, 9, A, B, C, D, E, F. That's pretty tedious.

Here's the completed table, once again.

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	1	0	1	0	0	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	0	0	0	1	1
2	0	0	0	0	1	1	1	1	0	0	0	0	1	0	1	1
3	0	0	0	0	0	0	0	0	1	0	1	1	1	1	1	1

Step 3: Determining a Hamiltonian Path's existence

Let's look at mask F (1111) again. If there are any 1's in that column, there exists a Hamiltonian Path in the graph! But that's not all. We can also determine where the path ends from the table. If the first cell at the top is "1", then there exists a Hamiltonian Path that ends at Vertex 0.

From what I can see, all 4 cells in that column are set to "1". This means there are Hamiltonian Paths that end at all vertices in the graph! That's pretty nice, but there are a few problems to this approach for the problem we are trying to solve...

A few problems

There are a two problems with this approach when considering RainbowGraph...

• RainbowGraph doesn't care if we can determine whether a Hamiltonian Path exists or not. It cares about how many there are.
• We know how to determine if a Hamiltonian Path exists, as well as what vertex it ends at. But we don't know where such paths started.

Thankfully, there is a way to fix it. And it's quite simple as well. However, we will lose the O(2^N × N²) time complexity. Instead, it'll become O(2^N × N³). That's not so bad.

Modification 1: Finding a starting vertex

We can force the table to tell us the starting vertex by simply increasing the number of tables we have. For this to work, we will modify Step 1 from the previous section... the initial setup.

Recall that this is what the initial step looked like before:

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

Since there are 4 nodes in the graph, there will be 4 tables instead. And the "1"s will be split among them. This will get tedious very quickly.

dp[0] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp[3] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

That's it! That's the only modification that had to be made. For each of those tables, run Step 2...

dp[0] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
dp[3] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

Why does this matter? Well because we forced a starting vertex by splitting tables, we can figure out if there's a path from point A to point B and vice versa. I labeled the tables above as dp[0..3]. The number represents the starting vertex. The row in the table represents the ending vertex.

If I wanted to determine if there was a Hamiltonian Path between node 0 and 1, I'd look at dp[0], go to the last column, and look at the second column. Easy enough.

Modification 2: Get number of Hamiltonian Paths rather than determining if one exists.

There is a minor detail in Step 2 that can be modified for this to work. Instead of setting a cell to 1, add the value of the cell we were on. So when on Mask 0011, Node 0, we go to mask 0010 and look at Vertex 1 and see it goes to Vertex 0. Thus, we add the value of 0010's Vertex 1 cell to 0011's Vertex 0 cell. This will give you the total paths, in the end.

There isn't much to show with this method. In code, it's a change to a single line of code. Here's the final result, with notable changes being coloured:

dp[0] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 2
dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
dp[3] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 2 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

We can verify these results with our eyes. Starting from Vertex 0, there are 2 Hamiltonian Paths that go to Vertex 3:

• 0 -> 1 -> 2 -> 3
• 0 -> 2 -> 1 -> 3

The same goes for going from Vertex 3 to Vertex 0. Just flip the paths.

We now have our secret weapon prepared. Let's compare performance. Slide 37 has a pretty nice graph on this:


It's no competition. The Held-Karp Algorithm completely destroys DFS. I am pretty confident that it'll pass Topcoder's 70 test cases with absolutely no stru- oh...


Well that kind of sucks... Okay let's see what else we can do.

All of that hard work got us really close to solving RainbowGraph. But "close" isn't really good enough. Thankfully, the method we discussed above can be optimised. I'll briefly discuss methods on making this nearly three times faster.

Optimisation 1: "If A can go to B, than B can go to A."

Remember how we split up the bitDP table by starting vertex? This actually gives bitDP another property that a clever eye can spot. Observe the 2 following bitDP tables:

dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1

I've highlighted rows that you should pay attention to. They are the same! dp[x][y] is the same as dp[y][x]. This means we can cut out exactly half of the computations needed to generate the tables.

Optimisation 2: We can skip computations by being clever

I very briefly go over this in the talk, but there are places in the table that are guaranteed to be 0 no matter the circumstance. I'll highlight them here:

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	1	0	1	0	0	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	0	0	0	1	1
2	0	0	0	0	1	1	1	1	0	0	0	0	1	0	1	1
3	0	0	0	0	0	0	0	0	1	0	1	1	1	1	1	1

These cells are never accessed. In fact, any cell that comes before an initial "1" for a vertex is guaranteed to never be accessed. For graphs of 5 nodes, the first 16 cells of the last row are "0". It increases exponentially.

Splitting the bitDP tables by starting vertex gives us another opportunity to skip computations as well. Rows of the same index as the starting vertex are guaranteed to only have one "1"... The initial cell from step 1. So dp[1][1], dp[2][2], etc can be skipped entirely.

Speed Improvement Comparison

Now let's compare bitDP with our optimised bitDP (I name it "bitDP v2").


Does it pass Topcoder? Yes! Finally.