Conference item icon

Conference item

Fine-grained dichotomies for the Tutte plane and Boolean #CSP

Abstract:

Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén [9] and Husfeldt and Taslaman [12], in combination with the results of Curticapean [7], extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line y = 1, whic... Expand abstract
Publication status:
Published
Peer review status:
Reviewed (other)

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.IPEC.2016.9

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Merton, Merton College
Department:
Unknown
Role:
Author
Publisher:
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Publisher's website
Journal:
11th International Symposium on Parameterized and Exact Computation
Volume:
63
Issue:
9
Pages:
9:1-9:14
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Host title:
11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Publication date:
2017-01-01
Acceptance date:
2016-07-24
DOI:
ISSN:
1868-8969
Source identifiers:
1068854
ISBN:
9783959770231
Pubs id:
pubs:1068854
UUID:
uuid:fe0fd728-8097-4c55-82e5-1f2c28312215
Local pid:
pubs:1068854
Deposit date:
2019-10-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP