The Art Gallery Guardian

Reconstructing edge-disjoint paths, a tighter analysis


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

0.0.0.0.0.1

Given a simple undirected graph of nn vertices and mm edges, construct a data structure such that we can query two vertices uu and vv, and it returns the maximum edge disjoint paths between uu and vv.

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

The current state of art in the article is:

  1. Proprocessing time O(nMF(n,m))O(nMF(n,m)).
  2. O(n3)O(n^3) space.
  3. O(α(n)λ(u,v)n)O(\alpha(n)\lambda(u,v)n) query time.

We can improve this by having a tighter analysis.

First, if ff and gg be kk-edge disjoint path from xx to yy and yy to zz respectively. Let mm be the number of edges in fgf\cup g, then there exist an algorithm to output kk-edge disjoint path from xx to zz in O(m)O(m) time. One can see this by update section 22 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 ff uses only O(fn)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(n2.5logn)O(n^{2.5}\log n) space and get a query time of O(λ(u,v)n)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))O(nMF(n,m)).
  2. O(n2.5logn)O(n^{2.5}\log n) space.
  3. O(λ(u,v)n)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))O(nMF(n,m)).
  2. O(mn3/2logn)O(\sqrt{m}n^{3/2}\log n) space.
  3. O(kn)O(\sqrt{k}n) query time for a kk edge disjoint path from uu to vv.

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 2014-11-02.
Tags: combinatorial optimization.