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

DOI10.1007/s00453-018-0472-zzbMath1414.68034OpenAlexW3021067957MaRDI QIDQ1725642

Marc Roth, Holger Dell, Cornelius Brand

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6942/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Parameterized Counting and Cayley Graph Expanders

Uses Software

• tutte_bhkk

Cites Work

• The complexity of computing the permanent
• Which problems have strongly exponential complexity?
• Block interpolation: a framework for tight exponential-time counting complexity
• Complexity of generalized satisfiability counting problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Exponential Time Complexity of Computing the Probability That a Graph Is Connected
• Computational Complexity of Holant Problems
• PP is as Hard as the Polynomial-Time Hierarchy
• Combinatorics, Complexity, and Chance
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• On the computational complexity of the Jones and Tutte polynomials
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Complexity of counting CSP with complex weights
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item

This page was built for publication: Fine-grained dichotomies for the Tutte plane and Boolean \#CSP