LIPIcs.IPEC.2022.31.pdf
- Filesize: 0.54 MB
- 4 pages
Document
PACE Solver Description: DreyFVS
Authors
Amadeus Reinald 
,
Mathis Rocton
-
Part of:
Volume:
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
Cite As Get BibTex
Gabriel Bathie, Gaétan Berthe, Yoann Coudert-Osmont, David Desobry, Amadeus Reinald, and Mathis Rocton. PACE Solver Description: DreyFVS. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 31:1-31:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.31
Abstract
We describe DreyFVS, a heuristic for Directed Feedback Vertex Set submitted to the 2022 edition of Parameterized Algorithms and Computational Experiments Challenge. The Directed Feedback Vertex Set problem asks to remove a minimal number of vertices from a digraph such that the resulting digraph is acyclic. Our algorithm first performs a guess on a reduced instance by leveraging the Sinkhorn-Knopp algorithm, to then improve this solution by pipelining two local search methods.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
- Theory of computation → Parameterized complexity and exact algorithms
Keywords
- Directed Feedback Vertex Set
- Heuristic
- Sinkhorn algorithm
- Local search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Gabriel Bathie, Gaétan Berthe, Yoann Coudert-Osmont, David Desobry, Amadeus Reinald, and Mathis Rocton. DreyFVS, June 2022. URL: https://doi.org/10.5281/zenodo.6638217.
- Isabel Beichl and Francis Sullivan. Approximating the permanent via importance sampling with application to the dimer covering problem. Journal of Computational Physics, 149(1):128-147, 1999. URL: https://doi.org/10.1006/jcph.1998.6149.
- Philippe Galinier, Eunice Lemamou, and Mohamed Wassim Bouzidi. Applying local search to the feedback vertex set problem. Journal of Heuristics, 19(5):797-818, October 2013. URL: https://doi.org/10.1007/s10732-013-9224-z.
- Hen-Ming Lin and Jing-Yang Jou. On computing the minimum feedback vertex set of a directed graph by contraction operations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(3):295-307, 2000. URL: https://doi.org/10.1109/43.833199.
- James Shook and Isabel Beichl. Matrix scaling: A new heuristic for the feedback vertex set problem, June 2014. URL: https://math.nist.gov/mcsd/Seminars/2014/2014-06-10-Shook-presentation.pdf.
-
Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-348, 1967.
