# Reconstructing edge-disjoint paths, a tighter analysis

This is a small improvement of the analysis of [1], this assume you already read that paper.

Given a simple undirected graph of $n$ vertices and $m$ edges, construct a data structure such that we can query two vertices $u$ and $v$, and it returns the maximum edge disjoint paths between $u$ and $v$.

We let $MF(n,m)$ to be the time to compute $st$-maximum flow on a undirected unit capacity graph.

The current state of art in the article is:

- Proprocessing time $O(nMF(n,m))$.
- $O(n_{3})$ space.
- $O(α(n)λ(u,v)n)$ query time.

We can improve this by having a tighter analysis.

First, if $f$ and $g$ be $k$-edge disjoint path from $x$ to $y$ and $y$ to $z$ respectively. Let $m$ be the number of edges in $f∪g$, then there exist an algorithm to output $k$-edge disjoint path from $x$ to $z$ in $O(m)$ time. One can see this by update section $2$ of their paper by using a stable matching algorithm without the dummy edges, because this is just stable matching with incomplete lists[2].

Second, acyclic flow of value $f$ uses only $O(f n)$ edges(Theorem 3.1 in [3]), therefore we do not have to store any non-acyclic flows. This also speed up all computations because the number of edges are smaller.

Third, we can use $O(n_{2.5}gn)$ space and get a query time of $O(λ(u,v) n)$. In fact there is a time space trade off [4].

Thus finally, we get

- Proprocessing time $O(nMF(n,m))$.
- $O(n_{2.5}gn)$ space.
- $O(λ(u,v) n)$ query time.

With even better analysis, we can obtain the following [5].

- Proprocessing time $O(nMF(n,m))$.
- $O(m n_{3/2}gn)$ space.
- $O(k n)$ query time for a $k$ edge disjoint path from $u$ to $v$.

# References

**Reconstructing edge-disjoint paths**, Operations Research Letters. 31 (2003) 273–276 10.1016/S0167-6377(03)00022-1.

**Finding maximum flows in undirected graphs seems easier than bipartite matching**, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing - STOC ’98. (1998) 69–78 10.1145/276698.276714.

**Optimal preprocessing for answering on-line product queries**, Tel Aviv University, 1987.

**Reconstructing edge-disjoint paths faster**, Operations Research Letters. 44 (2016) 174–176 https://doi.org/10.1016/j.orl.2015.12.017.