Finding all independent sets of a perfect graph

Question

I read that a maximum independent set on a perfect graph can be found in polynomial time.

Is there any polynomial time algorithm that can find the list of all independent sets of a perfect graph?

Answer 1

It is true that the maximum independent set can be found in polynomial time in perfect graphs (graph classes). As for the list all independent sets for a perfect graph with n nodes: The number of all independent sets seems to me to be exponential. But to list all maximal independent sets software is available due to Wikipedia.

Answer 2

The classic construction of Moon and Moser (1965) shows an example of a perfect graph which has an exponential number of maximal (and maximum) independent sets.

To construct such a graph, take $n$ disjoint copies of $K_3$ (triangles). A maximal/maximum independent set is selected by choosing 1 vertex from each triangle. So this graph on $3n$ vertices has $3^{n}$ different maximal (and maximum) independent sets, making it impossible to list them all out in polynomial time.