The Complexity of Counting in Sparse, Regular, and Planar Graphs
| Title: | The Complexity of Counting in Sparse, Regular, and Planar Graphs |
| Author: | Vadhan, Salil |
| Citation: | Vadhan, Salil P. 2001. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing 31(2): 398-427. |
| Access Status: | At the direction of the depositing author this work is not currently accessible through DASH. |
| Full Text & Related Files: |
Vadhan_CountSparseGraphs.pdf (412.0Kb; PDF) 
|
| 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. |
| Published Version: | http://dx.doi.org/10.1137/S0097539797321602 |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:2961235 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5137]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
