PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Time Complexity of the Permanent and the Tutte Polynomial

Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wáhlen

arXiv:1206.1775v1cs.CCcs.DSmath.CO

TL;DR

Known #P-hardness does not distinguish problems requiring exponential time from those admitting subexponential algorithms, as the planar Tutte polynomial illustrates. The paper introduces #ETH, transfers sparsification to counting d-CNF formulas, and uses isolation-based reductions where interpolation would weaken the bounds. Under #ETH, Tutte evaluation has exp(Ω(n)) lower bounds except at |y| = 1; under rETH, no randomized exp(o(m)) algorithm computes independent sets (m edges) or #2-Sat (m clauses).

  • Problem

    Known #P-hardness does not distinguish problems requiring exponential time from those admitting subexponential algorithms, as the planar Tutte polynomial illustrates.

    Source: §1 · p. 2

  • Method

    The paper introduces #ETH, transfers sparsification to counting d-CNF formulas, and uses isolation-based reductions where interpolation would weaken the bounds.

    Source: Complexity assumptions · p. 5, Results: The Permanent · p. 7

  • Results

    Under #ETH, Tutte evaluation has exp(Ω(n)) lower bounds except at |y| = 1; under rETH, no randomized exp(o(m)) algorithm computes independent sets (m edges) or #2-Sat (m clauses).

    Source: Computing the Tutte polynomial · p. 4, Results: Counting Independent Sets · p. 6

  • Takeaways & Limitations

    The bounds suggest that known exp(O(n)) algorithms for the permanent and Tutte polynomial are unlikely to admit substantial improvement under the stated assumptions.

    Source: §1 · p. 2

    Tutte lower bounds leave the line y = 1 open except at (1, 1), and some simple-graph bounds are only exponential up to a polylogarithmic factor.

    Source: §7 · p. 28

Abstract

from arXiv · show

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.

1. Introduction

The introduction argues that polynomial-time hardness alone does not distinguish exponential from subexponential algorithms, and presents conditional lower bounds for counting problems, the permanent, and Tutte evaluations. It develops #ETH and related reductions to establish these bounds.

1. Introduction

  • The lower bounds address known exp(O(n)) algorithms for the permanent and Tutte polynomial, both based on inclusion–exclusion, showing that substantial improvement is unlikely under the stated assumptions.The Tutte bound is stated to match the exp(O(n)) algorithm from [BHK+08], except on |y| = 1.Source: §1 · p. 2, Computing the Tutte polynomial · p. 4
  • Under #ETH, Tutte evaluation has exp(Ω(n)) lower bounds except at |y| = 1; for simple graphs, some bounds lose a polylogarithmic factor, while planar graphs admit exp(O(√n)) algorithms.The paper also notes that its lower bounds for sparse and simple graphs do not hold everywhere or always match the multigraph bound.Source: Computing the Tutte polynomial · p. 4, Results: The Tutte Polynomial · p. 8
  • The counting sparsification result gives an equivalent formulation of #ETH: for every integer d ≥3, #d-Sat cannot be solved in time exp(c · m) for some constant c > 0.The paper transfers the sparsification lemma to counting d-CNF formulas, making the clause-count parameter usable in reductions.Source: Complexity assumptions · p. 5
  • Under rETH, counting independent sets and #2-Sat cannot be computed in time exp(o(m)), where m is the number of edges or clauses, respectively.The isolation lemma avoids interpolation’s polylogarithmic loss, yielding an asymptotically tight bound but requiring rETH.Source: Results: Counting Independent Sets · p. 6
  • For permanents, #ETH rules out exp(o(m)) for Perm−1,0,1 and Perm, and exp(o(m/log n)) for Perm0,1; rETH strengthens the 0-1 bound to exp(o(m)).The 0-1 bound under #ETH uses logarithmic-size gadgets to simulate weights; the rETH proof uses isolation and avoids interpolation.Source: Results: The Permanent · p. 7
  • The paper’s conditional lower bounds also apply to related graph problems, including Ising and Potts partition functions, reliability, chromatic and flow polynomials, and several multigraph counting problems.The listed multigraph problems include perfect matchings, cycle covers, connected spanning subgraphs, nowhere-zero flows, and acyclic orientations.Source: Consequences · pp. 8–9

