Document Open Access Logo

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth

Authors Łukasz Kowalik , Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.37.pdf
  • Filesize: 0.59 MB
  • 18 pages

Document Identifiers

Author Details

Łukasz Kowalik
  • Institute of Informatics, University of Warsaw, Poland
Marcin Mucha
  • Institute of Informatics, University of Warsaw, Poland
Wojciech Nadara
  • Institute of Informatics, University of Warsaw, Poland
Marcin Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Manuel Sorge
  • Institute of Informatics, University of Warsaw, Poland
Piotr Wygocki
  • Institute of Informatics, University of Warsaw, Poland

Funding

This work has been supported by the ERC Starting Grant TOTAL, Grant Agreement No 677651 (Ł.K., M.M), the ERC Starting Grant CUTACOMBS, Grant Agreement No 714704 (W.N., M.P., M.S.) and by the Polish National Science Center Grant PRELUDIM 2018/29/N/ST6/00676 (P.W.). The publication of proceedings of PACE 2020 has been supported by the University of Warsaw and the European Research Council (ERC) via European Union’s Horizon 2020 research and innovation programme Grant Agreement no. 714704.

Acknowledgements

The PACE challenge was supported by Networks [Networks project, 2017] and University of Warsaw. The prize money (EUR 4000) was given through the generosity of Networks [Networks project, 2017]. We are grateful to the whole optil.io team, led by Szymon Wasik, and especially to Jan Badura for the fruitful collaboration and for hosting the competition at https://www.optil.io on-line judge system. Special thanks go to Felix Reidl, who designed the eye-catching PACE 2020 poster.

Cite As Get BibTex

Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki. The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.IPEC.2020.37

Abstract

This year’s Parameterized Algorithms and Computational Experiments challenge (PACE 2020) was devoted to the problem of computing the treedepth of a given graph. Altogether 51 participants from 20 teams, 12 countries and 3 continents submitted their implementations to the competition.
In this report, we describe the setup of the challenge, the selection of benchmark instances and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers and the differences in their performance on our benchmark dataset.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • computing treedepth
  • contest
  • implementation challenge
  • FPT

Metrics

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

