Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP

Cornelius Brand, Holger Dell, Marc Roth

TL;DR

This paper closes a gap in our understanding of computational complexity by proving that counting acyclic subgraphs (forests) in a graph is as hard as possible under the strong assumption of the counting exponential time hypothesis (#ETH). This result, combined with existing work, provides a complete fine-grained complexity picture for evaluating the Tutte polynomial. It also extends this fine-grained analysis to Boolean constraint satisfaction problems (#CSP), showing that all #P-hard #CSP instances are also hard under #ETH.

What Problem Does This Paper Address?

The paper tackles the problem of precisely characterizing the computational difficulty of certain counting problems. Specifically, it focuses on two main areas:

  1. The Tutte Polynomial: The Tutte polynomial is a powerful mathematical object that encodes many combinatorial properties of graphs. Evaluating this polynomial at specific points can correspond to counting various graph structures (like spanning trees or colorings). Previous work established a dichotomy: for most points, evaluating the Tutte polynomial is #P-hard, while for a few special points, it's efficiently computable in polynomial time. However, a specific line of points (y=1) remained an open problem for achieving the strongest possible hardness guarantees under the counting exponential time hypothesis (#ETH). This paper resolves that open problem by proving that counting forests (acyclic subgraphs) is hard under #ETH, thus completing the fine-grained dichotomy for the Tutte polynomial.
  2. Boolean Constraint Satisfaction Problems (#CSP): This area deals with counting the number of ways to assign values (0 or 1) to variables to satisfy a set of constraints. A known result states that if the constraints are not "affine" (linear equations over GF(2)), the problem is #P-hard. This paper extends this by showing that all such #P-hard #CSP instances are also hard under #ETH, providing a fine-grained complexity classification for these problems as well.

Methods

The authors employ several sophisticated techniques to achieve their results:

  • Block Interpolation: This is a key technique, introduced by Curticapean, that allows for proving tight exponential-time lower bounds. It's a way to "interpolate" polynomial values by cleverly constructing and querying related problems, avoiding the need for exponential numbers of evaluation points or super-linear graph sizes. The paper adapts this technique to new contexts.
  • Reduction Chains: The proofs rely on constructing chains of reductions. This means showing that if you could solve problem A efficiently, you could also solve a known hard problem B efficiently. By starting with a problem known to be hard under #ETH (like counting perfect matchings or independent sets in bipartite graphs) and reducing it to the problem in question, they establish the hardness of the target problem.
  • Multivariate Polynomials and Graph Polynomials: The paper works with various graph polynomials, such as the multivariate forest polynomial and the Tutte polynomial. These polynomials encode combinatorial information, and their evaluation complexity is directly linked to the complexity of counting the underlying structures.
  • Kronecker Powers: For the #CSP part, the authors use Kronecker powers to transfer the block interpolation idea to systems of linear equations that don't directly correspond to interpolation.

Datasets

Not discussed in the paper. The paper deals with theoretical computational complexity and proves hardness results for abstract graph problems, rather than evaluating algorithms on specific datasets.

Key Insights and Ideas

  • Completing the Tutte Polynomial Dichotomy: The most significant insight is finally resolving the hardness of counting forests under #ETH. This means that for almost all points on the Tutte plane, counting the corresponding graph property is fundamentally hard, and no algorithm significantly faster than brute-force exponential time (specifically, faster than $2^{\epsilon n}$ for some $\epsilon > 0$) can exist unless #ETH is false.
  • Bridging #P-hardness and #ETH-hardness: The paper demonstrates how to lift existing #P-hardness results to the more refined #ETH-hardness. This is crucial because #ETH provides a stronger, more precise measure of computational difficulty in the exponential time regime.
  • Independent Sets in Bipartite Graphs as a Core Hardness Source: The paper highlights the central role of counting independent sets in bipartite graphs. This problem is shown to be hard under #ETH, and it serves as a crucial building block for proving the hardness of other problems, including forest counting and certain #CSP instances.
  • Generalizing Fine-Grained Complexity to #CSP: The work extends the concept of fine-grained complexity (analyzing algorithms with exponents in their running times) to the domain of Boolean #CSP. This provides a more nuanced understanding of the difficulty of these problems beyond just their #P-hardness.

Key Results

  • Theorem 1 (Forest Counting Hardness): If #ETH holds, then counting all acyclic subgraphs (forests) in a simple n-vertex graph with at most $O(n)$ edges cannot be computed in time $2^{\epsilon n}$ for any $\epsilon > 0$.
  • Corollary 2 (Tutte Plane Dichotomy): This theorem provides a complete fine-grained dichotomy for the Tutte polynomial over the real numbers. For specific points, it's polynomial-time computable; otherwise, it's #P-hard, and under #ETH, it cannot be computed in time $2^{\epsilon n}$.
  • Theorem 3 (Bipartite Independent Set Hardness): If #ETH holds, counting independent sets in bipartite n-vertex graphs of maximum degree at most $D$ cannot be computed in time $2^{\epsilon n}$ for any $\epsilon > 0$.
  • Corollary 4 (#CSP Dichotomy): For Boolean constraint satisfaction problems, if all constraints are affine, they are solvable in polynomial time. Otherwise, they are #P-hard, and under #ETH, they cannot be computed in time $2^{\epsilon n}$.

Limitations and Future Work

  • Assumptions: The results are conditional on the truth of the Exponential Time Hypothesis (#ETH), which is a widely believed but unproven conjecture.
  • Sparse Graphs: While the results hold for sparse graphs (graphs with a number of edges linear in the number of vertices), the constants in the exponents ($\epsilon$) might depend on the sparsity.
  • Future Directions: The paper explicitly mentions that these results are a "first step towards understanding the fine-grained complexity of technically much more challenging dichotomies," such as those for counting CSPs with complex weights or Holant problems. This suggests that extending these fine-grained analysis techniques to even more complex combinatorial counting problems is a promising avenue for future research.

Summary updated

Abstract

Jaeger, Vertigan, and Welsh (1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén (2010) and Husfeldt and Taslaman (2010), in combination with the results of Curticapean (2015), extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line y=1, which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given n-vertex graph cannot be determined in time exp(o(n)) unless #ETH fails. Another dichotomy theorem we strengthen is the one of Creignou and Hermann (1996) for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases cannot be solved in time exp(o(n)) unless #ETH fails. The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails. In order to prove our results, we use the block interpolation idea by Curticapean (2015) and transfer it to systems of linear equations that might not directly correspond to interpolation.
BibTeX
@article{brand2019fine,
  author = {Cornelius Brand and Holger Dell and Marc Roth},
  title = {{Fine-Grained Dichotomies for the Tutte Plane and Boolean \#CSP}},
  journal = {Algorithmica},
  year = {2019},
  doi = {10.1007/s00453-018-0472-z},
}
Figure