CODEWITHSUNDEEP
algorithmgraphdynamic-programminggraph-theory
user16786403
user16786403

Reputation: 15

Find the number of simple paths from A to B going through a given point on the graph

I am looking into an interesting issue in networks.

Given an undirected graph which can contain cycles:

I choose two points, A and B as origin and end of my paths. My goal is to calculate how many simple paths go through each of the other nodes in the graph.

For example, in this graph: In this graph

there are 4 simple paths from 0 to 4. Node 3 has a count of 4, nodes 1 and 2 have a count of 2.

Brute forcing this is impossible, since it would require finding all simple paths, which is on the order of O(n!). I tried to make a variation of the Floyd–Warshall algorithm, but I cannot find a good recursive formula - I can only manage to count all paths, not only simple ones.

Is there a solution to this problem in polynomial time?

Thank you!

Upvotes: 1

Views: 952

Answers (1)

templatetypedef
templatetypedef

Reputation: 373042

To the best anyone knows, no, there isn’t a polynomial-time algorithm for this problem. The problem of counting how many s-t simple paths there are in a graph - not even listing them, just counting them - is #P-complete. Since a polynomial-time algorithm for a #P-complete problem would prove P = NP, there are no known polynomial-time algorithms for this problem.

Upvotes: 1

Related Questions