The Complexity of Counting in Sparse, Regular, and Planar Graphs
Salil P. Vadhan
Abstract
We show that a number of graph-theoretic counting problems remain NP-hard,
indeed #P-complete, in very restricted classes of graphs. In particular,
we prove that the problems of counting matchings, vertex covers, independent
sets, and extremal variants of these all remain hard when restricted to
planar bipartite graphs of bounded degree or regular graphs of constant
degree. We obtain corollaries about counting cliques in restricted classes
of graphs and counting satisfying assignments to restricted classes of
monotone 2-CNF formulae. To achieve these results, a new interpolation-based
reduction technique which preserves properties such as constant degree
is introduced.
Versions
[
back to Salil Vadhan's research interests ]