DocumentCode
3450109
Title
On counting independent sets in sparse graphs
Author
Dyer, Martin ; Frieze, Alan ; Jerrum, Mark
Author_Institution
Sch. of Comput. Studies, Leeds Univ., UK
fYear
1999
fDate
1999
Firstpage
210
Lastpage
217
Abstract
We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree Δ. The first result implies that the Monte-Carlo Markov chain technique is likely to fail if Δ⩾6. The second shows that no fully polynomial randomized approximation scheme can exist for Δ⩾25, unless P=NP under randomized reductions
Keywords
Markov processes; Monte Carlo methods; approximation theory; computational complexity; graph theory; randomised algorithms; set theory; Monte-Carlo Markov chain technique; approximate counting; constant maximum degree; independent set counting; polynomial randomized approximation scheme; randomized reductions; sparse graphs; Bipartite graph; Computer science; Electronic switching systems; Mathematics; Monte Carlo methods; Polynomials; Radio access networks;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location
New York City, NY
ISSN
0272-5428
Print_ISBN
0-7695-0409-4
Type
conf
DOI
10.1109/SFFCS.1999.814593
Filename
814593
Link To Document