CODEWITHSUNDEEP
graphcliqueindependent-set
user2858924
user2858924

Reputation: 433

Finding all independent sets of a perfect graph

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?

Upvotes: 0

Views: 456

Answers (2)

JimN
JimN

Reputation: 427

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.

Upvotes: 0

gue
gue

Reputation: 2028

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.

Upvotes: 0

Related Questions