deepkamal's blog

How to find total number of simple paths b/w every pair of nodes in polynomial time for directed graph ?
By deepkamal, history, 3 years ago, In English

So, I was looking at the editorial of 167E - Волшебники и пари, It askes us to find total number of simple paths from every node (with indegree zero) to every node (with outdegree zero). How do we solve this ?. Also can we solve for any given directed graph the total number of simple paths b/w every pair of nodes in polynomial time ?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

In that problem, the graph is acyclic and there are 600 vertices, so the simple O(N*M) dynamic programming should work (reorder vertices so that for all edges u->v u < v, then for each source initialize the array with zeroes, place 1 at the source and for each edge u -> v in increasing order of u do dp[v] += dp[u]).
In general graphs, the problem "how many simple paths exist between u and v" is #P-complete, according to a proof from the internet. (if the paths don't have to be simple, for a given path length they can be counted using matrix exponentiation)
I think the original problem can also be solved in O(log N) matrix multiplications of size N (by adding an edge from every sink to itself and squaring the matrix ceil(log2(N)) times)

→ Reply