The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration. (English) Zbl 1443.68220
Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 30, 12 p. (2018).
Summary: In this article, the Program committee of the Second Parameterized Algorithms and Computational Experiments challenge (PACE 2017) reports on the second iteration of the PACE challenge. Track A featured the Treewidth problem and Track B the Minimum Fill-In problem. Over 44 participants on 17 teams from 11 countries submitted their implementations to the competition.
For the entire collection see [Zbl 1387.68026].
For the entire collection see [Zbl 1387.68026].
References:
| [1] | 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, 16th International Symposium on Experimental Algorithms, · Zbl 1433.68275 |
| [2] | David Bergman and Arvind U. Raghunathan. A benders approach to the minimum chordal completion problem. In Laurent Michel, editor, Integration of AI and OR Techniques in · Zbl 1464.90074 |
| [3] | Hans L. Bodlaender, Pinar Heggernes, and Yngve Villanger.Faster parameterized algorithms for minimum fill-in.Algorithmica, 61(4):817-838, 2011.doi:10.1007/ s00453-010-9421-1. · Zbl 1230.68100 |
| [4] | Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput., 31(1):212-232, 2001. doi:10.1137/S0097539799359683. · Zbl 0987.05085 |
| [5] | Peter Buneman. A characterisation of rigid circuit graphs. Discrete Mathematics, 9(3):205- 212, 1974. doi:10.1016/0012-365X(74)90002-8. · Zbl 0288.05128 |
| [6] | Benjamin A. Burton, Ryan Budney, William Pettersson, et al. Regina: Software for lowdimensional topology, 1999-2016. URL: http://regina-normal.github.io. |
| [7] | Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58(4):171-176, 1996. doi:10.1016/0020-0190(96)00050-6. · Zbl 0875.68702 |
| [8] | Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium · Zbl 1397.68030 |
| [9] | 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, 11th International Symposium on |
| [10] | Emmanuel J. P. Douzery, Celine Scornavacca, Jonathan Romiguier, Khalid Belkhir, Nicolas Galtier, Frédéric Delsuc, and Vincent Ranwez. OrthoMaM v8: A database of orthologous exons and coding sequences for comparative genomics in mammals. Molecular Biology and |
| [11] | Johannes Klaus Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. Answer set solving with bounded treewidth revisited. In Marcello Balduccini and Tomi Janhunen, editors, Logic Programming and Nonmonotonic Reasoning - 14th International Conference, · Zbl 1491.68042 |
| [12] | Johannes Klaus Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. DynASP2.5: Dynamic programming on tree decompositions in action.In Proceedings of the 12th · Zbl 1443.68164 |
| [13] | Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger. Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput., 38(3):1058-1079, 2008. doi:10.1137/ 050643350. · Zbl 1163.05320 |
| [14] | Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput., 42(6):2197-2216, 2013. doi:10.1137/11085390X. · Zbl 1285.68055 |
| [15] | Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. · Zbl 0411.68039 |
| [16] | Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging treewidth heuristics.In Jiong Guo and Danny Hermelin, editors, 11th · Zbl 1398.68490 |
| [17] | Rob Gysel, Kristian Stevens, and Dan Gusfield.Reducing problems in unrooted tree compatibility to restricted triangulations of intersection graphs. In Benjamin J. Raphael and Jijun Tang, editors, Algorithms in Bioinformatics - 12th International Workshop, |
| [18] | Yoichi Iwata. Linear-time kernelization for feedback vertex set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on · Zbl 1352.68111 |
| [19] | Haim Kaplan, Ron Shamir, and Robert Endre Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mex · Zbl 0928.68124 |
| [20] | Kalev Kask, Andrew Gelfand, Lars Otten, and Rina Dechter. Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In Wolfram Burgard and Dan Roth, editors, Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, |
| [21] | Masashi Kiyomi, Yoshio Okamoto, and Yota Otachi. On the treewidth of toroidal grids. Discrete Applied Mathematics, 198:303-306, 2016. doi:10.1016/j.dam.2015.06.027. · Zbl 1327.05091 |
| [22] | Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. Sat-encodings for special treewidth and pathwidth. In Serge Gaspers and Toby Walsh, editors, Theory and Applications of Sat · Zbl 1496.68266 |
| [23] | Matrix market. URL: http://math.nist.gov/MatrixMarket/. |
| [24] | Multiple-alignment to character-state intersection graph converter, 2017. URL: https: //github.com/PACE-challenge/phylo_converter. |
| [25] | Assaf Natanzon, Ron Shamir, and Roded Sharan. A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Comput., 30(4):1067-1079, 2000. doi:10.1137/ S0097539798336073. · Zbl 0969.68194 |
| [26] | Network repository. URL: http://networkrepository.com/. |
| [27] | Networks project, 2017. URL: http://www.thenetworkcenter.nl. |
| [28] | Parameterized Algorithms and Computational Experiments website, 2015-2017.URL: https://pacechallenge.wordpress.com. · Zbl 1073.13002 |
| [29] | :12 |
| [30] | :11 volume 63 of LIPIcs, pages 30:1-30:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.IPEC.2016.30. |
| [31] | Vincent Ranwez, Frédéric Delsuc, Sylvie Ranwez, Khalid Belkhir, Marie-Ka Tilak, and Emmanuel JP Douzery. OrthoMaM: A database of orthologous genomic markers for placental mammal phylogenetics. BMC Evolutionary Biology, 7(1):241, Nov 2007. Database accessed |
| [32] | Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, · Zbl 1426.90250 |
| [33] | Robert Endre Tarjan.Decomposition by clique separators.Discrete Mathematics, 55(2):221-232, 1985. doi:10.1016/0012-365X(85)90051-2. · Zbl 0572.05039 |
| [34] | Mikkel Thorup. All structured programs have small tree-width and good register allocation. Inf. Comput., 142(2):159-181, 1998. doi:10.1006/inco.1997.2697. · Zbl 0924.68023 |
| [35] | 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, · Zbl 1443.68213 |
| [36] | 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 |
| [37] | Mihalis Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77-79, 1981. · Zbl 0496.68033 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
