Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Is there a path finding algorithm that exploits a directed bipartite graphs' structure?
I found this: Shortest-Path for Weighted Directed Bipartite Graphs but it didn't seem like the OP needed a bipartite graph and the answer reflected that.
I also found this: https://www.degruyter.com/downloadpdf/j/comp.2013.3.issue-4/s13537-013-0110-4/s13537-013-0110-4.pdf but it's not clear whether the solution is performant and I also don't have a APSP problem.
Clearly, an algorithm that runs on bipartite graphs only can't be slower than an algorithm that works on any graph. Therefore, the bipartite-shortest-path problem is in P.
In the opposite direction, consider a transformation that splits every edge into a pair of edges. It results in a bipartite graph and it preserves shortest paths. Therefore, any algorithm that can find the shortest path in a bipartite graph with v+e vertices and 2e edges can also find the shortest path in an arbitrary graph with v vertices and e edges.
Time complexity of Dijkstra's algorithm is O(e + v log v), so any performance improvement gained by a bipartite-shortest-path algorithm over a regular algorithm is limited to the constant factor of 2. Any faster, and it supersedes the regular algorithm entirely.
The Wikipedia page on the shortest path problem lists several special cases but never mentions bipartite graphs even in passing. It does include an algorithm from 2004 which reduces the time complexity to just O(e + v log log v).
Conclusion: There most likely is no known algorithm for bipartite path search that improves upon the best known algorithm for path search on arbitrary graphs. There is also no room for such improvement in terms of algorithmic complexity, and for only a factor of two in terms of runtime (treating log(log v) as a constant).
