Document Open Access Logo

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

Authors Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.27.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Graph algorithms
Keywords
  • Cut graph
  • Multiway cut
  • Surface
  • Lower bound
  • Parameterized Complexity
  • Exponential Time Hypothesis

Metrics

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

Abstract

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem.
A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus g has a cut graph of length at most a given value. We prove a time lower bound for this problem of n^{Omega(g/log g)} conditionally to ETH. In other words, the first n^{O(g)}-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors.
A multiway cut of an undirected graph G with t distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n^{Omega(sqrt{gt + g^2}/log(gt))}, conditionally to ETH, for any choice of the genus g >=0 of the graph and the number of terminals t >=4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case).
Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value g of the genus.

Cite As Get BibTex

Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.27

Author Details

Vincent Cohen-Addad
  • Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6, Paris, France
Éric Colin de Verdière
  • Université Paris-Est, LIGM, CNRS, ENPC, ESIEE Paris, UPEM, Marne-la-Vallée, France
Dániel Marx
  • Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary
Arnaud de Mesmay
  • Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, 38000 Grenoble, France

Funding

  • Cohen-Addad, Vincent: Ce projet a bénéficié d'une aide de l'État gérée par l'Agence Nationale de la Recherche au titre du Programme FOCAL portant la référence suivante : ANR-18-CE40-0004-01.
  • Colin de Verdière, Éric: Partially supported by the French ANR project ANR-17-CE40-0033 (SoS).
  • Marx, Dániel: Supported by ERC Consolidator Grant SYSTEMATICGRAPH (No. 725978).
  • de Mesmay, Arnaud: Partially supported by the French ANR projects ANR-16-CE40-0009-01 (GATO), ANR-18-CE40-0004-01 (FOCAL) and the CNRS PEPS project COMP3D.

Acknowledgements

We are grateful to the anonymous referees for a careful reading of the paper and many helpful suggestions.

References

  1. Jianer Chen, Iyad A Kanj, Ljubomir Perković, Eric Sedgwick, and Ge Xia. Genus characterizes the complexity of certain graph problems: Some tight results. Journal of Computer and System Sciences, 73(6):892-907, 2007. Google Scholar
  2. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1782-1801, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.129.
  3. Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de Mesmay. A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals. In 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1439-1458, 2018. Google Scholar
  4. Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. Full version of this article, 2019. URL: http://arxiv.org/abs/1903.08603.
  5. Vincent Cohen-Addad and Arnaud de Mesmay. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. In European Symposium on Algorithms (ESA), pages 386-398. Springer, 2015. Google Scholar
  6. Éric Colin de Verdière. Multicuts in planar and bounded-genus graphs with bounded number of terminals. Algorithmica, 78(4):1206-1224, 2017. Google Scholar
  7. Éric Colin de Verdière. Computational topology of graphs on surfaces. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Toth, editors, Handbook of Discrete and Computational Geometry, chapter 23, pages 605-636. CRC Press LLC, third edition, 2018. Google Scholar
  8. Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In 27th ACM-SIAM symposium on Discrete algorithms (SODA), pages 1650-1669. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  9. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 3. Springer, 2015. Google Scholar
  10. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864-894, 1994. Google Scholar
  11. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. In 50th ACM Symposium on Theory of Computing (STOC), pages 574-586, 2018. Google Scholar
  12. Erik D Demaine, Fedor V Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. Journal of the ACM, 52(6):866-893, 2005. Google Scholar
  13. Jeff Erickson and Sariel Har-Peled. Optimally cutting a surface into a disk. Discrete &Computational Geometry, 31(1):37-59, 2004. Google Scholar
  14. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. In IEEE 57th Symposium on Foundations of Computer Science, FOCS, pages 515-524, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.62.
  15. John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391-407, 1984. Google Scholar
  16. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1):1, 2007. Google Scholar
  17. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In 33rd ACM Symposium on Theory of Computing (STOC), pages 657-666, 2001. Google Scholar
  18. Te C. Hu. Integer programming and network flows. Technical report, Wisconsin Univ Madison Dept. of Computer Sciences, 1969. Google Scholar
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In 39th IEEE Symposium on Foundations of Computer Science (FOCS), pages 653-662, 1998. Google Scholar
  20. Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In 49th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 771-780. IEEE, 2008. Google Scholar
  21. Philip N. Klein and Dániel Marx. Solving Planar k-Terminal Cut in O(n^c√k) Time. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 569-580. Springer, 2012. Google Scholar
  22. Daniel Lokshtanov, Dániel Marx, Saket Saurabh, et al. Lower bounds based on the exponential time hypothesis. Bulletin of EATCS, 3(105), 2013. Google Scholar
  23. Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström. Subexponential Parameterized Odd Cycle Transversal on Planar Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, pages 424-434, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.424.
  24. Dániel Marx. On the Optimality of Planar and Geometric Approximation Schemes. In 48th IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 338-348, 2007. Google Scholar
  25. Dániel Marx. Can You Beat Treewidth? Theory of Computing, 6(1):85-112, 2010. Google Scholar
  26. Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 677-688, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  27. Dániel Marx. The Square Root Phenomenon in Planar Graphs. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, volume 7924. Springer, 2013. Google Scholar
  28. Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs. In 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 474-484, 2018. Google Scholar
  29. Dániel Marx and Michał Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25, pages 542-553, 2014. Google Scholar
  30. Dániel Marx and Michal Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In 23rd European Symposium on Algorithms (ESA), pages 865-877, 2015. Google Scholar
  31. Dániel Marx and Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In 30th Symposium on Computational Geometry (SoCG), page 67. ACM, 2014. Google Scholar
  32. Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics, 12(1):6-26, 1999. Google Scholar
  33. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001. Google Scholar
  34. Zoë Wood, Hugues Hoppe, Mathieu Desbrun, and Peter Schröder. Removing excess topology from isosurfaces. ACM Transactions on Graphics (TOG), 23(2):190-208, 2004. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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