The Complexity of Counting in Sparse, Regular, and Planar Graphs

DSpace/Manakin Repository

The Complexity of Counting in Sparse, Regular, and Planar Graphs

Citable link to this page

. . . . . .

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:
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

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7175]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters