Document Open Access Logo

The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration

Authors Édouard Bonnet, Florian Sikora

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.26.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Édouard Bonnet
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Florian Sikora
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France

Funding

Partially supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program "Investissements d’Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR) and project "ESIGMA" (ANR-17-CE23-0010).

Cite AsGet BibTex

Édouard Bonnet and Florian Sikora. The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2018.26

Abstract

The Program Committee of the Third Parameterized Algorithms and Computational Experiments challenge (PACE 2018) reports on the third iteration of the PACE challenge. This year, all three tracks were dedicated to solve the Steiner Tree problem, in which, given an edge-weighted graph and a subset of its vertices called terminals, one has to find a minimum-weight subgraph which spans all the terminals. In Track A, the number of terminals was limited. In Track B, a tree-decomposition of the graph was provided in the input, and the treewidth was limited. Finally, Track C welcomed heuristics. Over 80 participants on 40 teams from 16 countries submitted their implementations to the competition.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Steiner tree problem
  • contest
  • implementation challenge
  • FPT

Metrics

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

References

  1. Michael Abseher, Nysret Musliu, and Stefan Woltran. htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond. In Domenico Salvagnin and Michele Lombardi, editors, Proceedings of the 14th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR '17), volume 10335 of Lecture Notes in Computer Science, pages 376-386. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59776-8_30.
  2. Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 6:1-6:13, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.6.
  3. Max Bannach, Sebastian Berndt, and Thorsten Ehlers. Jdrasil: A Modular Library for Computing Tree Decompositions. In Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman, editors, Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), volume 75 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1-28:21, Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.SEA.2017.28.
  4. Max Bannach, Sebastian Berndt, Thorsten Ehlers, and Dirk Nowotka. SAT-encodings of tree decompositions. SAT COMPETITION 2018, page 72, 2018. Google Scholar
  5. Sebastian Berndt. Computing Tree Width: From Theory to Practice and Back. In Conference on Computability in Europe, pages 81-88. Springer, 2018. Google Scholar
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74, 2007. URL: http://dx.doi.org/10.1145/1250790.1250801.
  7. Johannes Blum and Sabine Storandt. Computation and Growth of Road Network Dimensions. In International Computing and Combinatorics Conference, pages 230-241. Springer, 2018. Google Scholar
  8. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.008.
  9. Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. URL: http://dx.doi.org/10.1145/2432622.2432628.
  10. Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci., 406(3):207-214, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.06.046.
  11. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  12. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  13. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The First Parameterized Algorithms and Computational Experiments Challenge. In Jiong Guo and Danny Hermelin, editors, Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1-30:9, Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.30.
  14. Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, pages 30:1-30:12, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.30.
  15. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through Colors and IDs. ACM Trans. Algorithms, 11(2):13:1-13:20, 2014. URL: http://dx.doi.org/10.1145/2650261.
  16. Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  17. Eugene F. Dumitrescu, Allison L. Fisher, Timothy D. Goodrich, Travis S. Humble, Blair D. Sullivan, and Andrew L. Wright. Benchmarking treewidth as a practical component of tensor-network-based quantum simulation. arXiv preprint arXiv:1807.04599, 2018. Google Scholar
  18. Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 26:1-26:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.26.
  19. Ranel E. Erickson, Clyde L. Monma, and Arthur F. Veinott Jr. Send-and-Split Method for Minimum-Concave-Cost Network Flows. Math. Oper. Res., 12(4):634-664, 1987. URL: http://dx.doi.org/10.1287/moor.12.4.634.
  20. Johannes K Fichte, Markus Hecher, Neha Lodha, and Stefan Szeider. An SMT Approach to Fractional Hypertree Width. technical report, 2018. Google Scholar
  21. Johannes Klaus Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. Answer Set Solving with Bounded Treewidth Revisited. In Marcello Balduccini and Tomi Janhunen, editors, Proceedings of 14th International Conference on Logic Programming and Nonmonotonic Reasoning - (LPNMR 2017), volume 10377 of Lecture Notes in Computer Science, pages 132-145. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-61660-5_13.
  22. Johannes Klaus Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. DynASP2.5: Dynamic programming on tree decompositions in action. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.17.
  23. Johannes Klaus Fichte, Markus Hecher, Stefan Woltran, and Markus Zisser. Weighted Model Counting on the GPU by Exploiting Small Treewidth. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 28:1-28:16, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.28.
  24. Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. Dynamic Programming for Minimum Steiner Trees. Theory Comput. Syst., 41(3):493-500, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1324-4.
  25. Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging Treewidth Heuristics. In Jiong Guo and Danny Hermelin, editors, Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:13, Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.13.
  26. Martin Josef Geiger. Implementation of a Metaheuristic for the Steiner Tree Problem in Graphs. Mendeley Data. v1. URL: http://dx.doi.org/10.17632/yf9vpkgwdr.1.
  27. Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, 1968. Google Scholar
  28. L.W. van der Graaff. Dynamic programming on Nice Tree Decompositions. Master’s thesis, Utrecht University, 2015. URL: https://dspace.library.uu.nl/handle/1874/309652.
  29. Stefan Hougardy, Jannik Silvanus, and Jens Vygen. Dijkstra meets Steiner: A fast exact goal-oriented Steiner tree algorithm. Math. Program. Comput., 9(2):135-202, 2017. URL: http://dx.doi.org/10.1007/s12532-016-0110-1.
  30. Frank K. Hwang, Dana S. Richards, and Pawel Winter. The Steiner tree problem, volume 53. Elsevier, 1992. Google Scholar
  31. Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.68.
  32. Krzysztof Kiljan and Marcin Pilipczuk. Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set. arXiv preprint arXiv:1803.00925, 2018. Google Scholar
  33. Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. SAT-encodings for special treewidth and pathwidth. In Proceedings of the 20th International Conference on Theory and Applications of Satisfiability Testing (SAT 2017), volume 10491 of Lecture Notes in Computer Science, pages 429-445. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-66263-3_27.
  34. Daniel Mölle, Stefan Richter, and Peter Rossmanith. Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover. Theory Comput. Syst., 43(2):234-253, 2008. URL: http://dx.doi.org/10.1007/s00224-007-9089-3.
  35. Networks project, 2017. URL: http://www.thenetworkcenter.nl.
  36. Parameterized Algorithms and Computational Experiments website, 2015-2018. URL: https://pacechallenge.org.
  37. Daniel Rehfeldt. A generic approach to solving the Steiner tree problem and variants. Master’s thesis, Technische Universität Berlin, Germany, 2015. URL: http://nbn-resolving.de/urn:nbn:de:0297-zib-57817.
  38. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics, 19(1):122-134, 2005. Google Scholar
  39. Ondřej Suchý. Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices. Algorithmica, 79(1):189-210, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0249-1.
  40. Hisao Tamaki. Positive-Instance Driven Dynamic Programming for Treewidth. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:13, Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.68.
  41. Tom C. van der Zanden and Hans L. Bodlaender. Computing Treewidth on the GPU. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.29.
  42. Rim van Wersch and Steven Kelk. ToTo: An open database for computation, storage and retrieval of tree decompositions. Discrete Applied Mathematics, 217:389-393, 2017. URL: http://dx.doi.org/10.1016/j.dam.2016.09.023.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact