Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Metric Decompositions of Path-Separable Graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, \(\beta \)-decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by \(\beta >0\)) are likely to be “clustered” together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n-vertex graphs admit an \(O(\ln n)\)-padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184–193, 1996), and that excluded-minor graphs admit O(1)-padded decomposition (Klein et al., 25th annual ACM symposium on theory of computing, pp 682–690, 1993; Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485–497, 2004; Abraham et al., Proceedings of the 46th annual ACM symposium on theory of computing. STOC ’14, pp 79–88. ACM, New York, NY, USA, 2014). We design decompositions to the family of p-path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC ’06, pp 188–197, 2006) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p-path-separable n-vertex graph admits an \(O(\ln (p \ln n))\)-decomposition, which refines the \(O(\ln n)\) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. If we relax the balance constraint, and require that every S-flap U has size \(|U| \le 2|V|/3\), then two shortest paths suffice.

References

  1. Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, pp. 188–197 (2006)

  2. Abraham, I., Gavoille, C., Gupta, A., Neiman, O., Talwar, K.: Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. STOC ’14, pp. 79–88. ACM, New York, NY, USA (2014)

  3. Awerbuch, B., Peleg, D.: Sparse partitions. In: 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 503–513 (1990)

  4. Assouad, P.: Plongements lipschitziens dans \({ R}^{n}\). Bull. Soc. Math. France 111(4), 429–448 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: 37th Annual Symposium on Foundations of Computer Science, pp. 184–193. IEEE (1996)

  6. Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 762–771. SIAM (2005)

  7. Calinescu, G., Karloff, H.J., Rabani, Y.: Approximation algorithms for the 0-extension problem. SIAM J. Comput. 34(2), 358–372 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  8. Diot, E., Gavoille, C.: Path separability of graphs. In: Frontiers in Algorithmics, 4th International Workshop, FAW, pp. 262–273 (2010)

  9. Das, B., Sivakumar, R., Bharghavan, V.: Routing in ad hoc networks using a spine. In: Sixth International Conference on Computer Communications and Networks, pp. 1–20 (1997)

  10. Englert, M., Gupta, A., Krauthgamer, R., Räcke, H., Talgam-Cohen, I., Talwar, K.: Vertex sparsifiers: new results from old techniques. SIAM J. Comput. 43(4), 1239–1262 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485–497 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fakcharoenphol, J., Talwar, K.: Improved decompositions of graphs with forbidden minors. In: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 36–46 (2003)

  13. Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 534–543 (2003)

  14. Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25(2), 235–251 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kamma, L., Krauthgamer, R., Nguyen, H.L.: Cutting corners cheaply, or how to remove steiner points. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1029–1040 (2014)

  16. Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 119–132. IEEE (2006)

  17. Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geometric Funct. Anal. 15(4), 839–858 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  18. Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th Annual ACM Symposium on Theory of Computing, pp. 682–690 (1993)

  19. Lee, J.R., Naor, A.: Metric decomposition, smooth measures, and clustering (2004). Unpublished manuscript. http://www.cims.nyu.edu/~naor/homepagefiles/cluster

  20. Lee, J.R., Sidiropoulos, A.: Genus and the geometry of the cut graph. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pp. 193–201. Society for Industrial and Applied Mathematics (2010)

  21. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  22. Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9(2), 253–275 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  23. Rao, S.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In: Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300–306. ACM (1999)

  24. Talwar, K.: Bypassing the embedding: Algorithms for low dimensional metrics. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 281–290 (2004)

  25. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993–1024 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors thank Ittai Abraham, Alex Andoni, and Kunal Talwar for useful discussions during preliminary stages of this work.

Author information

Authors and Affiliations

  1. Weizmann Institute of Science, Rehovot, Israel

    Lior Kamma & Robert Krauthgamer

Authors
  1. Lior Kamma
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Krauthgamer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lior Kamma.

Additional information

Work supported in part by a US-Israel BSF Grant #2010418 and an Israel Science Foundation Grant #897/13.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kamma, L., Krauthgamer, R. Metric Decompositions of Path-Separable Graphs. Algorithmica 79, 645–653 (2017). https://doi.org/10.1007/s00453-016-0213-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0213-0

Keywords

Search

Navigation