License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11151/
Go to the corresponding LIPIcs Volume Portal

Chimani, Markus ; Wiedera, Tilo

Stronger ILPs for the Graph Genus Problem

pdf-format:
LIPIcs-ESA-2019-30.pdf (0.6 MB)

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
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI