Counting the Maximal Independent Sets in Power Set Graphs

Abstract

Counting the number of maximal independent sets is $\mathrm{\#}P$-complete even for chordal graphs. We prove that the number of maximal independent sets in a subclass $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 $G_n^R$ and prove that there are $2^{\frac{|V(G_n^R)|+1}{4}}$ maximum independent sets in $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 $G_n^R$.