Document Open Access Logo

Stronger ILPs for the Graph Genus Problem

Authors Markus Chimani , Tilo Wiedera

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.30.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Markus Chimani
  • Theoretical Computer Science, Osnabrück University, Germany
Tilo Wiedera
  • Theoretical Computer Science, Osnabrück University, Germany

Funding

Supported by the German Research Foundation (DFG) grant CH 897/2-2.

Cite As Get BibTex

Markus Chimani and Tilo Wiedera. Stronger ILPs for the Graph Genus Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.30

Abstract

The minimum genus of a graph is an important question in graph theory and a key ingredient in several graph algorithms. However, its computation is NP-hard and turns out to be hard even in practice. Only recently, the first non-trivial approach - based on SAT and ILP (integer linear programming) models - has been presented, but it is unable to successfully tackle graphs of genus larger than 1 in practice.
Herein, we show how to improve the ILP formulation. The crucial ingredients are two-fold. First, we show that instead of modeling rotation schemes explicitly, it suffices to optimize over partitions of the (bidirected) arc set A of the graph. Second, we exploit the cycle structure of the graph, explicitly mapping short closed walks on A to faces in the embedding.
Besides the theoretical advantages of our models, we show their practical strength by a thorough experimental evaluation. Contrary to the previous approach, we are able to quickly solve many instances of genus > 1.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Linear programming
Keywords
  • algorithm engineering
  • genus
  • integer linear programming

Metrics

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

