Search code examples
algorithmgraphgraph-theory

Finding all edges that appear on at least one s-t path

I am looking for an algorithm to solve the following problem:

  • Input: Directed Graph G, nodes s and t
  • Output: Set of all edges that are part of a simple st-path

A path is simple if no node is visited twice.

Does somebody have an idea how to do this?

The problem is easy on DAGs as all paths are simple. However, the input graph is not a DAG. I believe that by using a strongly connected component algorithm, the problem can be reduced to the case where G is strongly connected. Unfortunately, I do not know how to proceed further. I'm even unsure whether the problem is polynomially solvable.

Solution

  • I've managed to figure out a polynomial-time algorithm for the undirected case. For the directed case, I don't have a full answer, but for reasons I'll outline below I have a weak hunch that the problem is NP-hard.

    The main insight I'm using is the following. Suppose you have a pair of nodes s and t and you want to determine whether the edge {u, v} appears on some simple path from s to v. This is equivalent to asking whether there are paths Psu and Pvt where Psu runs from s to u, Pvt runs from v to t, and Psu and Pvt have no nodes in common.

    This is a special case of a problem called the 2-distinct path problem. In that problem, you're given pairs of nodes (w, x) and (y, z) and are asked whether there are node-disjoint paths from w to x and from y to z. This problem has been studied since the 1970s, and we know that

    • there exists a polynomial-time algorithm for this problem in the undirected case, but that
    • the directed version of the problem is NP-hard.

    This means that, in the undirected case, we can solve your original problem as follows. Given nodes s and t, for each edge {u, v}, see whether there's a solution to the 2-distinct path problem from s to u and from v to t. If so, record that there is a simple path passing through {u, v}. At the end, report all edges you found this way. Using Tholey's algorithm as a black box solver for the 2-distinct path problem gives a total runtime of O(mn + m2 α(m, n)), where α(m, n) is the inverse Ackermann function.

    This approach could also be used in the directed case, except that the 2-distinct path problem is NP-hard for directed graphs, even if the one of the terminal nodes has a direct edge to the other start node. That by itself doesn't prove that your original problem is NP-hard because solving your problem doesn't immediately seem to give a way to determine whether there are two disjoint paths from s to t. However, the fact that it's this difficult to determine whether a single edge is on some s-t path is weak heuristic evidence that this is a hard problem.