License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.30
URN: urn:nbn:de:0030-drops-173861
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17386/
Go to the corresponding LIPIcs Volume Portal


Bergenthal, Moritz ; Dirks, Jona ; Freese, Thorben ; Gahde, Jakob ; Gerhard, Enna ; Grobler, Mario ; Siebertz, Sebastian

PACE Solver Description: GraPA-JAVA

pdf-format:
LIPIcs-IPEC-2022-30.pdf (0.5 MB)


Abstract

We present an exact solver for the DFVS, submitted for the exact track of the Parameterized Algorithms and Computational Experiments challenge (PACE) in 2022. The solver heavily relies on data reduction (known from the literature and new reduction rules). The instances are then further processed by integer linear programming approaches. We implemented the algorithm in the scope of a student project at the University of Bremen.

BibTeX - Entry

@InProceedings{bergenthal_et_al:LIPIcs.IPEC.2022.30,
  author =	{Bergenthal, Moritz and Dirks, Jona and Freese, Thorben and Gahde, Jakob and Gerhard, Enna and Grobler, Mario and Siebertz, Sebastian},
  title =	{{PACE Solver Description: GraPA-JAVA}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{30:1--30:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17386},
  URN =		{urn:nbn:de:0030-drops-173861},
  doi =		{10.4230/LIPIcs.IPEC.2022.30},
  annote =	{Keywords: complexity theory, parameterized complexity, linear programming, java, directed feedback vertex set, PACE 2022}
}

Keywords: complexity theory, parameterized complexity, linear programming, java, directed feedback vertex set, PACE 2022
Collection: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Issue Date: 2022
Date of publication: 14.12.2022
Supplementary Material: Software (Source Code Release): https://doi.org/10.5281/zenodo.6647003
Software (Public Git Repositories): https://gitlab.informatik.uni-bremen.de/grapa/java/
Software (Public Git Repository): https://gitlab.informatik.uni-bremen.de/grapa/java/fptg-library archived at: https://archive.softwareheritage.org/swh:1:dir:fd00e212eda2d4eab270dadc83923224551db839
Software (Public Git Repository): https://gitlab.informatik.uni-bremen.de/grapa/java/maxcliqueenumeration archived at: https://archive.softwareheritage.org/swh:1:dir:a4cde68f2e0de0e5b873eb5a02dc975c4a37fbb1
Software (Public Git Repository): https://gitlab.informatik.uni-bremen.de/grapa/java/pace-2022-dfvs-solver archived at: https://archive.softwareheritage.org/swh:1:dir:a80285858dd46e917d4f0c89fd13948177c6a048


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