D 2016

Counting Linear Extensions: Parameterizations by Treewidth

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

Základní údaje

Originální název

Counting Linear Extensions: Parameterizations by Treewidth

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Sebastian ORDYNIAK (40 Rakousko), Eduard EIBEN (703 Slovensko) a Kanga KUSTAA (246 Finsko)

Vydání

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

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/16:00093946

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-015-6

ISSN

DOI

Klíčová slova anglicky

treewidth; linear extensions

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 27. 4. 2017 07:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.