Document Open Access Logo

The First Parameterized Algorithms and Computational Experiments Challenge

Authors Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, Frances A. Rosamond

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2016.30.pdf
  • Filesize: 0.5 MB
  • 9 pages

Document Identifiers

Subject Classification

Keywords
  • treewidth
  • feedback vertex set
  • contest
  • implementation challenge
  • FPT

Metrics

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

Abstract

In this article, the steering committee of the Parameterized Algorithms and Computational Experiments challenge (PACE) reports on the first iteration of the challenge. Where did PACE come from, how did it go, who won, and what's next?

Cite As Get BibTex

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 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 30:1-30:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.30

Author Details

Holger Dell
Thore Husfeldt
Bart M. P. Jansen
Petteri Kaski
Christian Komusiewicz
Frances A. Rosamond

References

  1. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebra. Discr., 8:277-284, 1987. URL: http://dx.doi.org/10.1137/0608024.
  2. Ann Becker, Reuven Bar-Yehuda, and Dan Geiger. Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. (JAIR), 12:219-234, 2000. URL: http://dx.doi.org/10.1613/jair.638.
  3. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: http://dx.doi.org/10.1137/S0097539793251219.
  4. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: http://dx.doi.org/10.1137/130947374.
  5. Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs. In Proc. 24th ESA, volume 57 of LIPIcs, pages 28:1-28:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.28.
  6. Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Kim Stevens. An O(2^O(k)n³) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst., 41(3):479-492, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1345-z.
  7. DIMACS graph coloring instances. URL: http://mat.gsia.cmu.edu/COLOR/instances.html.
  8. Rodney G. Downey and Michael R. Fellows. Parameterized computational feasibility. In Feasible Mathematics II, pages 219-244. Birkhauser, 1994. Google Scholar
  9. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci., 72(8):1386-1396, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2006.02.001.
  10. Yoichi Iwata. Linear-time kernelization for feedback vertex set. CoRR, abs/1608.01463, 2016. URL: http://arxiv.org/abs/1608.01463.
  11. Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput., 45(4):1377-1411, 2016. URL: http://dx.doi.org/10.1137/140962838.
  12. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proc. of a Symp. on the Complexity of Computer Computations, IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  13. 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. AAAI Press, 2011. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3771.
  14. Petteri Kaski. Engineering motif search for large graphs, 2015. URL: https://simons.berkeley.edu/talks/petteri-kaski-2015-11-05.
  15. 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.
  16. List of all submissions for track A, 2016. URL: https://github.com/holgerdell/PACE-treewidth-testbed/blob/github/pace2016-submissions.yaml.
  17. Networks project, 2016. URL: http://www.thenetworkcenter.nl.
  18. Parameterized Algorithms and Computational Experiments website, 2015. URL: http://pacechallenge.wordpress.com.
  19. Repository of all hidden and public inputs for track B on GitHub, 2016. URL: https://github.com/ckomus/PACE-fvs.
  20. Repository of control flow graphs on GitHub, 2016. URL: https://github.com/freetdi/CFGs.git.
  21. Repository of named graphs on GitHub, 2016. URL: https://github.com/freetdi/named-graphs.
  22. Schulze rankings of heuristic treewidth implementations, 2016. URL: https://github.com/holgerdell/PACE-treewidth-testbed/blob/github/logs/2016-08-13.02-08-25/ranks-he-se.txt.
  23. Markus Schulze. A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method. Social Choice and Welfare, 36(2):267-303, 2011. URL: http://dx.doi.org/10.1007/s00355-010-0475-4.
  24. 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.
  25. Treewidth testbed on GitHub, 2016. URL: https://github.com/holgerdell/PACE-treewidth-testbed.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »