Counting the Maximal Independent Sets in Power Set Graphs

Counting the number of maximal independent sets is \#P-complete even for chordal graphs. We prove that the number of maximal independent sets in a subclass \(\mathcal{G}_n^R\) (Right power set graphs) of chordal graphs can be computed in polynomial time using Golomb’s nonlinear recurrence relation. We provide a recursive construction of \(\mathcal{G}_n^R\) and prove that there are \(2^\frac{|V(\mathcal{G}_n^R)|+1}{4}\) maximum independent sets in \(\mathcal{G}_n^R\). We also provide a polynomial-time algorithm to solve the maximum independent set problem (MISP) in a superclass \(\mathcal{F}_n\) of the complement of \(\mathcal{G}_n^R\).