Editing Independent set (graph theory) (section)

=== Counting independent sets ===

{{unsolved|computer science|Is there a fully polynomial-time approximation algorithm for the number of independent sets in bipartite graphs?}}

The [[counting problem (complexity)|counting problem]] #IS asks, given an undirected graph, how many independent sets it contains. This problem is intractable, namely, it is [[♯P]]-complete, already on graphs with maximal [[degree (graph theory)|degree]] three.<ref>{{Cite journal |last1=Dyer |first1=Martin |last2=Greenhill |first2=Catherine |date=2000-04-01 |title=On Markov Chains for Independent Sets |url=https://www.sciencedirect.com/science/article/pii/S0196677499910714 |journal=Journal of Algorithms |volume=35 |issue=1 |pages=17–49 |doi=10.1006/jagm.1999.1071 |issn=0196-6774}}</ref> It is further known that, assuming that [[NP (complexity)|NP]] is different from [[RP (complexity)|RP]], the problem cannot be tractably [[Approximation algorithm|approximated]] in the sense that it does not have a fully [[polynomial-time approximation scheme]] with randomization (FPRAS), even on graphs with maximal degree six;<ref>{{Cite book |last=Sly |first=Allan |chapter=Computational Transition at the Uniqueness Threshold |date=2010 |title=2010 IEEE 51st Annual Symposium on Foundations of Computer Science |chapter-url=https://ieeexplore.ieee.org/document/5671190 |pages=287–296 |doi=10.1109/FOCS.2010.34|isbn=978-1-4244-8525-3 |s2cid=901126 }}</ref> however it does have an fully polynomial-time approximation scheme (FPTAS) in the case where the maximal degree is five.<ref>{{Cite journal |last1=Bezáková |first1=Ivona |last2=Galanis |first2=Andreas |last3=Goldberg |first3=Leslie Ann |last4=Guo |first4=Heng |last5=Štefankovič |first5=Daniel |date=2019 |title=Approximation via Correlation Decay When Strong Spatial Mixing Fails |url=https://epubs.siam.org/doi/10.1137/16M1083906 |journal=SIAM Journal on Computing |language=en |volume=48 |issue=2 |pages=279–349 |doi=10.1137/16M1083906 |s2cid=131975798 |issn=0097-5397|arxiv=1510.09193 }}</ref> The problem #BIS, of counting independent sets on [[bipartite graph]]s, is also [[♯P]]-complete, already on graphs with maximal [[degree (graph theory)|degree]] three.<ref>{{Cite journal |last1=Xia |first1=Mingji |last2=Zhang |first2=Peng |last3=Zhao |first3=Wenbo |date=2007-09-24 |title=Computational complexity of counting problems on 3-regular planar graphs |url=https://www.sciencedirect.com/science/article/pii/S0304397507004653 |journal=Theoretical Computer Science |series=Theory and Applications of Models of Computation |volume=384 |issue=1 |pages=111–125 |doi=10.1016/j.tcs.2007.05.023 |issn=0304-3975}}, quoted in {{Cite journal |last1=Curticapean |first1=Radu |last2=Dell |first2=Holger |last3=Fomin |first3=Fedor |last4=Goldberg |first4=Leslie Ann |last5=Lapinskas |first5=John |date=2019-10-01 |title=A Fixed-Parameter Perspective on #BIS |journal=Algorithmica |language=en |volume=81 |issue=10 |pages=3844–3864 |doi=10.1007/s00453-019-00606-4 |s2cid=3626662 |issn=1432-0541|doi-access=free |hdl=1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af |hdl-access=free }}</ref>
It is not known whether #BIS admits a FPRAS.<ref>{{Cite book |url=https://epubs.siam.org/doi/book/10.1137/1.9781611975994 |title=Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms |date=2020 |publisher=Society for Industrial and Applied Mathematics |isbn=978-1-61197-599-4 |editor-last=Chawla |editor-first=Shuchi |location=Philadelphia, PA |language=en |doi=10.1137/1.9781611975994.88|arxiv=1906.01666 |s2cid=174799567 |last1=Cannon |first1=Sarah |last2=Perkins |first2=Will }}</ref>

The question of [[counting maximal independent sets]] has also been studied.