The Complexity of Counting in Sparse, Regular, and Planar Graphs
Access StatusFull text of the requested work is not available in DASH at this time ("dark deposit"). For more information on dark deposits, see our FAQ.
MetadataShow full item record
CitationVadhan, Salil P. 2001. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing 31(2): 398-427.
AbstractWe 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:2961235
- FAS Scholarly Articles