References

  1. Max Bannach. maxbannach/fluid: pace-2020, June 2020. URL: https://doi.org/10.5281/zenodo.3871709.
  2. Max Bannach. maxbannach/pid-star: pace-2020, June 2020. URL: https://doi.org/10.5281/zenodo.3871800.
  3. Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE solver description: Fluid. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 27:1-27:3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.27.
  4. Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE solver description: PID^*. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 28:1-28:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.28.
  5. Anne Berry, Jean Paul Bordat, and Olivier Cogis. Generating all the minimal separators of a graph. Int. J. Found. Comput. Sci., 11(3):397-403, 2000. URL: https://doi.org/10.1142/S0129054100000211.
  6. Narek Bojikian, Alexander van der Grinten, Falko Hegerfeld, Laurence Alec Kluge, and Stefan Kratsch. Pace-challenge-2020-hu-berlin-exact-track, June 2020. URL: https://doi.org/10.5281/zenodo.3894555.
  7. Édouard Bonnet and Florian Sikora. The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1-26:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.26.
  8. Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep. PACE solver description: tdull. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 29:1-29:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.29.
  9. Wojciech Czerwinski, Wojciech Nadara, and Marcin Pilipczuk. Improved bounds for the excluded-minor approximation of treedepth. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 34:1-34:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.34.
  10. Philip de Bruin. Philipdb/treedepth-exact: Submission for pace, May 2020. URL: https://doi.org/10.5281/zenodo.3866006.
  11. Mees de Vries, Ruben Brokkelkamp, Raymond van Venetië, and Jan Westerdiep. tdull, June 2020. URL: https://doi.org/10.5281/zenodo.3881472.
  12. 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: https://doi.org/10.4230/LIPIcs.IPEC.2016.30.
  13. 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: https://doi.org/10.4230/LIPIcs.IPEC.2017.30.
  14. Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko Müller. On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discret. Appl. Math., 98(1-2):39-63, 1999. URL: https://doi.org/10.1016/S0166-218X(99)00179-1.
  15. Gabriel Duarte, Samuel Eduardo, and Uéverton Souza. Ufffptteam, June 2020. URL: https://doi.org/10.5281/zenodo.3872029.
  16. M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher. The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper). In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1-25:23, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.25.
  17. Oleg Evsees, Alexander Zemlyanskiy, and Igor Kozin. Gensol.exe, June 2020. URL: https://doi.org/10.5281/zenodo.3882767.
  18. Robert Ganian, Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. Sat-encodings for treecut width and treedepth. In Stephen G. Kobourov and Henning Meyerhenke, editors, Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019, pages 117-129. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975499.10.
  19. Marcelo Garlet Milani. td-milani: A treedepth solver, June 2020. URL: https://doi.org/10.5281/zenodo.3885116.
  20. Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. URL: https://doi.org/10.1137/0710032.
  21. Alan George and Joseph W.H. Liu. The evolution of the minimum degree ordering algorithm. SIAM Review, 31(1):1-19, 1989. URL: https://doi.org/10.1137/1031001.
  22. Stéphane Grandcolas. sga, June 2020. URL: https://doi.org/10.5281/zenodo.3884054.
  23. Michael Hamann and Ben Strasser. Graph bisection with pareto optimization. ACM J. Exp. Algorithmics, 23, 2018. URL: https://doi.org/10.1145/3173045.
  24. Minoru Kanehisa and Susumu Goto. KEGG: Kyoto encyclopedia of genes and genomes. Nucleic acids research, 28(1):27-30, 2000. Google Scholar
  25. Jun Kawahara, Toshiki Saitoh, Akira Suzuki, Toshiyuki Takase, and Katsuhisa Yamanaka. wankosoba: Exact treedepth decomposition solver, June 2020. URL: https://doi.org/10.5281/zenodo.3894127.
  26. Ken-ichi Kawarabayashi and Benjamin Rossman. A polynomial excluded-minor approximation of treedepth. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 234-246. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.17.
  27. Yasuaki Kobayashi and Hisao Tamaki. Treedepth parameterized by vertex cover number. 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 18:1-18:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.18.
  28. Tuukka Korhonen. Pace 2020 exact treedepth submission: sms, June 2020. URL: https://doi.org/10.5281/zenodo.3872898.
  29. Tuukka Korhonen. PACE solver description: Sms. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 30:1-30:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.30.
  30. A. Naldi, D. Berenguier, A. Fauré, F. Lopez, D. Thieffry, and C. Chaouiya. Logical modelling of regulatory networks with ginsim 2.3. Biosystems, 97(2):134-139, 2009. URL: https://doi.org/10.1016/j.biosystems.2009.04.008.
  31. Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. URL: https://doi.org/10.1016/j.ejc.2005.01.010.
  32. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  33. Jaroslav Nesetril and Patrice Ossona de Mendez. On low tree-depth decompositions. Graphs and Combinatorics, 31(6):1941-1963, 2015. URL: https://doi.org/10.1007/s00373-015-1569-7.
  34. Network repository. URL: http://networkrepository.com/.
  35. Networks project, 2017. URL: http://www.thenetworkcenter.nl.
  36. Ferran Parés, Dario Garcia Gasulla, Armand Vilalta, Jonatan Moreno, Eduard Ayguadé, Jesús Labarta, Ulises Cortés, and Toyotaro Suzumura. Fluid communities: A competitive, scalable and diverse community detection algorithm. In Chantal Cherifi, Hocine Cherifi, Márton Karsai, and Mirco Musolesi, editors, Complex Networks & Their Applications VI, pages 229-240, Cham, 2018. Springer International Publishing. Google Scholar
  37. Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 931-942. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_77.
  38. Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. Google Scholar
  39. Dmitry Sayutin. PACE 2020 Magnolia Tree Depth solver (DP & Sat based), June 2020. URL: https://doi.org/10.5281/zenodo.3888908.
  40. Alejandro A. Schäffer. Optimal node ranking of trees in linear time. Inf. Process. Lett., 33(2):91-96, 1989. URL: https://doi.org/10.1016/0020-0190(89)90161-0.
  41. Aman Singal. Pace2020 - heuristic treedepth, June 2020. URL: https://doi.org/10.5281/zenodo.3871918.
  42. Chris Stark, Bobby-Joe Breitkreutz, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, and Mike Tyers. Biogrid: a general repository for interaction datasets. Nucleic acids research, 34:D535-D539, 2006. Google Scholar
  43. Ben Strasser. Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR, abs/1709.08949, 2017. URL: http://arxiv.org/abs/1709.08949.
  44. Ben Strasser. Flowcutter pace 2020 submission, May 2020. URL: https://doi.org/10.5281/zenodo.3870928.
  45. Ben Strasser. PACE solver description: Tree depth with flowcutter. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 32:1-32:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.32.
  46. Sylwester Swat. swacisko/pace-2020: First release of extreem, June 2020. URL: https://doi.org/10.5281/zenodo.3873126.
  47. Sylwester Swat. PACE solver description: Finding elimination trees using extreem - a heuristic solver for the treedepth decomposition problem. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 33:1-33:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.33.
  48. Damian Szklarczyk, Annika L Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta-Cepas, Milan Simonovic, Nadezhda T Doncheva, John H Morris, Peer Bork, et al. String v11: protein-protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets. Nucleic acids research, 47(D1):D607-D613, 2019. Google Scholar
  49. Ken Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph. Discret. Appl. Math., 158(15):1660-1667, 2010. URL: https://doi.org/10.1016/j.dam.2010.05.013.
  50. 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: https://doi.org/10.4230/LIPIcs.ESA.2017.68.
  51. Hisao Tamaki. Computing treewidth via exact and heuristic lists of minimal separators. In Ilias S. Kotsireas, Panos M. Pardalos, Konstantinos E. Parsopoulos, Dimitris Souravlias, and Arsenis Tsokas, editors, Analysis of Experimental Algorithms - Special Event, SEA² 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers, volume 11544 of Lecture Notes in Computer Science, pages 219-236. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34029-2_15.
  52. Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. Journal of Combinatorial Optimization, 37(4):1283-1311, 2019. URL: https://doi.org/10.1007/s10878-018-0353-z.
  53. James Trimble. An algorithm for the exact treedepth problem. In Simone Faro and Domenico Cantone, editors, 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy, volume 160 of LIPIcs, pages 19:1-19:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.19.
  54. James Trimble. jamestrimble/pace2020-treedepth-solvers: v1.0.0, June 2020. URL: https://doi.org/10.5281/zenodo.3881441.
  55. James Trimble. PACE solver description: Bute-plus: A bottom-up exact solver for treedepth. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 34:1-34:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.34.
  56. James Trimble. PACE solver description: Tweed-plus: A subtree-improving heuristic solver for treedepth. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 35:1-35:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.35.
  57. Szymon Wasik, Maciej Antczak, Jan Badura, Artur Laskowski, and Tomasz Sternal. Optil.io: Cloud based platform for solving optimization problems using crowdsourcing approach. In Proceedings of the 19th ACM Conference on Computer Supported Cooperative Work and Social Computing Companion, CSCW '16 Companion, page 433–436, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2818052.2869098.
  58. Marcin Wrochna. marcinwrochna/sallow: pace-2020, May 2020. URL: https://doi.org/10.5281/zenodo.3870565.
  59. Marcin Wrochna. PACE solver description: Sallow: a heuristic algorithm for treedepth decompositions. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 36:1-36:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.36.
  60. Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn. PACE solver description: Computing exact treedepth via minimal separators. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 31:1-31:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.xx.
  61. Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn. solver from xuzijian629, May 2020. URL: https://doi.org/10.5281/zenodo.3870624.
  62. Zijian Xu and Vorapong Suppakitpaisarn. On the size of minimal separators for treedepth decomposition, 2020. URL: http://arxiv.org/abs/2008.09822.
  63. Marinka Zitnik, Rok Sosič, Sagar Maheshwari, and Jure Leskovec. BioSNAP Datasets: Stanford biomedical network dataset collection. http://snap.stanford.edu/biodata, August 2018.
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