Exponential Time Complexity of the Permanent and the Tutte Polynomial

DOI10.1145/2635812MaRDI QIDQ4962155zbMATH OpenOpenAlexFDO

Authors Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wahlen

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, http://eprints.sztaki.hu/8205/

zbMATH Keywords

computational complexitycounting problemsexponential time hypothesispermanentTutte polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. (b) The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). (c) The Tutte polynomial of an n-vertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x,y) in the case of multigraphs, and it cannot be computed in time exp(o(n/polylog n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n-variable 3-CNF formulas cannot be decided in time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH, namely that the satisfying assignments cannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d-CNF formulas to the counting setting.

Recommendations

• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• The exact complexity of the Tutte polynomial
• Tutte polynomials computable in polynomial time
• Exponential time paradigms through the polynomial time lens
• FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• On Parameterized Exponential Time Complexity
• On parameterized exponential time complexity
• The exponential time hypothesis and the parameterized clique problem

Cited in

(40)

• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Counting the number of perfect matchings, and generalized decision trees
• Completeness, approximability and exponential time results for counting problems with easy decision version
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Computing the permanent modulo a prime power
• The relative exponential time complexity of approximate counting satisfying assignments
• scientific article; zbMATH DE number 5839812 (Why is no real title available?)
• The relative exponential time complexity of approximate counting satisfying assignments
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Counting problems in parameterized complexity
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• Counting solutions to polynomial systems via reductions
• Below all subsets for some permutational counting problems
• Approximation algorithms for replenishment problems with fixed turnover times
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Parameterized Counting and Cayley Graph Expanders
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Proper colorability of segment intersection graphs
• Parameterized approximation algorithms and lower bounds for k-center clustering and variants
• The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
• Enumerative and structural aspects of anagrams without fixed letters
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
• Exponential lower bounds via exponential sums
• ETH lower bounds for n-queens: time waits for nobody
• Sub-exponential time lower bounds for \#VC and \#Matching on 3-regular graphs
• Approximation results on resource leveling problems
• Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
• On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• On exponential-time hypotheses, derandomization, and circuit lower bounds
• A framework of quantum strong exponential-time hypotheses
• Tractability of packing vertex-disjoint a-paths under length constraints
• Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Can you link up with treewidth?
• Can you link up with treewidth?

This page was built for publication: Exponential Time Complexity of the Permanent and the Tutte Polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962155)