Fine-grained dichotomies for the Tutte plane and Boolean #CSP
<br/>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],...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
2017
|