Document Open Access Logo

The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration

Authors Holger Dell, Christian Komusiewicz, Nimrod Talmon, Mathias Weller

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.30.pdf
  • Filesize: 0.61 MB
  • 12 pages

Document Identifiers

Author Details

Holger Dell
Christian Komusiewicz
Nimrod Talmon
Mathias Weller

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.30

Abstract

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.

Subject Classification

Keywords
  • treewidth
  • minimum fill-in
  • 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, Integration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings, 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, 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, SEA 2017, June 21-23, 2017, London, UK, volume 75 of LIPIcs, pages 28:1-28:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.SEA.2017.28.
  3. 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 Constraint Programming - 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings, volume 9075 of Lecture Notes in Computer Science, pages 47-64. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-18008-3_4.
  4. Hans L. Bodlaender, Pinar Heggernes, and Yngve Villanger. Faster parameterized algorithms for minimum fill-in. Algorithmica, 61(4):817-838, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9421-1.
  5. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput., 31(1):212-232, 2001. URL: http://dx.doi.org/10.1137/S0097539799359683.
  6. Peter Buneman. A characterisation of rigid circuit graphs. Discrete Mathematics, 9(3):205-212, 1974. URL: http://dx.doi.org/10.1016/0012-365X(74)90002-8.
  7. Benjamin A. Burton, Ryan Budney, William Pettersson, et al. Regina: Software for low-dimensional topology, 1999-2016. URL: http://regina-normal.github.io.
  8. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58(4):171-176, 1996. URL: http://dx.doi.org/10.1016/0020-0190(96)00050-6.
  9. 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 on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 28:1-28:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.28.
  10. 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 Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 30:1-30:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.30.
  11. 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 Evolution, 31(7):1923-1928, 2014. URL: http://dx.doi.org/10.1093/molbev/msu132.
  12. 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, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, 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.
  13. 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.
  14. 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. URL: http://dx.doi.org/10.1137/050643350.
  15. Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput., 42(6):2197-2216, 2013. URL: http://dx.doi.org/10.1137/11085390X.
  16. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  17. Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging treewidth heuristics. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 13:1-13:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.13.
  18. 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, WABI 2012, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, volume 7534 of Lecture Notes in Computer Science, pages 93-105. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33122-0_8.
  19. Yoichi Iwata. Linear-time kernelization for feedback vertex set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 68:1-68:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.68.
  20. 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 Mexico, USA, 20-22 November 1994, pages 780-791. IEEE Computer Society, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365715.
  21. 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, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. AAAI Press, 2011. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3771.
  22. Masashi Kiyomi, Yoshio Okamoto, and Yota Otachi. On the treewidth of toroidal grids. Discrete Applied Mathematics, 198:303-306, 2016. URL: http://dx.doi.org/10.1016/j.dam.2015.06.027.
  23. 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 Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings, 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.
  24. Matrix market. URL: http://math.nist.gov/MatrixMarket/.
  25. Multiple-alignment to character-state intersection graph converter, 2017. URL: https://github.com/PACE-challenge/phylo_converter.
  26. 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. URL: http://dx.doi.org/10.1137/S0097539798336073.
  27. Network repository. URL: http://networkrepository.com/.
  28. Networks project, 2017. URL: http://www.thenetworkcenter.nl.
  29. Parameterized Algorithms and Computational Experiments website, 2015-2017. URL: https://pacechallenge.wordpress.com.
  30. 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 2017 at http://orthomam.univ-montp2.fr. URL: http://dx.doi.org/10.1186/1471-2148-7-241.
  31. Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 68:1-68:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.68.
  32. Robert Endre Tarjan. Decomposition by clique separators. Discrete Mathematics, 55(2):221-232, 1985. URL: http://dx.doi.org/10.1016/0012-365X(85)90051-2.
  33. Mikkel Thorup. All structured programs have small tree-width and good register allocation. Inf. Comput., 142(2):159-181, 1998. URL: http://dx.doi.org/10.1006/inco.1997.2697.
  34. 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.
  35. 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.
  36. Mihalis Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77-79, 1981. URL: http://dx.doi.org/10.1137/0602010.
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 About DROPS Imprint Privacy Contact