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 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~((|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 F_n of complement of G_n~R.