Document Open Access Logo

Counting Linear Extensions: Parameterizations by Treewidth

Authors Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.39.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Eduard Eiben
Robert Ganian
Kustaa Kangas
Sebastian Ordyniak

Cite As Get BibTex

Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.39

Abstract

We consider the #P-complete problem of counting the number of linear extensions of a poset (#LE); a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of #LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that #LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Algorithms. On the positive side we show that #LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph.

Subject Classification

Keywords
  • Partially ordered sets
  • Linear extensions
  • Parameterized Complexity
  • Structural parameters
  • Treewidth

Metrics

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

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308-340, 1991. Google Scholar
  2. Mike D Atkinson. On computing the number of linear extensions of a tree. Order, 7(1):23-25, 1990. Google Scholar
  3. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  4. Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996. Google Scholar
  5. Bostjan Bresar, Manoj Changat, Sandi Klavzar, Matjaz Kovse, Joseph Mathews, and Antony Mathews. Cover-incomparability graphs of posets. Order, 25(4):335-347, 2008. Google Scholar
  6. Graham Brightwell and Peter Winkler. Counting linear extensions is #P-complete. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC'91, pages 175-181, 1991. Google Scholar
  7. Russ Bubley and Martin Dyer. Faster random generation of linear extensions. Discrete Mathematics, 201(1-–3):81-88, 1999. Google Scholar
  8. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Karel De Loof, Hans De Meyer, and Bernard De Baets. Exploiting the lattice of ideals representation of a poset. Fundam. Inf., 71(2,3):309-321, February 2006. URL: http://dl.acm.org/citation.cfm?id=1227505.1227514.
  11. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  12. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  13. Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-17, January 1991. URL: http://dx.doi.org/10.1145/102782.102783.
  14. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Inf. Comput., 209(2):143-153, 2011. Google Scholar
  15. Stefan Felsner and Thibault Manneville. Linear extensions of N-free orders. Order, 32(2):147-155, 2014. URL: http://dx.doi.org/10.1007/s11083-014-9321-0.
  16. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM J. Comput., 33(4):892-922, 2004. Google Scholar
  17. Georg Gottlob, Reinhard Pichler, and Fang Wei. Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artificial Intelligence, 174(1):105-132, 2010. URL: http://dx.doi.org/10.1016/j.artint.2009.10.003.
  18. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1), 2007. Google Scholar
  19. M. Habib and R.H. Möhring. On some complexity properties of N-free posets and posets with bounded decomposition diameter. Discrete Mathematics, 63(2):157-182, 1987. URL: http://dx.doi.org/10.1016/0012-365X(87)90006-9.
  20. Michel Habib and Rolf H Möhring. Treewidth of cocomparability graphs and a new order-theoretic parameter. Order, 11(1):47-60, 1994. Google Scholar
  21. Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams. Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports, 3(8):40-72, 2013. URL: http://dx.doi.org/10.4230/DagRep.3.8.40.
  22. Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto. Counting linear extensions of sparse posets. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI 2016, New York City, USA, 2016. to appear. Google Scholar
  23. T. Kloks. Treewidth: Computations and Approximations. Springer Verlag, Berlin, 1994. Google Scholar
  24. Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari. Probabilistic preference logic networks. In Torsten Schaub, Gerhard Friedrich, and Barry O'Sullivan, editors, ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), volume 263 of Frontiers in Artificial Intelligence and Applications, pages 561-566. IOS Press, 2014. Google Scholar
  25. Heikki Mannila and Christopher Meek. Global partial orders from sequential data. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'00, pages 161-168, New York, NY, USA, 2000. ACM. URL: http://dx.doi.org/10.1145/347090.347122.
  26. Rolf H. Möhring. Algorithms and Order, chapter Computationally Tractable Classes of Ordered Sets, pages 105-193. Springer Netherlands, 1989. Google Scholar
  27. Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Convex rank tests and semigraphoids. SIAM Journal on Discrete Mathematics, 23(3):1117-1134, 2009. URL: http://dx.doi.org/10.1137/080715822.
  28. Teppo Mikael Niinimäki and Mikko Koivisto. Annealed importance sampling for structure learning in Bayesian networks. In IJCAI. IJCAI/AAAI, 2013. Google Scholar
  29. Daniel Paulusma, Friedrich Slivovsky, and Stefan Szeider. Model counting for CNF formulas of bounded modular treewidth. Algorithmica, pages 1-27, 2015. URL: http://dx.doi.org/10.1007/s00453-015-0030-x.
  30. Marcin Peczarski. New results in minimum-comparison sorting. Algorithmica, 40(2):133-145, July 2004. URL: http://dx.doi.org/10.1007/s00453-004-1100-7.
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