Максимальные классы, для которых наибольшее независимое множество можно найти за полиномиальное время?

В ISGCI списки более 1100 классов графов. Для многих из них мы знаем, можно ли выбрать НЕЗАВИСИМЫЙ НАБОР за полиномиальное время; их иногда называют классами IS-easy . Я хотел бы составить список максимальных классов IS-easy. Эти классы вместе образуют границу (известной) управляемости для этой задачи.

Так как к любому бесконечному классу IS-easy можно просто добавить конечное число графов, не влияя на его управляемость, существуют некоторые ограничения. Давайте ограничим классы наследственными (закрытыми при взятии индуцированных подграфов или, что то же самое, определенными набором исключенных индуцированных подграфов). Кроме того, давайте рассмотрим только те семейства, которые не содержат X для множества X с небольшим описанием. Там , возможно , являются также быть бесконечными восходящие цепочки послушными классов (например, -бесплатно и классы описаны Дэвидом Eppstein ниже), но давайте ограничимся классами, на самом деле доказано, что это легко.$(P,\text{star}_{1,2,k})$

Вот те, о которых я знаю:

• идеальные графики
• $(P,\text{star}_{1,2,5})$ бесплатно
• $(K_{3,3}-e, P_5)$ бесплатно
• совместно Meyniel
• почти двудольный
• Кресло-бесплатно
• ( , крикет) - бесплатно$P_5$
• $(P_5,K_{n,n})$ бесплатно (для любого фиксированного )$n$
• $(P_5, X_{82}, X_{83})$ бесплатно

Известны ли другие такие максимальные классы?

Изменить: См. Также связанный вопрос, заданный Ярославом Булатовым, касающийся классов, определенных исключенными несовершеннолетними, что легко для второстепенных исключенных графов? а увидеть глобальные свойства наследственных классов? для более общего вопроса я задавал ранее о наследственных классах.

Как отмечает в комментариях Юкка Суомела, случай с исключенным несовершеннолетним также интересен (и ставит интересный вопрос), но здесь это не главное.

Чтобы избежать примера Дэвида, максимальный класс также должен быть определен как графы без X, где не каждый граф в X имеет независимую вершину.

Занятия даны в ответах ниже:

• без яблок (по предложению Standa Živný)
• ( , house) -бесплатно$P_5$ (предложено Дэвидом Эппштейном)
• ( когтя) - бесплатно$K_2 \cup$ (предложено Дэвидом Эппштейном)

Добавлено 2013-10-09: недавний результат Локштанова, Ватшелла и Виллангера, упомянутый Мартином Ватшелле в ответе, заменяет некоторые из ранее известных максимальных классов.

В частности, будучи IS-easy, включает в себя ( , крикет) -free, ( , ) -free, ( , , ) -free и ( , хаус) -свободно быть просто.$P_5$$P_5$$P_5$$K_{n,n}$$P_5$$X_{82}$$X_{83}$$P_5$

Это означает, что все классы наследственных графов, определяемые одним запрещенным индуцированным подграфом, содержащим до пяти вершин, теперь могут быть окончательно классифицированы как IS-easy или не IS-easy.

К сожалению, доказательство того, что графы образуют простой в IS класс, похоже, не работает для графов, поэтому следующей границей является классификация всех классов наследственных графов, определенных одним графом из шести вершин.$P_5$$P_6$

Я по- прежнему особенно заинтересован в IS-простых классах вида -свободного для некоторого набора графов с бесконечным числом классов изоморфизма, но где -бесплатно не IS-легко для любого .$X$$X$$Y$$Y \subset X$

Вопрос уже немного старше, но ISGCI может помочь здесь.

Когда вы запускаете приложение ISGCI Java и заходите в меню Проблемы -> Границы / Открыть классы -> Независимый набор, вы получаете диалог с 3 списками.

Список Maximal P содержит все классы C (в ISGCI), для которых IS может быть решена за полиномиальное время, так что существует минимальный суперкласс C, для которого IS, как известно, не находится в P (т. Е. NP-полная, открытая или неизвестно ISGCI). Выбор класса и нажатие «Draw» нарисуют класс и суперклассы, найденные путем перехода в BFS-стиле вверх по иерархии включения настолько, насколько это необходимо для поиска класса, в котором IS, как известно, не находится в P.

Список Minimal NP-complete завершается наоборот: он содержит классы, для которых IS является NP-complete, так что не все максимальные подклассы также NP-complete. Рисование идет вниз по иерархии, пока не будет найден не-NP-полный класс.

Открытый список содержит классы, для которых проблема либо открыта, либо неизвестна. Рисование проходит по супер / подклассам, пока не будет достигнут класс, который не открыт.

При создании чертежа рекомендуется установить раскраску для задачи «Независимый набор» («Задачи» - «Цвет задачи» -> «Независимый набор»).

Что касается вопроса Standa Zivny, в ISGCI перечислены следующие 20 классов с известной сложностью для невзвешенной проблемы IS, но с неизвестной сложностью для взвешенного случая (ISGCI не может различить «простые» и «сложные» полиномиальные алгоритмы):

