Abstrakt. Vi anser att #P-komplett problemet med att räkna antalet oberoende uppsättningar i en given graf. Vårt intresse är att förstå effektiviteten i den populära trosförökning (BP) heuristiska. BP är en enkel iterativ algoritm som är känd för att ha minst en fast punkt, där varje fast punkt motsvarar en stationär punkt av Bethe fri energi (inledd av Jedidia, Freeman, och Weiss [IEEE Trans. Informera. Teori, 51 (2004), s. 2282-2312 som ett erkännande av Betes tidigare arbete 1935). Utvärderingen av Bethe fri energi vid en sådan stationär punkt (eller BP fast punkt) leder till Bethe approximation för antalet oberoende uppsättningar av den givna grafen. BP är inte känt för att konvergera i allmänhet, inte heller är en effektiv, konvergent förfarande för att hitta stationära punkter av Bethe fri energi känd. Dessutom är effektiviteten i Bethe approximationen inte väl förstådd. Som det första resultatet av detta dokument föreslår vi en BP-liknande algoritm som alltid konvergerar till en stationär punkt av Bethe fri energi för någon graf för den oberoende uppsättning problem. Detta förfarande finner en ε-ungefärlig stationär punkt i Oðn 2 d 4 2 d ε −4 log 3 ðnε −1  ska iterationer för en graf av n noder med max-grad d. Vi studerar kvaliteten på den resulterande Bethe approximation med hjälp av den nyligen utvecklade "loop-serien" ram Chertkov och Chernyak [J. Stat. - Mech. - Vad är det? Teorin Exp., 6 (2006), P06009]. Eftersom denna karakterisering endast gäller för exakta stationära punkter av Bethe fri energi, ger vi en något modifierad karakterisering som håller för ε-ungefärliga stationära punkter. Vi fastställer att för alla grafer på n noder med max-grad d och omkrets större än 8d log 2 n, det multiplikativa felet mellan antalet oberoende uppsättningar och Bethe approximationen sönderfaller som 1 ̊ Oðn −γ  på vissa γ > 0. Detta ger en deterministisk beräkningsalgoritm som leder till helt olika resultat jämfört med ett nyligen resultat av Weitz [i Proceedings of the 30-Eighth Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2006, s. - 140-149. - Vad är det? - 140-149. Slutligen, som en följd av vår analys visar vi att Bethe approximationen är oerhört bra för en slumpmässig 3-regelbunden graf betingad på den kortaste cykeln täcker gissningar av Alon och Tarsi [SIAM J. Algebr. Diskreta metoder, 6 (1985), s. 335-350] är sant.
I REF användes slingan för att bevisa att Bethe approximationen ger en god uppskattning av antalet oberoende uppsättningar på grafer med liten maximal och stor omkrets.
Counting independent sets using the Bethe approximation
{'venue': 'SIAM J. Discr. Math', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}