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.IPEC.2019.25
URN: urn:nbn:de:0030-drops-114861
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11486/
Dzulfikar, M. Ayaz ;
Fichte, Johannes K. ;
Hecher, Markus
The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
Abstract
The organizers of the 4th Parameterized Algorithms and Computational Experiments challenge (PACE 2019) report on the 4th iteration of the PACE challenge. This year, the first track featured the MinVertexCover problem, which asks given an undirected graph G=(V,E) to output a set S subseteq V of vertices such that for every edge vw in E at least one endpoint belongs to S. The exact decision version of this problem is one of the most discussed problem if not even the prototypical problem in parameterized complexity theory. Another two tracks were dedicated to computing the hypertree width of a given hypergraph, which is a certain generalization of tree decompositions to hypergraphs that has widely been applied to problems in databases, constraint programming, and artificial intelligence. On one track we asked for submissions that compute hypertree decompositions of minimum width (MinHypertreeWidth) and on the other track we asked to heuristically compute hypertree decompositions of small width quickly (HeurHypertreeWidth). We received 28 implementations from 26 teams. This year we asked participants to submit solver descriptions in order to count as a submission for the challenge. We received those from 16 teams with overall 33 participants from 10 countries. One team submitted successful solutions to all three tracks.
BibTeX - Entry
@InProceedings{dzulfikar_et_al:LIPIcs:2019:11486,
author = {M. Ayaz Dzulfikar and Johannes K. Fichte and Markus Hecher},
title = {{The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {25:1--25:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-129-0},
ISSN = {1868-8969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11486},
URN = {urn:nbn:de:0030-drops-114861},
doi = {10.4230/LIPIcs.IPEC.2019.25},
annote = {Keywords: Parameterized Algorithms, Vertex Cover Problem, Hypertree Decompositions, Implementation Challenge, FPT}
}
|
Keywords: |
|
Parameterized Algorithms, Vertex Cover Problem, Hypertree Decompositions, Implementation Challenge, FPT |
|
Collection: |
|
14th International Symposium on Parameterized and Exact Computation (IPEC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.12.2019 |
