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.31
URN: urn:nbn:de:0030-drops-173870
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17387/
Go to the corresponding LIPIcs Volume Portal

Bathie, Gabriel ; Berthe, Gaétan ; Coudert-Osmont, Yoann ; Desobry, David ; Reinald, Amadeus ; Rocton, Mathis

PACE Solver Description: DreyFVS

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

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.

BibTeX - Entry

@InProceedings{bathie_et_al:LIPIcs.IPEC.2022.31,
  author =	{Bathie, Gabriel and Berthe, Ga\'{e}tan and Coudert-Osmont, Yoann and Desobry, David and Reinald, Amadeus and Rocton, Mathis},
  title =	{{PACE Solver Description: DreyFVS}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{31:1--31: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/17387},
  URN =		{urn:nbn:de:0030-drops-173870},
  doi =		{10.4230/LIPIcs.IPEC.2022.31},
  annote =	{Keywords: Directed Feedback Vertex Set, Heuristic, Sinkhorn algorithm, Local search}
}

Keywords: Directed Feedback Vertex Set, Heuristic, Sinkhorn algorithm, Local search
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): https://doi.org/10.5281/zenodo.6638217

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