Block interpolation: a framework for tight exponential-time counting complexity

DOI10.1016/j.ic.2018.02.008zbMath1394.68158arXiv1511.02910OpenAlexW2789507435WikidataQ115574501 ScholiaQ115574501MaRDI QIDQ1640999

Radu Curticapean

Publication date: 14 June 2018

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.02910

zbMATH Keywords

Tutte polynomialpermanentmatching polynomialcounting complexityindependent set polynomialexponential-time hypothesis

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Compactors for parameterized counting problems ⋮ Parameterised counting in logspace ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Unnamed Item ⋮ Counting Minimal Dominating Sets ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Parameterized and exact computation. 5th international symposium, IPEC 2010, Chennai, India, December 13--15, 2010. Proceedings
• Relations among MOD-classes
• Inapproximability of the Tutte polynomial
• Approximating the permanent of graphs with large factors
• Which problems have strongly exponential complexity?
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• Exponential Time Complexity of Weighted Counting of Independent Sets
• The Exponential Time Complexity of Computing the Probability That a Graph Is Connected
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
• The Complexity of the Counting Constraint Satisfaction Problem
• Holographic Algorithms
• A Computational Proof of Complexity of Some Restricted Counting Problems
• Hard Enumeration Problems in Geometry and Combinatorics
• Fine-grained dichotomies for the Tutte plane and Boolean #CSP
• On the computational complexity of the Jones and Tutte polynomials
• The Exponential Time Hypothesis and the Parameterized Clique Problem
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• On Problems as Hard as CNF-SAT
• The Complexity of Computing the Sign of the Tutte Polynomial
• Complexity of counting CSP with complex weights
• Complexity of the Cover Polynomial
• On the complexity of \(k\)-SAT

This page was built for publication: Block interpolation: a framework for tight exponential-time counting complexity