# Reconstructing edge-disjoint paths, a tighter analysis

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

Problem1

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:

1. Proprocessing time $O(nMF(n,m))$.
2. $O(n^3)$ space.
3. $O(\alpha(n)\lambda(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\cup 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(\sqrt{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}\log n)$ space and get a query time of $O(\sqrt{\lambda(u,v)}n)$. In fact there is a time space trade off [4].

Thus finally, we get

1. Proprocessing time $O(nMF(n,m))$.
2. $O(n^{2.5}\log n)$ space.
3. $O(\sqrt{\lambda(u,v)}n)$ query time.

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

1. Proprocessing time $O(nMF(n,m))$.
2. $O(\sqrt{m}n^{3/2}\log n)$ space.
3. $O(\sqrt{k}n)$ query time for a $k$ edge disjoint path from $u$ to $v$.

# References

[1] M. Conforti, R. Hassin, R. Ravi, Reconstructing edge-disjoint paths, Operations Research Letters. 31 (2003) 273–276 10.1016/S0167-6377(03)00022-1.

[2] K. Iwama, S. Miyazaki, Y. Morita, D. Manlove, Stable marriage with incomplete lists and ties, in: J. Wiedermann, P. van Emde Boas, M. Nielsen (Eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, 1999: pp. 443–452 10.1007/3-540-48523-6_41.

[3] D.R. Karger, M.S. Levine, 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.

[4] N. Alon, B. Schieber, Optimal preprocessing for answering on-line product queries, Tel Aviv University, 1987.

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

Posted by Chao Xu on .
Tags: combinatorial optimization.