D 2016

Counting Linear Extensions: Parameterizations by Treewidth

GANIAN, Robert, Sebastian ORDYNIAK, Eduard EIBEN and Kanga KUSTAA

Basic information

Original name

Counting Linear Extensions: Parameterizations by Treewidth

Authors

GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Sebastian ORDYNIAK (40 Austria), Eduard EIBEN (703 Slovakia) and Kanga KUSTAA (246 Finland)

Edition

Aarhus, Denmark, 24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark, p. 1-18, 18 pp. 2016

Publisher

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/16:00093946

Organization unit

Faculty of Informatics

ISBN

978-3-95977-015-6

ISSN

DOI

Keywords in English

treewidth; linear extensions

Tags

Tags

International impact, Reviewed
Změněno: 27/4/2017 07:09, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

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 com- plexity 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 xed- parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Al- gorithms. On the positive side we show that #LE becomes xed-parameter tractable parameterized by the treewidth of the incomparability graph.