References

  1. Amariah Becker, Philip N. Klein, and David Saulpic. A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. In ESA 2017, pages 12:1-12:15, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.12.
  2. Stephan Beyer, Markus Chimani, Ivo Hedtke, and Michal Kotrbcík. A Practical Method for the Minimum Genus of a Graph: Models and Experiments. In SEA 2016, LNCS 9685, pages 75-88, 2016. URL: https://doi.org/10.1007/978-3-319-38851-9_6.
  3. C. Paul Bonnington and Tomaz Pisanski. On the orientable genus of the cartesian product of a complete regular tripartite graph with an even cycle. Ars Comb., 70, 2004. Google Scholar
  4. Matthew G. Brin, David E. Rauschenberg, and Craig C. Squier. On the genus of the semidirect product of ℤ₉ by ℤ₃. Journal of Graph Theory, 13(1):49-61, 1989. URL: https://doi.org/10.1002/jgt.3190130108.
  5. Matthew G. Brin and Craig C. Squier. On the Genus of ℤ₃ × ℤ₃ × ℤ₃. Eur. J. Comb., 9(5):431-443, 1988. URL: https://doi.org/10.1016/S0195-6698(88)80002-7.
  6. Chandra Chekuri and Anastasios Sidiropoulos. Approximation Algorithms for Euler Genus and Related Problems. In FOCS 2013, pages 167-176, 2013. URL: https://doi.org/10.1109/FOCS.2013.26.
  7. Jianer Chen. A Linear-Time Algorithm for Isomorphism of Graphs of Bounded Average Genus. J. Disc. Math., 7(4):614-631, 1994. URL: https://doi.org/10.1137/S0895480191196769.
  8. Jianer Chen, Iyad A. Kanj, Ljubomir Perkovic, Eric Sedgwick, and Ge Xia. Genus characterizes the complexity of certain graph problems: Some tight results. J. Comput. Syst. Sci., 73(6):892-907, 2007. URL: https://doi.org/10.1016/j.jcss.2006.11.001.
  9. Markus Chimani, Carsten Gutwenger, Mike Juenger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The Open Graph Drawing Framework (OGDF). In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 543-569. Chapman and Hall/CRC, 2013. URL: https://crcpress.com/Handbook-of-Graph-Drawing-and-Visualization/Tamassia/9781584884125.
  10. Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments. In SEA 2018, pages 22:1-22:15, 2018. URL: https://doi.org/10.4230/LIPIcs.SEA.2018.22.
  11. Markus Chimani and Tilo Wiedera. Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast. In ESA 2018, LIPIcs 112, pages 19:1-19:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.19.
  12. Marston Conder and Ricardo Grande. On Embeddings of Circulant Graphs. Electr. J. Comb., 22(2):P2.28, 2015. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p28.
  13. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. The Bidimensional Theory of Bounded-Genus Graphs. Disc. Math., 20(2):357-371, 2006. URL: https://doi.org/10.1137/040616929.
  14. Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Roberto Tamassia, Emanuele Tassinari, and Francesco Vargiu. An Experimental Comparison of Four Graph Drawing Algorithms. Comput. Geom., 7:303-325, 1997. URL: https://doi.org/10.1016/S0925-7721(96)00005-3.
  15. John A. Ellis, Hongbing Fan, and Michael R. Fellows. The dominating set problem is fixed parameter tractable for graphs of bounded genus. J. Algorithms, 52(2):152-168, 2004. URL: https://doi.org/10.1016/j.jalgor.2004.02.001.
  16. Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Marco E. Lübbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Matthias Walter, Fabian Wegscheider, Jonas T. Witt, and Jakob Witzig. The SCIP Optimization Suite 6.0. Technical report, Optimization Online, July 2018. URL: http://www.optimization-online.org/DB_HTML/2018/07/6692.html.
  17. David A. Hoelzeman and Saïd Bettayeb. On the genus of star graphs. IEEE Transactions on Computers, 43(6):755-759, 1994. URL: https://doi.org/10.1109/12.286309.
  18. Mark Jungerman and Gerhard Ringel. The genus of the n‐octahedron: Regular cases. J. Graph Theory, 2(1):69-75, 1978. URL: https://doi.org/10.1002/jgt.3190020109.
  19. K. Kawarabayashi, B. Mohar, and B. Reed. A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. In FOCS 2008, pages 771-780, 2008. URL: https://doi.org/10.1109/FOCS.2008.53.
  20. Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Beyond the Euler Characteristic: Approximating the Genus of General Graphs. In STOC 2015, pages 675-682, 2015. URL: https://doi.org/10.1145/2746539.2746583.
  21. Michal Kotrbcík and Tomaz Pisanski. Genus of the Cartesian Product of Triangles. Electr. J. Comb., 22(4):P4.2, 2015. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p2.
  22. Valentas Kurauskas. On the genus of the complete tripartite graph K_n, n, 1. Disc. Math., 340(3):508-515, 2017. URL: https://doi.org/10.1016/j.disc.2016.09.017.
  23. Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos. A Pseudo-approximation for the Genus of Hamiltonian Graphs. In APPROX 2013, pages 244-259, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_18.
  24. Dragan Marusic, Tomaz Pisanski, and Steve Wilson. The genus of the GRAY graph is 7. Eur. J. Comb., 26(3-4):377-385, 2005. URL: https://doi.org/10.1016/j.ejc.2004.01.015.
  25. Bojan Mohar. A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. J. Disc. Math., 12(1):6-26, 1999. URL: https://doi.org/10.1137/S089548019529248X.
  26. Bojan Mohar, Tomaz Pisanski, Martin Skoviera, and Arthur T. White. The cartesian product of three triangles can be embedded into a surface of genus 7. Disc. Math., 56(1):87-89, 1985. URL: https://doi.org/10.1016/0012-365X(85)90197-9.
  27. Wendy Myrvold and William Kocay. Errors in graph embedding algorithms. J. Comp. and Sys. Sciences, 77(2):430-438, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.002.
  28. Stephen C. North. 5114 directed graphs, 1995. Manuscript. Google Scholar
  29. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. ACM Trans. Algorithms, 14(4):53:1-53:73, 2018. URL: https://doi.org/10.1145/3239560.
  30. Gerhard Ringel. Das Geschlecht des vollständigen paaren Graphen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 28(3):139-150, 1965. URL: https://doi.org/10.1007/BF02993245.
  31. Gerhard Ringel. On the genus of the graph K_n × K₂ or the n-prism. Disc. Math., 20:287-294, 1977. URL: https://doi.org/10.1016/0012-365X(77)90067-X.
  32. Gerhard Ringel and J. W. T. Youngs. SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM. PNAS USA, 60(2):438-445, 1968. URL: https://doi.org/10.1073/pnas.60.2.438.
  33. Gerhard Ringel and J. W. T. Youngs. Das Geschlecht des vollständigen dreifärbbaren Graphen. Commentarii Mathematici Helvetici, 45(1):152-158, 1970. URL: https://doi.org/10.1007/BF02567322.
  34. Neil Robertson and Paul D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Comb. Theory, Ser. B, 48(2):255-288, 1990. URL: https://doi.org/10.1016/0095-8956(90)90121-F.
  35. Carsten Thomassen. The graph genus problem is NP-complete. J. Algorithms, 10(4):568-576, 1989. URL: https://doi.org/10.1016/0196-6774(89)90006-0.
  36. Carsten Thomassen. Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory, Series B, 48(2):155-177, 1990. URL: https://doi.org/10.1016/0095-8956(90)90115-G.
  37. Arthur T. White. The genus of the complete tripartite graph K_mn,n,n. J. Comb. Theory, 7(3):283-285, 1969. URL: https://doi.org/10.1016/S0021-9800(69)80027-X.
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 About DROPS Imprint Privacy Contact