gc_11 расширенный P ₄ -нагрузочный
gc_128 EPT
gc_415 хорошо покрытый
gc_428 (K _3,3 -e, P ₅ , X ₉₈ )
-свободный gc_648 (K _3,3 -e, P ₅ )
-свободный gc_752 со-наследственный клика-Helly
gc_756 (E, P) -
свободный gc_757 (P, T ₂ ) -
свободный gc_758 (P, P ₈ ) -
свободный gc_759 (K _3,3 -e, P ₅ , X ₉₉ ) -
свободный gc_808 (C ₆ , K _{3, 3} + e, P, P ₇ , X ₃₇ , X ₄₁ ) без
gc_811 (P, звезда_1,2,5 )
-свободный gc_812 (P ₅ , P ₂ ∪ P ₃ )
-свободный gc_813 (P, P ₇ )
-свободный gc_818 (P, звезда _1,2,3 )
-бесплатный gc_819 (P, звезда _{1, 2,4} ) -
свободный gc_841 (2К ₃ + е, А, С ₆ , Е, К _3,3-е , Р ₆ , R, Х ₁₆₆ , Х ₁₆₇ , Х ₁₆₉ , Х ₁₇₀ , Х ₁₇₁ , Х ₁₇₂ , Х ₁₈ , Х ₄₅ , Х ₅ , Х ₅₈ , Х ₈₄ , Х ₉₅ , Х₉₈ , А, С ₆ , Е, Р ₆ , Р, Х ₁₆₆ , Х ₁₆₇ , Х ₁₆₉ , Х ₁₇₀ , Х ₁₇₁ , Х ₁₇₂ , Х ₁₈ , Х ₄₅ , Х ₅ , Х ₅₈ , Х ₈₄ , Х ₉₅ , X ₉₈ , антенна, совместная антенна, совместное домино, совместная рыбка, совместный дом-близнец, домино, рыба, дом-близнец) - бесплатно
gc_894 совместное круговое совершенство
gc_895 сильно круговое совершенное
(3K ₂ , E, P ₂₎ ∪ P ₄ , нетто) -бесплатно

Несомненно, некоторые из них будут иметь известные алгоритмы и для взвешенного случая. Дополнения и исправления всегда приветствуются по адресу, указанному на веб-странице ISGCI!

Интересная статья, на которую можно посмотреть:

А. Брандштадт, В. В. Лозин, Р. Моска: Независимые множества максимального веса в графах без яблок, Журнал SIAM по дискретной математике 24 (1) (2010) 239–254. DOI: 10,1137 / 090750822

Бесконечный класс яблок определяется как циклы C_k, k> = 5, каждый со стеблем.

Вы не упоминаете, включает ли ваше понятие легкости IS проблему взвешенного IS. Графики без стульев (так называемые графы без вилок), как известно, IS-easy:

В.Е. Алексеев, Полиномиальный алгоритм нахождения наибольших независимых множеств в графах без вилок, Дискретная прикладная математика 135 (1-3) (2004) 3–16. DOI: 10.1016 / S0166-218X (02) 00290-1

Отслеживаемость взвешенного случая является нетривиальным расширением, см .:

В.В. Лозин, М. Миланик: Полиномиальный алгоритм для нахождения независимого набора максимального веса в графе без вилок, Журнал дискретных алгоритмов 6 (4) (2008) 595–604. DOI: 10.1016 / j.jda.2008.04.001

Существуют ли другие (интересные) классы, в которых взвешенная проблема IS значительно сложнее / труднее решить / открыть, чем невзвешенный случай?

По словам Василиса Джакумакиса и Ирены Русу, диск. Appl. Математика В 1997 г. (P5, хаус-свободные графы (aka (P5, coP5) -не графы) IS-легки.

Другой, приписываемый ISGCI В. Лозину, Р. Моска Диск. Appl. Математика 2005 , семейство (K2 u коготь) -без графов .

Могут также быть бесконечные восходящие цепочки обучаемых классов

Есть определенно бесконечные восходящие цепи. Если H - конечный набор графов, для которых H-свободные графы IS-легки, пусть H '- графы, образованные добавлением независимой вершины к каждому графу в H. Тогда H-свободные графы также IS-easy: просто примените H-free алгоритм к множествам, не являющимся соседями каждой вершины. Например, как описывает ISGCI, графы без ко-самоцветов IS-легки по той причине, что ко-самоцвет - это P4 плюс независимая вершина, а графы без P4 - IS-легко. Таким образом, вы, вероятно, хотите ограничить свой вопрос максимальными классами, в которых не все запрещенные подграфы имеют независимую вершину.

В документе, принятом в SODA 2014, приведен алгоритм полиномиального времени для независимого набора максимального веса на свободных графиках . http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf$P_5$

Пусть H - граф не более чем на 5 вершинах, тогда сложность Независимого множества известна на классе H-свободных графов.

Проблема сложна, если H содержит цикл или вершину степени 4. Единственными оставшимися случаями связности H являются , коготь и вилка, для этих классов проблема полинома известна, как известно, для несвязного H без циклов есть только несколько возможностей. Если H имеет изолированные вершины, легко увидеть, что IS полиномиален, поскольку он полиномиален для всех H на 4 вершинах без циклов. Дело было рассмотрено в 2005 году. H = P 2 ∪ P $P_5$$H = P_2 \cup P_3$