Counting Linear Extensions : Parameterizations by Treewidth
- Submitting institution
-
Royal Holloway and Bedford New College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 35187111
- Type
- D - Journal article
- DOI
-
10.1007/s00453-018-0496-4
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 1657
- Volume
- 81
- Issue
- -
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- September
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Counting the number of linear extension of a poset (#LE) is a fundamental problem in order theory with applications in a wide variety of areas. The main contribution of the paper is the introduction of a counting technique for showing hardness to the parameterized complexity community. This technique allows us to show that #LE is not fixed parameter tractable parameterized by the treewidth of the Hasse diagram, providing the first natural counting problem that is not fixed parameter tractable even though its decision version is trivial. This also resolves an open problem posed in the Dagstuhl seminar on Exact Algorithms.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -