Many graph-theoretic counting problems remain intractable (indeed #P-complete) despite additional constraints on their structural properties, like planarity, bipartiteness, and low degree, even though their decision counterparts might be easy. This talk explores Salil Vadhan’s framework for proving #P-completeness of problems like #Matchings, #VertexCovers, and #Monotone2CNF even on planar, low-degree, and regular graphs. A new interpolation based reduction technique that uses Fibonacci-style gadgets to preserve structure like constant degree, during reductions is used to prove these results. Based on: The Complexity of Counting in Sparse, Regular, and Planar Graphs, Salil P. Vadhan (https://doi.org/10.1137/S0097539797321602).
