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