Finding all paths on undirected graph

There is an easy way to partition the set of $s$-$t$ paths in a graph $G$. Fix an edge $tt'$ in $G$. Let $P_1$ be the set of paths from $s$ to $t$ which use the edge $tt'$, and let $P_2$ be the set of paths from $s$ to $t$ in $G-tt'$. Then $P_1 cap P_2 = emptyset$ and the set of $s$-$t$ paths $P = P_1 cup P_2$. Moreover, there is a one to one correspondence between the set of paths $P_1$ 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 $P_1$ and $P_2$. 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 $bar{G}$ and vertices $x$ and $y$ such that for all edges $xx'$ incident to $x$, we have that

1. $xx'$ is in some $y$-$x$ path,


2. there exists a $y$-$x'$ path in $bar{G}-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.

1. 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$.


2. Check if the number of $s$-$t$ paths in $G-tt'$ is at least two, and if not, let $P_1$ 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 $p_1 = |P_1|$. By choice of $tt'$, $p_1 ge 1$.


3. Check if the number of $s$-$t'$ paths in $G-t$ is at least two, and if not let $P_2$ be the set of the unique $s$-$t'$ path in $G-t$. Otherwise, we recursively find the set $P_2$ of $s$-$t'$ path in $G-t$. Let $p_2 = |P_2|$, and as above, we again have $p_2 ge 1$.

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)(p_i - 1)$ operations for $i = 1, 2$ in Steps 2 and 3, respectively. As $p_i ge 1$, we can bound the work in each of Steps 2 and 3 by $c'm + cm(p_i - 1)$. Thus, the total number of operations is at most $3c'm + c(m)(p_1 +p_2 - 2) le cm(p-1)$ if we choose $c ge 3c'$.

• Next lo.logic - Graph properties and infinite FOL sentences
• Previous nt.number theory - How natural is the reciprocity map?