Exponential Time Complexity of the Permanent and the Tutte Polynomial
From MaRDI portal
Publication:4962155
DOI10.1145/2635812zbMath1398.68191arXiv1206.1775OpenAlexW2021372200MaRDI QIDQ4962155
Holger Dell, Nina Taslaman, Thore Husfeldt, Martin Wahlen, Dániel Marx
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1206.1775
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Computing the permanent modulo a prime power ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP ⋮ Counting the number of perfect matchings, and generalized decision trees ⋮ Approximation algorithms for replenishment problems with fixed turnover times ⋮ Lower bounds for the happy coloring problems ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
