License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.39
URN: urn:nbn:de:0030-drops-63903
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6390/
Go to the corresponding LIPIcs Volume Portal

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

Counting Linear Extensions: Parameterizations by Treewidth

pdf-format:
LIPIcs-ESA-2016-39.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{eiben_et_al:LIPIcs:2016:6390,
  author =	{Eduard Eiben and Robert Ganian and Kustaa Kangas and Sebastian Ordyniak},
  title =	{{Counting Linear Extensions: Parameterizations by Treewidth}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6390},
  URN =		{urn:nbn:de:0030-drops-63903},
  doi =		{10.4230/LIPIcs.ESA.2016.39},
  annote =	{Keywords: Partially ordered sets, Linear extensions, Parameterized Complexity, Structural parameters, Treewidth}
}

Keywords: Partially ordered sets, Linear extensions, Parameterized Complexity, Structural parameters, Treewidth
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI