There is an easy way to partition the set of s-t paths in a graph G. Fix an edge tt′ in G. Let P1 be the set of paths from s to t which use the edge tt′, and let P2 be the set of paths from s to t in G−tt′. Then P1capP2=emptyset and the set of s-t paths P=P1cupP2. Moreover, there is a one to one correspondence between the set of paths P1 and the set of s-t′ paths in the graph G−t.
Thus, we get an easy recursive algorithm to find the set of paths s-t paths in a graph G. Pick an edge tt′ incident the vertex t and recursively calculate the sets P1 and P2. With a small amount of pre-processing, we can ensure that the runtime is O(m(p+1)) where m is the number of edges and p is the number of s-t paths.
To make the recurrence relation on the runtime work, consider the following. We can test in time O(m) if a given graph G and pair of vertices s and t if G has 0, exactly one, or at least two distinct s-t paths. To see this, simply find the block decomposition of the graph and, and check if there is any non-trivial block between s and t in the tree.
We can push this slightly farther. Given an instance of the problem G and vertices s and t, we can reduce the problem in time O(m) to a graph barG and vertices x and y such that for all edges xx′ incident to x, we have that
- xx′ is in some y-x path,
- there exists a y-x′ path in barG−x.
To see this, again using the block decomposition, we contract any bridge in the graph and delete edges not contained in any s-t path. As above, this can be done in O(m) time.
We give an O(m(p−1)) time algorithm to find the set of s-t paths in a given graph G with at least two s-t paths.
- We may assume, as above, that every edge tt′ incident to t is contained in some s-t path and that there exists at least one s-t′ path in G−t.
- Check if the number of s-t paths in G−tt′ is at least two, and if not, let P1 be the set of the unique s-t path in G−tt′. If there are at least two such paths, we recursively find the set of all such paths. Let p1=|P1|. By choice of tt′, p1ge1.
- Check if the number of s-t′ paths in G−t is at least two, and if not let P2 be the set of the unique s-t′ path in G−t. Otherwise, we recursively find the set P2 of s-t′ path in G−t. Let p2=|P2|, and as above, we again have p2ge1.
Step 1 can be performed in c′m operations for some constant c′. The initial check in steps 2 and 3 can be performed in c′(m−1) steps. If we must recursively run the algorithm, this will require another c(m−1)(pi−1) operations for i=1,2 in Steps 2 and 3, respectively. As pige1, we can bound the work in each of Steps 2 and 3 by c′m+cm(pi−1). Thus, the total number of operations is at most 3c′m+c(m)(p1+p2−2)lecm(p−1) if we choose cge3c′.
No comments:
Post a Comment