Title :
On counting independent sets in sparse graphs
Author :
Dyer, Martin ; Frieze, Alan ; Jerrum, Mark
Author_Institution :
Sch. of Comput. Studies, Leeds Univ., UK
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;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814593
