The complexity of counting in sparse, regular, and planar graphs

Authors
Citation
Sp. Vadhan, The complexity of counting in sparse, regular, and planar graphs, SIAM J COMP, 31(2), 2001, pp. 398-427
Citations number
52
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
398 - 427
Database
ISI
SICI code
0097-5397(20011011)31:2<398:TCOCIS>2.0.ZU;2-T
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 pla nar bipartite graphs of bounded degree or regular graphs of constant degree . We obtain corollaries about counting cliques in restricted classes of gra phs and counting satisfying assignments to restricted classes of monotone 2 -CNF formulae. To achieve these results, a new interpolation-based reductio n technique which preserves properties such a constant degree is introduced .