PACE Solver Description: GraPA-JAVA

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



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.30.pdf
  • Filesize: 0.54 MB
  • 4 pages

Document Identifiers

Author Details

Moritz Bergenthal
  • Universität Bremen, Germany
Jona Dirks
  • Universität Bremen, Germany
Thorben Freese
  • Universität Bremen, Germany
Jakob Gahde
  • Universität Bremen, Germany
Enna Gerhard
  • Universität Bremen, Germany
Mario Grobler
  • Universität Bremen, Germany
Sebastian Siebertz
  • Universität Bremen, Germany

Cite AsGet BibTex

Moritz Bergenthal, Jona Dirks, Thorben Freese, Jakob Gahde, Enna Gerhard, Mario Grobler, and Sebastian Siebertz. PACE Solver Description: GraPA-JAVA. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 30:1-30:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.30

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • complexity theory
  • parameterized complexity
  • linear programming
  • java
  • directed feedback vertex set
  • PACE 2022

Metrics

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

References

  1. Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Towards a Polynomial Kernel for Directed Feedback Vertex Set. In Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.36.
  2. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-21275-3.
  3. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics, 18, November 2013. URL: https://doi.org/10.1145/2543629.
  4. Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, and Mathias Weller. What is known about vertex cover kernelization? In Adventures Between Lower Bounds and Higher Altitudes, pages 330-356, 2018. URL: https://doi.org/10.1007/978-3-319-98355-4_19.
  5. Lisa K. Fleischer, Bruce Hendrickson, and Ali Pınar. On identifying strongly connected components in parallel. In José Rolim, editor, Parallel and Distributed Processing, pages 505-511, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-45591-4_68.
  6. Rudolf Fleischer, Xi Wu, and Liwei Yuan. Experimental study of fpt algorithms for the directed feedback vertex set problem. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, pages 611-622, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-04128-0_55.
  7. Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. WeGotYouCovered: The winning solver from the pace 2019 implementation challenge, vertex cover track. ArXiv, abs/1908.06795, 2019. URL: http://arxiv.org/abs/1908.06795.
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