2. Counting Independent Sets

Under rETH, the section proves that counting all independent sets and counting satisfying assignments of 2-CNF formulas require randomized time exp(Ω(m)), where m is the number of edges or clauses, respectively. Its reduction encodes Unique 3-Sat instances as graphs whose independent-set count has the same parity as the number of satisfying assignments.

Theorem 1.2

  • Under rETH, no randomized algorithm counts all independent sets in time exp(o(m)) or solves #2-Sat in time exp(o(m)), with m edges or clauses, respectively.The reduction uses the randomized hardness of Unique 3-Sat.Source: §2 · p. 9

Reduction from Unique 3-Sat

  • The reduction builds a graph with O(m) edges using paired literal vertices, seven clause vertices for satisfying partial assignments, consistency edges, and guard vertices.Each clause gadget is a clique; guards are added for every variable and clause.Source: §2 · pp. 9–10

Parity argument

  • Good independent sets correspond to satisfying assignments, while bad independent sets pair off by toggling the first guard whose neighbourhood is disjoint from the set.The pairing is a fixed-point-free involution, so the graph’s independent-set count has the same parity as the number of satisfying assignments.Source: §2 · p. 10

Hardness consequence

  • An exp(o(m))-time algorithm for counting independent sets modulo 2 would solve Unique 3-Sat in exp(o(m)) time, contradicting its rETH lower bound.The cited lower bound for Unique 3-Sat is exp(o(m)).Source: §2 · pp. 9–10

Reduction to #2-Sat

  • For any graph, introducing one variable per vertex and one clause (u ∨ v) per edge makes satisfying assignments correspond one-to-one with independent sets.This reduction transfers the independent-set hardness to #2-Sat.Source: §2 · p. 10

3. The Permanent

The section establishes conditional lower bounds for permanent variants through a reduction chain from #3-Sat, with separate bounds under #ETH and rETH. Its reductions use weighted gadgets, interpolation, and weight-simulation gadgets while tracking instance sizes.

3. The Permanent

  • Under #ETH, Perm−1,0,1 and Perm require exp(Ω(m)) time, while Perm0,1 requires exp(Ω(m/log n)) time; under rETH, Perm0,1 requires exp(Ω(m)) time.The reduction chain is #3-Sat ≼ Perm−1,0,1 ≼ Perm[0,n] ≼ Perm0,1.Source: §3 · p. 10
  • The weighted reduction maps a formula with m clauses to a graph with O(m) edges, whose permanent equals (−2)^i times the number of satisfying assignments.The preprocessing makes the counts of positive and negative occurrences equal, so i is constant over assignments.Source: §3 · pp. 10–11
  • A selector gadget encodes each variable’s truth choice, clause gadgets exclude the all-false configuration, and equality gadgets connect selector literals to their clause occurrences.The equality gadget contributes −1 when all four outer edges are taken, +2 when none are taken, and 0 otherwise.Source: Figure 2 · p. 11, §3 · p. 11
  • Interpolating the permanent as a degree-at-most-n polynomial in the −1 loop weight recovers the original permanent from d+1 queries with at most m edges each.The queried weights are a = 0, …, d, and evaluating the interpolated polynomial at −1 returns per G.Source: §3 · p. 12
  • Replacing edges of weight a with unweighted gadgets preserves the permanent but increases the edge count to at most O(m + n log n), yielding the exp(o(m/log n)) lower bound.Parallel paths correspond to addition and serial edges to multiplication.Source: §3 · pp. 10, 12, Figure 3 · p. 12
  • Under rETH, the reduction from Unique 3-Sat replaces each −1 edge by a weight-2 gadget and distinguishes zero from one satisfying assignment using the permanent modulo 3.The resulting residues are 0 for an unsatisfiable formula and 1 when it has exactly one satisfying assignment.Source: §3 · pp. 10, 12

4. Hyperbolas in the Tutte plane

The section proves #ETH lower bounds for computing coefficients of Tutte-polynomial restrictions to fixed hyperbolas. Its reductions use MaxCut for q=2 and 3-terminal minimum cuts for q≠1,2, with deletion–contraction and graph stretching extending hardness to simple graphs.

