TL;DR
This paper closes a gap in our understanding of computational complexity by proving that counting acyclic subgraphs (forests) of a graph is as hard as possible under the strong exponential time hypothesis (#ETH). This result, along with a similar hardness proof for counting independent sets in bipartite graphs, completes a fine-grained complexity dichotomy for evaluating the Tutte polynomial and for Boolean constraint satisfaction problems.
What Problem Does This Paper Address?
The paper tackles the question of how computationally hard it is to count certain combinatorial objects, specifically focusing on evaluating the Tutte polynomial and solving Boolean constraint satisfaction problems (#CSP). While it's known that many of these problems are "hard" (belonging to the complexity class #P), a more precise understanding of their difficulty, especially in terms of exponential time, is sought.
Previously, researchers established that evaluating the Tutte polynomial at most points is #P-hard, and under the strong exponential time hypothesis (#ETH), these problems are hard to solve even in subexponential time (specifically, $2^{o(n)}$). However, a specific case for the Tutte polynomial, along the line $y=1$, remained open. Similarly, for Boolean #CSPs, it was known that if they are #P-hard, they are also hard under #ETH, but the proof relied on reductions that didn't quite match the tightest possible exponential time bounds. This paper aims to close these gaps by proving the tightest possible exponential time hardness for these problems.
Methods
The core technical contribution of this paper lies in extending the "block interpolation" technique, introduced by Radu Curticapean, to prove new hardness results.
- Block Interpolation: This technique is a powerful tool for transferring hardness results from one problem to another, particularly in the context of exponential time complexity. It allows researchers to reduce the problem of computing all coefficients of a polynomial to the problem of evaluating it at specific points, even for multigraphs.
- Forest Counting Hardness: To prove the hardness of counting forests (acyclic subgraphs) under #ETH, the authors first establish a reduction from counting perfect matchings (a known #ETH-hard problem) to evaluating the Tutte polynomial along the $y=1$ line. This involves constructing a specific graph transformation and leveraging the properties of the multivariate forest polynomial.
- Independent Sets in Bipartite Graphs Hardness: A crucial step for the #CSP results is proving that counting independent sets in bipartite graphs is hard under #ETH, even for sparse graphs. This is achieved by reducing from a known #ETH-hard problem (counting independent sets in general graphs of bounded degree) to this specific bipartite case. This reduction involves a clever system of linear equations derived from graph properties.
- Transferring Hardness: Once these core hardness results are established, the paper shows how existing reductions for #CSPs can be used without modification to achieve the desired fine-grained #ETH dichotomy for Boolean #CSPs.
Datasets
Not discussed in the paper. The paper deals with theoretical complexity and algorithmic hardness proofs, not empirical evaluation on datasets.
Key Insights and Ideas
- Completing the Tutte Polynomial Dichotomy: The paper successfully closes the final gap in the complexity landscape of the Tutte polynomial under #ETH by proving that counting forests is indeed hard, matching the hardness of other points on the "Tutte plane." This means that for most points $(x, y)$, evaluating the Tutte polynomial $T(G; x, y)$ is computationally intractable in subexponential time unless #ETH fails.
- Tight Hardness for Boolean #CSPs: The paper establishes that all #P-hard Boolean #CSPs are also hard under #ETH, meaning they cannot be solved in $2^{o(n)}$ time unless #ETH fails. This is a significant refinement of previous results.
- The Power of Block Interpolation: The successful application of block interpolation to prove these new hardness results highlights its versatility and effectiveness as a tool for fine-grained complexity analysis.
- Bipartite Graph Hardness is Key: The proof that counting independent sets in bipartite graphs is #ETH-hard is a critical intermediate step. This result is surprising because bipartite graphs are often considered "simpler" than general graphs, yet counting independent sets on them is still fundamentally hard in the exponential time regime.
Key Results
- Theorem 1: Counting all acyclic subgraphs (forests) of a simple $n$-vertex graph with at most $C \cdot n$ edges cannot be computed in time $2^{o(n)}$ unless #ETH fails. This completes the #ETH dichotomy for the Tutte polynomial.
- Corollary 2: A complete #ETH dichotomy for the Tutte polynomial over the real plane is formally stated. For most points $(x, y)$, evaluating $T(G; x, y)$ is #P-hard and cannot be computed in $2^{o(n)}$ time unless #ETH fails.
- Theorem 3: Counting independent sets in bipartite $n$-vertex graphs of maximum degree at most $D$ cannot be computed in time $2^{o(n)}$ unless #ETH fails.
- Corollary 4: All #P-hard Boolean #CSPs are also hard under #ETH, meaning they cannot be computed in time $2^{o(n)}$ unless #ETH fails.
Limitations and Future Work
- Real vs. Rational Numbers: The paper notes that results are stated for rational numbers to avoid complexities in representing real numbers. Extending these results to arbitrary real numbers might require further investigation.
- Generalizations: The authors mention that their work is a step towards understanding more challenging dichotomies, such as those for CSPs with complex weights or Holant problems with symmetric signatures. This suggests future work in these directions.
- Sparse Graphs: While the hardness results hold even for sparse graphs, the exact trade-offs between sparsity and hardness might be an area for further exploration.
- Approximation Complexity: The paper focuses on exact counting. The complexity of approximating these counts, especially for independent sets in bipartite graphs, remains an open and active area of research.
Summary updated