J 2019

Counting Linear Extensions: Parameterizations by Treewidth

EIBEN, Eduard, Robert GANIAN, Kustaa KANGAS a Sebastian ORDYNIAK

Základní údaje

Originální název

Counting Linear Extensions: Parameterizations by Treewidth

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí), Kustaa KANGAS (246 Finsko) a Sebastian ORDYNIAK (276 Německo)

Vydání

Algorithmica, Springer, 2019, 0178-4617

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.650

Kód RIV

RIV/00216224:14330/19:00113714

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000465431800013

Klíčová slova anglicky

Parameterized Complexity
Změněno: 14. 5. 2020 10:41, Mgr. Michal Petr

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 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.