q = 2

  • Under #ETH, computing coefficients of Z(G; 2, w) for a simple graph cannot be done in exp(o(m)) time, via a reduction from #MaxCut.The coefficient of (1 + w)^(m−c) counts cuts of size c, so these coefficients encode the number of maximum cuts.Source: The Ising Hyperbola · p. 13, A maximum cut · p. 13
  • For q=2, the Fortuin–Kasteleyn representation connects the Ising polynomial’s coefficients to cut counts, making #MaxCut the hardness source.The coefficient of (1 + w)^(m−c) in Z(G; 2, w) is the number of cuts of size c.Source: A maximum cut · p. 13, The Ising Hyperbola · p. 13

Multivariate formulation

q ≠ 1, 2

  • For rational q≠1,2, coefficients of Z0(G; q, w) remain exp(o(m))-hard on simple graphs, even when |T|=3.The reduction uses a multivariate Tutte polynomial with two edge weights, one negative, to encode 3-terminal minimum cuts.Source: Three-terminal minimum cut · pp. 14–15
  • Adding a triangle between the three terminals makes the coefficient sequence reveal the number of 3-terminal minimum cuts in the original graph.The reduction cancels contributions from edge subsets that already connect a pair of terminals; the smallest cut size and its coefficient recover the minimum-cut count.Source: Three-terminal minimum cut · pp. 15–16
  • Deletion–contraction removes the three negative-weight edges, and 3-stretching yields simple graphs while preserving the reduction to single-weight coefficients.The resulting graphs have at most n + 2m vertices and 3m edges; the coefficient-hardness conclusion applies to Z0, and to Z when q≠0,1,2.Source: General Hyperbolas · pp. 16–17

5. Individual Points for Multigraphs

The section transfers coefficient hardness on hyperbolas to individual Tutte-polynomial evaluation points for multigraphs. Thickening and interpolation give exp(o(n)) lower bounds at most points, with stated exceptions.

Individual points

  • Thickening and interpolation relocate coefficient hardness from hyperbolas to individual points in the Tutte plane.The thickened graphs retain the same vertex count, enabling the lower bound in terms of n.Source: §5 · pp. 17–18
  • The tight n-vertex bound is not established for y∈{0,±1}, where thickening fails completely.The stated method covers most, not all, points in the Tutte plane.Source: §5 · p. 17
  • For rational (q,w) with q≠1 and w∉{0,−1,−2}, evaluating Z(G; q, w) on multigraphs cannot be done in exp(o(n)) time under #ETH.The proof uses thickening to obtain distinct weight shifts, then interpolation to recover polynomial coefficients.Source: §5 · p. 18

6. Individual Points for Simple Graphs

This section establishes lower bounds for Tutte-polynomial evaluation at individual points on simple graphs, using Theta inflations and interpolation and treating the reliability line separately with Wump inflations for specified weight ranges. Under #ETH, for every nonzero rational w, computing Z0(G; 0, w) on a simple graph with m edges requires time exp(Ω(m/log² m)).

Theta inflations

  • For most Tutte-plane points, the result makes points as hard as the entire hyperbola on which they lie, with a polylogarithmic loss in the exponent; on y = −1, three known polynomial-time points are excluded.The y = −1 line is notable because the passage reports no other good exponential lower bounds there, even for more general graph classes.Source: §6 · p. 18
  • For rational (q, w) with q not in {0, 1}, w ≠ 0, and three excluded points, #ETH rules out computing Z(G; q, w) on simple graphs in time exp(o(m/log^3 m)).The excluded points (4, −2), (2, −1), and (2, −2) correspond to polynomial-time points (−1, −1), (−1, 0), and (0, −1) in the Tutte plane.Source: Points on the Hyperbolas · p. 21
  • Theta inflations provide distinct weight shifts for interpolation, yielding simple graphs with at most O(m log^3 m) edges and transferring coefficient-counting hardness to evaluation.The method recovers coefficients of v → Z(G; q, v) from m+1 shifted evaluations; degenerate cases are transformed before applying the interpolation construction.Source: Points on the Hyperbolas · pp. 21–22

