Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.30
URN: urn:nbn:de:0030-drops-111511
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11151/
Chimani, Markus ; Wiedera, Tilo
Stronger ILPs for the Graph Genus Problem
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{chimani_et_al:LIPIcs:2019:11151,
author = {Markus Chimani and Tilo Wiedera},
title = {{Stronger ILPs for the Graph Genus Problem}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11151},
URN = {urn:nbn:de:0030-drops-111511},
doi = {10.4230/LIPIcs.ESA.2019.30},
annote = {Keywords: algorithm engineering, genus, integer linear programming}
}
| Keywords: | algorithm engineering, genus, integer linear programming | |
| Seminar: | 27th Annual European Symposium on Algorithms (ESA 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 06.09.2019 |
