Fine-grained dichotomies for the Tutte Plane and Boolean #CSP
Jaeger et al. (Math Proc Camb Philos Soc 108(1):35–53, 1990) 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 (in: ICALP 2010, v...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer Nature
2018
|