FPTAS for #BIS with Degree Bounds on One Side
summary
Presents a fully polynomial-time approximation scheme (FPTAS) for counting independent sets (#BIS) in bipartite graphs where one side has a maximum degree bound; uses algorithmic techniques tailored to that degree constraint to approximate the partition function/count of independent sets.
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:32Outline
- 1:10Counting Problems
- 3:06Approximate Counting
- 4:23Counting vs Distribution
- 9:03Computation Tree
- 9:39An example of independent sets
- 15:28Computational Efficient Correlation Decay
- 16:16Proof Sketch for Correlation Decay
- 21:35Some examples
- 26:58Counting Independent Sets (#IS)
- 28:55Correlation decay for #15
- 30:05Correlation decay for #IS (cont.)
- 33:00#BIS
- 36:15Some approximation trichotomies
- 37:12Our new algorithm
- 39:00Two-layer recursion
- 39:48Choice of the Potential Function
- 43:00Adaptive Truncation
- 43:49Analogy with MCMC