Reliability line

  • The reliability line x = 1 is not covered by the preceding result because q = 0; there the Tutte polynomial specializes to the reliability polynomial, and p = 1 is easy to evaluate.For connected G, R(G; p) is the probability that G stays connected when each edge independently fails with probability p; R(G; 1) = 0.Source: Wump Graphs · p. 22
  • Wump inflations yield a rich enough set of distinct reliability-line weight shifts for interpolation when w lies in (−1, 0) or (9, ∞), using sequences computable in polynomial time.The section defines Wump graphs by concatenating humps formed from multiple paths; their associated sequences determine shifted-weight ordering.Source: Wump Graphs · pp. 24–25

Points on the Reliability Line

  • Under #ETH, Z0(G; 0, w) for a given simple graph cannot be computed in time exp(o(m/log^2 m)) for any nonzero rational w.Here m is the number of edges.Source: Points on the Reliability Line · p. 27
  • Weight shifts for either sign of w use graph transformations that preserve simplicity and increase the edge count by at most a constant factor 2k.For w < 0 the shift uses a k-stretch; for w > 0 it uses a 2-stretch of a k-thickening.Source: Points on the Reliability Line · p. 27
  • Using m + 1 distinct Wump-graph weight shifts, interpolation recovers the degree-m polynomial’s coefficients from graphs with at most O(m log^2 m) edges.By Proposition 4.3, those coefficients cannot be computed in time exp(o(m)) under #ETH, yielding the claimed exp(o(m/log^2 m)) lower bound.Source: Points on the Reliability Line · p. 27

7. Conclusion and Further Work

The results leave the Tutte polynomial’s hardness unresolved along the line y = 1, except at (1, 1). They also leave open whether computing forest-polynomial coefficients requires exponential time under #ETH.

7. Conclusion and Further Work

  • The Tutte polynomial results leave the line y = 1 open except at (1, 1), even for multigraphs.The paper also notes that its conditional lower bounds exp(Ω(n/polylog n)) do not match the corresponding exp(O(n)) upper bounds.Source: §7 · p. 28
  • At every point on the open line, hardness is shown to be at least that of computing the coefficients of the forest polynomial F(G; w).For multigraphs the reduction does not increase the number of vertices; for simple graphs it increases the number of edges by O(log^2 m).Source: §7 · p. 28
  • Whether computing the coefficients of F(G; w) requires exponential time under #ETH remains unknown.Source: §7 · p. 28

A. The Sparsification Lemma

The appendix adapts sparsification to counting by making the satisfying assignments of the resulting formulas disjoint, so their counts can be summed. It also uses sparsification to relate variable- and clause-subexponential algorithms for #d-Sat.

A. The Sparsification Lemma

  • Sparsification reduces the density of combinatorial instances while preserving properties such as the answer to a computational problem.Its algorithmic use can preprocess instances, while its complexity-theoretic use identifies sparse instances as the hardest for efficiently sparsifiable NP-hard problems.Source: A. The Sparsification Lemma · p. 33
  • The standard sparsification lemma connects variable and clause counts by producing bounded-occurrence formulas, as used in the ETH setting.The appendix frames this as replacing the variable parameter n with the clause parameter m.Source: A. The Sparsification Lemma · p. 33
  • The counting adaptation makes each satisfying assignment belong to exactly one sparsified formula, yielding #Sat(γ) = Σ_i #Sat(γ_i).The modified branching makes the assignment sets disjoint; the construction adds at most n unit clauses and does not increase the number of formulas.Source: A. The Sparsification Lemma · pp. 33–34
  • For every d ≥ 3, #d-Sat has a variable-subexponential algorithm if and only if it has a clause-subexponential algorithm.Sparsification queries formulas with O(n) clauses and runs in exp(O(n/k)) time, for parameter k.Source: A. The Sparsification Lemma · p. 34
  • A clause-subexponential algorithm for #3-Sat would give one for #d-Sat by a width reduction preserving the number of satisfying assignments.The transformation introduces a constant number of new variables per original clause and produces O(m) clauses.Source: A. The Sparsification Lemma · p. 34

B. Parameterized Complexity

The appendix relates counting ETH to parameterized counting hardness and to a uniform formulation based on sparse 3-CNF instances. It defines FPT through running times of the form f(k) poly(n).

