DROPS

Document

Invited Paper

DOI: 10.4230/LIPIcs.IPEC.2019.25

The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)

Authors: M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

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.

Cite as

M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher. The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper). In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dzulfikar_et_al:LIPIcs.IPEC.2019.25,
  author =	{Dzulfikar, M. Ayaz and Fichte, Johannes K. and Hecher, Markus},
  title =	{{The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration}},
  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 =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.25},
  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}
}

Search Results

Documents authored by Dzulfikar, M. Ayaz

The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message