Counting Number of Paths (Length N) in Bipartite Graph

Question

I am currently counting the number of paths of length $n$ in a bipartite graph by doing a depth first search (up to 10 levels). However, my implementation of this takes 5+ minutes to count 7 million paths of length 5 from a bipartite graph with 3000+ elements. I am looking for a more efficient way to do this counting problem, and I am wondering if there is any such algorithm in the literature.

These are undirected bipartite graphs, so there can be cycles in the paths.

My goal here is to count the number of paths of length $n$ in a bipartite graph of 1 million elements under a minute.

Thank you in advance for any suggested answers.

Answer 1

I agree with the first idea but it's not quite a BFS. In a BFS you go through each node once, here you can go a large number of times.
You have to keep 2 arrays (let's call it Cnt1, and Cnt2, Cnt1 is the number of times you have reached an element and you have a path of length i, and Cnt2 is the same but for length i + 1). First time all the elements are 0 in Cnt2 and 1 in Cnt1( because you have one path of length zero starting at each node).

Repeat N times:
Go through all the nodes
For the current node you go through all his connected nodes and for each you add at there position on Cnt2 the number of times you reached the current node in Cnt1.
When you finished all the nodes you just Copy Cnt2 in Cnt1 and make Cnt2 zero.
At the end you just add all the numbers of Cnt1 and that is the answer.

Answer 2

Convert to a breadth-first search, and whenever you have 2 paths that lead to the same node at the same length, just keep track of how many such ways there are and not how you got there.

This will avoid a lot of repeated work and should provide a significant speedup. (If n is not small, there are better speedups, read on.)

My goal here is to count the number of paths of length n in a bipartite graph of 1 million elements under a minute.

Um, good luck?

An alternate approach to look into is if you take the adjacency matrix of the graph, and raise it to the n'th power, all of the entries of the matrix you get are the number of paths of length end starting in one place, ending in another. So you can take shortcuts like repeated squaring. Convenient, isn't that?

Unfortunately a million element graph gives rise to an adjacency matrix with 10^12 entries. Multiplying two such matrices with a naive algorithm should require 10^18 operations. Of course we have better matrix multiplication algorithms, but you're still not getting below, say, 10^15 operations. Which will most assuredly not complete in 1 minute. (If your matrix is sparse enough you might have a chance, but you should do some researching on the topic.)