B. Parameterized Complexity

  • Fixed-parameter tractable problems have algorithms running in f(k) poly(n) time for some computable function f.Source: B. Parameterized Complexity · p. 35
  • If #ETH holds, then #W[1] ≠ FPT, ruling out fixed-parameter tractability for the class’s complete counting problems under that assumption.Examples given are counting k-cliques and simple paths of length k.Source: B. Parameterized Complexity · p. 35
  • The appendix presents an equivalence involving a uniform #ETH variant and the absence of deterministic 2^o(n)-time algorithms for counting satisfying assignments of sparse 3-CNF formulas.The stated problem uses formulas with at most k log n clauses.Source: B. Parameterized Complexity · p. 35

C. Hardness of 3-Colouring and 3-Terminal MinCut

The section establishes clause-subexponential hardness under #ETH for counting not-all-equal assignments, maximum cuts, three-terminal minimum cuts, and proper 3-colourings. Its reductions keep instance sizes linear in the source clause count, though not all reductions are parsimonious.

C. Hardness of 3-Colouring and 3-Terminal MinCut

  • #NAE-3-Sat, #MaxCut, #3-Terminal MinCut, and #3-Colouring cannot be computed in exp(o(m)) time unless #ETH fails.The reductions from #3-Sat have linear-size clause or edge growth, allowing a subexponential algorithm for any target problem to imply one for #3-Sat.Source: C. Hardness of 3-Colouring and… · p. 35, Three-colouring · p. 39
  • The reductions are oracle reductions making at most one query, and need not preserve solution counts exactly.For example, every graph has at least one maximum cut, whereas a formula may be unsatisfiable.Source: C. Hardness of 3-Colouring and… · p. 36
  • #3-Sat reduces to promised #NAE-3-Sat+ with O(m) clauses, and the construction gives #NAE-3-Sat(ϕ′′) = 2 · (#Sat(ψ) + 1).The promise is met by planting a satisfying assignment before converting clauses to not-all-equal form.Source: Not-all-equal-Sat · p. 36
  • A graph with O(m) edges encodes #NAE-3-Sat+ as maximum cuts of size 2m+n, one for each not-all-equal assignment.The construction uses variable-literal edges and a triangle for each constraint; the maximum-cut correspondence is parsimonious.Source: Maximum Cut · p. 37
  • #MaxCut reduces to #3-Terminal MinCut with O(m) edges, preserving the number of solutions in the described construction.Each source edge contributes an 18-edge gadget, and minimum three-terminal cuts of the resulting graph correspond to maximum cuts.Source: Minimum cut between three terminals · p. 38
  • #NAE-3-Sat reduces to #3-Colouring with O(m) edges, producing 3 · 2^m colourings per not-all-equal assignment.The graph has 1 + 2n + 3m vertices and 3n + 6m edges.Source: Three-colouring · pp. 38–39

C.1. Hardness of Colouring and Other Individual Points on the Chromatic Line

The section establishes #ETH-based lower bounds for evaluations on the chromatic line by relating the Tutte polynomial to chromatic-polynomial evaluations. It also identifies exceptional points and a separate hardness bound for simple graphs.

C.1. Hardness of Colouring and Other Individual Points on the Chromatic Line

  • The chromatic polynomial χ(G; q) counts proper vertex colourings for natural-number q, and the Tutte polynomial specializes to it when y = 0.Source: §C.1 · p. 39
  • For q ≥ 4, #ETH rules out exp(o(m)) computation of χ(q), and the reduction transfers this bound to Tutte(x, 0) when q = 1 − x.Linial’s identity obtains χ(3) from χ(G + K_i; q), with the enlarged graph having O(m(G)) edges.Source: §C.1 · p. 39
  • For x ∉ Q \ {1, 0, −1, −2, −3, . . .}, #ETH rules out exp(o(n)) computation of Tutte(x, 0), even for simple graphs.The proof interpolates χ(G; r) from n + 1 evaluations obtained through χ(q − i); the query graphs can have quadratically many edges but at most 2n vertices.Source: §C.1 · p. 40
  • The x-axis points not covered are x ∈ {1, 0, −1}; two admit polynomial-time algorithms, while Tutte(1, 0) cannot be evaluated in exp(o(m / log^2 m)) time under #ETH.Source: §C.1 · p. 40
Loading 1206.1775v1…