Document Open Access Logo

Retracting Graphs to Cycles

Authors Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.70.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Samuel Haney
  • Duke University, Durham, NC, USA
Mehraneh Liaee
  • Northeastern University, Boston, MA, USA
Bruce M. Maggs
  • Duke University, Durham, NC, USA
  • Akamai Technologies, Cambridge, MA, USA
Debmalya Panigrahi
  • Duke University, Durham, NC, USA
Rajmohan Rajaraman
  • Northeastern University, Boston, MA, USA
Ravi Sundaram
  • Northeastern University, Boston, MA, USA

Funding

All the authors were partially supported by NSF grant CCF 1535972. Additional funding information appears below.
  • Panigrahi, Debmalya: NSF grant CCF 1527084, an NSF CAREER Award CCF 1750140, and the Joint Indo-US Networked Center for Algorithms under Uncertainty.
  • Sundaram, Ravi: NSF grant CNS 1718286.

Acknowledgements

We would like to thank Seffi Naor for helpful discussions on the problems considered in this paper.

Cite AsGet BibTex

Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Retracting Graphs to Cycles. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.70

Abstract

We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner’s Lemma that rules out the possibility of improving this result using certain natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps by giving an optimal combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph algorithms
  • Graph embedding
  • Planar graphs
  • Approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mark Anthony Armstrong. Basic Topology. Springer Science &Business Media, 2013. Google Scholar
  2. Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In SODA, pages 119-128, 2005. Google Scholar
  3. Aaron Bernstein, Karl Däubel, Yann Disser, Torsten Mütze Max Klimm, and Frieder Smolny. Distance-Preserving Graph Contractions. In ITCS, 2018. Google Scholar
  4. A. Blum, G. Konjevod, R. Ravi, and S. Vempala. Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theoretical Computer Science, 235(1):25-42, 2000. Google Scholar
  5. Karol Borsuk. On retractions and related sets. PhD thesis, University of Warsaw, 1930. Google Scholar
  6. G. Calinescu, H. Karloff, and Y. Rabani. Approximation Algorithms for the 0-Extension Problem. SIAM Journal on Computing, 34(2):358-372, 2004. Google Scholar
  7. Chandra Chekuri, Sanjeev Khanna, Joseph Naor, and Leonid Zosin. A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM Journal on Discrete Math., 18:608-625, 2004. Google Scholar
  8. J. Chuzhoy and J. S. Naor. The Hardness of Metric Labeling. SIAM Journal on Computing, 36(2):498-515, 2006. Google Scholar
  9. Chandan K. Dubey, Uriel Feige, and Walter Unger. Hardness results for approximating the bandwidth. Journal of Computer and System Sciences, 77(1):62-90, 2011. Google Scholar
  10. John Dunagan and Santosh Vempala. On Euclidean Embeddings and Bandwidth Minimization. In APPROX-RANDOM, pages 229-240, 2001. Google Scholar
  11. Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An Improved Approximation Algorithm for the 0-extension Problem. In SODA, pages 257-265, 2003. Google Scholar
  12. T. Feder, P. Hell, P. Jonsson, A. Krokhin, and G. Nordh. Retractions to Pseudoforests. SIAM Journal on Discrete Mathematics, 24(1):101-112, 2010. Google Scholar
  13. Tomas Feder and Pavol Hell. List Homomorphisms to Reflexive Graphs. Journal of Combinatorial Theory, 72(2):236-250, 1998. Google Scholar
  14. Uriel Feige. Approximating the Bandwidth via Volume Respecting Embeddings. Journal of Computer and System Sciences, 60(3):510-539, 2000. Google Scholar
  15. Anupam Gupta. Improved Bandwidth Approximation for Trees. In SODA, pages 788-793, 2000. Google Scholar
  16. Eitan M. Gurari and Ivan Hal Sudborough. Improved Dynamic Programming Algorithms for Bandwidth Minimization and the MinCut Linear Arrangement Problem. Journal of Algorithms, 5(4):531-546, 1984. Google Scholar
  17. Geňa Hahn and Claude Tardif. Graph homomorphisms: structure and symmetry, pages 107-166. Springer Netherlands, 1997. Google Scholar
  18. Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Rajmohan Rajaraman, Debmalya Panigrahi, and Ravi Sundaram. Retracting Graphs to cycles. CoRR, 2019. URL: http://arxiv.org/abs/1904.11946.
  19. Mark D. Hansen. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In FOCS, pages 604-609, 1989. Google Scholar
  20. Stephan Held, Bernhard Korte, Dieter Rautenbach, and Jens Vygen. Combinatorial Optimization in VLSI Design. In Combinatorial Optimization - Methods and Applications, pages 33-96. IOS Press, 2011. Google Scholar
  21. P. Hell and J. Nesetril. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, 2004. Google Scholar
  22. J.G. Hocking and G.S. Young. Topology. Addison-Wesley series in mathematics. Dover Publications, 1961. Google Scholar
  23. Matoušek J. Embedding Finite Metric Spaces into Normed Spaces. In Lectures on Discrete Geometry, Graduate Texts in Mathematics, volume 212. Springer, 2002. Google Scholar
  24. H. Karloff, S. Khot, A. Mehta, and Y. Rabani. On Eathmover Distance, Metric Labeling, and 0-Extension. SIAM Journal on Computing, 39(2):371-387, 2009. Google Scholar
  25. A. V. Karzanov. Minimum 0-extension of graph metrics. European Journal of Combinatorics, 19:71-101, 1998. Google Scholar
  26. Claire Kenyon, Yuval Rabani, and Alistair Sinclair. Low Distortion Maps Between Point Sets. SIAM Journal on Computing, 39(4):1617-1636, 2009. Google Scholar
  27. J. Kleinberg and É Tardos. Approximation algorithms for classification problems with pairwise relationships. Journal of the ACM, 49:616-639, 2002. Google Scholar
  28. Jiří Matoušek and Anastasios Sidiropoulos. Inapproximability for Metric Embeddings into R^d. In FOCS, pages 405-413, 2008. Google Scholar
  29. R. Nowakowski and I. Rival. A fixed edge theorem for graphs with loops. Journal of Graph Theory, 3:339-350, 1979. Google Scholar
  30. Alain Quilliot. A retraction problem in graph theory. Discrete Mathematics, 54(1):61-71, 1985. Google Scholar
  31. Daniel Rotter and Jens Vygen. d-dimensional arrangement revisited. Information Processing Letters, 113(13):498-505, 2013. Google Scholar
  32. James B. Saxe. Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time. SIAM on Journal Matrix Analysis Applications, 1:363-369, 1980. Google Scholar
  33. Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for Sensor Network Localization. Mathematical Programming, 109(2-3):367-384, 2007. Google Scholar
  34. E. Sperner. Neuer beweis für die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 6(1):265-272, 1928. Google Scholar
  35. Santosh Vempala. Random Projection: A New Approach to VLSI Layout. In FOCS, pages 389-395, 1998. Google Scholar
  36. Narayan Vikas. Compaction, Retraction, and Constraint Satisfaction. SIAM Journal on Computing, 33(4):761-782, 2004. Google Scholar
  37. Narayan Vikas. A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results. Journal of Computer and System Sciences, 71(4):406-439, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact