Найти все независимые множества идеального графа

Question

Я читал, что максимальное независимое множество идеального графа может быть найдено за полиномиальное время.

Существует ли алгоритм полиномиального времени, который может найти список всех независимых множеств идеального графа?

Answer 1

Это правда, что максимальное независимое множество можно найти за полиномиальное время в совершенных графах ( классах графов). Что касается списка всех независимых множеств для идеального графа с n узлами: количество всех независимых множеств представляется мне экспоненциальным. Но перечислить все максимальные независимые наборы программного обеспечения доступно благодаря Wikipedia.

Answer 2

Классическая конструкция Муна и Мозера (1965) показывает пример идеального графа, который имеет экспоненциальное число максимальных (и максимальных) независимых множеств.

Чтобы построить такой граф, возьмите $n$ непересекающихся копий $K_3$ (треугольников). Максимальный/максимальный независимый набор выбирается путем выбора по 1 вершине из каждого треугольника. Таким образом, этот граф с $3n$ вершинами имеет $3^{n}$ различных максимальных (и максимальных) независимых множеств, что делает невозможным их перечисление за полиномиальное время.