×

The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration. (English) Zbl 07378612

Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 26, 15 p. (2019).
Summary: 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.
For the entire collection see [Zbl 1407.68042].

MSC:

68Q25 Analysis of algorithms and problem complexity
68Wxx Algorithms in computer science

Software:

dynASP; ToTo; Jdrasil
PDF BibTeX XML Cite
Full Text: DOI

References:

[2] Michael Abseher, Nysret Musliu, and Stefan Woltran. htd -A Free, Open-Source Frame-work for (Customized) Tree Decompositions and Beyond. In Domenico Salvagnin and Michele Lombardi, editors, Proceedings of the 14th International Conference on Integra-tion of AI and OR Techniques in Constraint Programming (CPAIOR ’17), volume 10335 of Lecture Notes in Computer Science, pages 376-386. Springer, 2017. doi:10.1007/ 978-3-319-59776-8_30. · Zbl 06756600
[3] 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. doi:10.4230/LIPIcs.ESA.2018.6. · Zbl 1461.68091
[4] É. Bonnet and F. Sikora 26:13 · Zbl 1433.68275
[5] Max Bannach, Sebastian Berndt, and Thorsten Ehlers. Jdrasil: A Modular Library for Com-puting 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. doi:10.4230/LIPIcs.SEA.2017.28. · Zbl 1433.68275
[6] Max Bannach, Sebastian Berndt, Thorsten Ehlers, and Dirk Nowotka. SAT-encodings of tree decompositions. SAT COMPETITION 2018, page 72, 2018. · Zbl 06932460
[7] Sebastian Berndt. Computing Tree Width: From Theory to Practice and Back. In Con-ference on Computability in Europe, pages 81-88. Springer, 2018. · Zbl 1232.68188
[8] 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. doi:10.1145/1250790.1250801. · Zbl 06946790
[9] Johannes Blum and Sabine Storandt. Computation and Growth of Road Network Dimen-sions. In International Computing and Combinatorics Conference, pages 230-241. Springer, 2018. · Zbl 1296.68074
[10] 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. doi:10.1016/j.ic.2014.12.008. · Zbl 1281.68234
[11] 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. doi: 10.1145/2432622.2432628. · Zbl 1160.68023
[12] Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproxim-ability results. Theor. Comput. Sci., 406(3):207-214, 2008. doi:10.1016/j.tcs.2008.06. 046. · Zbl 1160.68023
[13] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3. · Zbl 1292.68122
[14] 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. doi:10.1109/FOCS.2011.23. · Zbl 1292.68122
[15] Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The First Parameterized Algorithms and Computational Experi-ments Challenge. In Jiong Guo and Danny Hermelin, editors, Proceedings of the 11th In-ternational 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. doi:10.4230/LIPIcs.IPEC.2016.30. · Zbl 1443.68220
[16] 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. doi:10.4230/ LIPIcs.IPEC.2017.30. · Zbl 1398.68226
[17] Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through Colors and IDs. ACM Trans. Algorithms, 11(2):13:1-13:20, 2014. doi:10.1145/ 2650261. · Zbl 1398.68226
[18] Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. · Zbl 0229.05125
[19] 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. · Zbl 07228417
[20] 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. doi:10.4230/LIPIcs.STACS.2018.26. · Zbl 0667.90036
[21] 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. doi: 10.1287/moor.12.4.634. · Zbl 0667.90036
[22] Johannes K Fichte, Markus Hecher, Neha Lodha, and Stefan Szeider. An SMT Approach to Fractional Hypertree Width. technical report, 2018. · Zbl 06769657
[23] 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 Nonmono-tonic Reasoning -(LPNMR 2017), volume 10377 of Lecture Notes in Computer Science, pages 132-145. Springer, 2017. doi:10.1007/978-3-319-61660-5_13. · Zbl 1443.68164
[24] 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), Leib-niz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2017. doi: 10.4230/LIPIcs.IPEC.2017.17. · Zbl 06916306
[25] 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. doi:10.4230/LIPIcs.ESA.2018.28.
[26] Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xin-hui Wang. Dynamic Programming for Minimum Steiner Trees. Theory Comput. Syst., 41(3):493-500, 2007. doi:10.1007/s00224-007-1324-4. · Zbl 1398.68490
[27] Martin Josef Geiger. Implementation of a Metaheuristic for the Steiner Tree Problem in Graphs. Mendeley Data. v1.doi:10.17632/yf9vpkgwdr.1.
[28] :14
[29] Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging Treewidth Heuristics. In Jiong Guo and Danny Hermelin, editors, Proceed-ings 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. doi:10.4230/LIPIcs.IPEC.2016.13. · Zbl 1398.68490
[30] :15 volume 80 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:14, 2017.doi:10.4230/LIPIcs.ICALP.2017.68.
[31] Martin Josef Geiger. Implementation of a Metaheuristic for the Steiner Tree Problem in Graphs. Mendeley Data. v1. doi:10.17632/yf9vpkgwdr.1. · Zbl 0159.22001
[32] Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, 1968. · Zbl 0159.22001
[33] 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. · Zbl 1387.05252
[34] 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. doi: 10.1007/s12532-016-0110-1. · Zbl 0774.05001
[35] Frank K. Hwang, Dana S. Richards, and Pawel Winter. The Steiner tree problem, volume 53. Elsevier, 1992. · Zbl 1441.68188
[36] Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In Ioannis Chatzi-giannakis, 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. doi:10.4230/LIPIcs.ICALP.2017.68. · Zbl 1441.68188
[37] Krzysztof Kiljan and Marcin Pilipczuk. Experimental Evaluation of Parameterized Al-gorithms for Feedback Vertex Set. arXiv preprint arXiv:1803.00925, 2018. · Zbl 06807241
[38] Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. SAT-encodings for special treewidth and pathwidth. In Proceedings of the 20th International Conference on Theory and Applic-ations of Satisfiability Testing (SAT 2017), volume 10491 of Lecture Notes in Computer Science, pages 429-445. Springer, 2017. doi:10.1007/978-3-319-66263-3_27. · Zbl 1148.68041
[39] 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. doi:10.1007/s00224-007-9089-3. · Zbl 1148.68041
[40] Parameterized Algorithms and Computational Experiments website, 2015-2018. URL: https://pacechallenge.org.
[41] Daniel Rehfeldt. A generic approach to solving the Steiner tree problem and variants. Mas-ter’s thesis, Technische Universität Berlin, Germany, 2015. URL: http://nbn-resolving. de/urn:nbn:de:0297-zib-57817.
[42] Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approx-imation. SIAM Journal on Discrete Mathematics, 19(1):122-134, 2005. · Zbl 1082.05088
[43] Ondřej Suchý. Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices. Algorithmica, 79(1):189-210, 2017. doi:10.1007/s00453-016-0249-1. · Zbl 1372.68146
[44] 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. doi:10.4230/LIPIcs.ESA.2017.68. · Zbl 1442.90198
[45] 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 Compu-tation (IPEC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2017. doi:10.4230/LIPIcs.IPEC.2017.29. · Zbl 1443.68213
[46] 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. doi:10.1016/j.dam.2016.09.023. · Zbl 1358.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.