Counting Linear Extensions: Parameterizations by Treewidth

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113714" target="_blank" >RIV/00216224:14330/19:00113714 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00453-018-0496-4" target="_blank" >https://doi.org/10.1007/s00453-018-0496-4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-018-0496-4" target="_blank" >10.1007/s00453-018-0496-4</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Counting Linear Extensions: Parameterizations by Treewidth

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Counting Linear Extensions: Parameterizations by Treewidth

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

81

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

27

Strana od-do

1657-1683

Kód UT WoS článku

000465431800013

EID výsledku v databázi Scopus

2-s2.0-85053424850