Полиномиальные задачи в классах графов, заданных запрещенными индуцированными циклическими подграфами

Кросспост из МО .

Пусть - класс графов, определенный конечным числом запрещенных индуцированных подграфов, причем все они циклические (содержат хотя бы один цикл).$C$

Существуют ли NP-сложные графовые задачи, которые можно решить за полиномиальное время для кроме Clique и Clique cover?$C$

Если я правильно помню, это невозможно для независимого набора (если ).$P=NP$

Поиск в graphclasses.org не нашел ни одного.

Класс, для которого покрытие Clique и Clique является полиномиальным, - это C5, C6, X164, X165, sunlet4, без треугольников

редактировать

Отрицательный для IS и Domination находится в этой статье . Страница 2, графики .$S_{i,j,k}$

Я думаю, что есть ряд сложных проблем, которые становятся легкими для графов без треугольников; особенно те, которые имеют дело непосредственно с треугольниками, такими как разбиение на треугольники (есть ли разделение на треугольники?). Другие менее тривиальные примеры включают в себя:

• Проблема стабильного среза (G имеет независимый набор S такой, что GS отключен?). См .: О стабильных наборах в графах, Discrete Applied Math. 105 (2000) 39-50.

• Основа графа пересечений (Является ли G графом пересечений подмножеств множества оснований k-элемента?). См .: Проблема [GT59] в: Garey & Johnson, Компьютеры и Intractability: Руководство по теории NP-полноты.

Вот несколько дополнительных примеров ответа Мон Тэга:

• Задача о разъединенном отрезке ( допускает ли набор вершин S, таких что G - S и подграф G, индуцированный S , разъединены) является NP-полной (см. Здесь ). Легко видеть, что эта задача является полиномиально разрешимой для графов без треугольников (отсюда также проблема Устойчивых сечений, как упомянуто Мон Тэгом).$G$$S$$G-S$$G$$S$

• Распознавание треугольных линейных графов является NP-полным (см. Здесь ). Также легко видеть, что эта задача становится полиномиальной для входных графов без треугольников.

• Вычислить максимальное связанное сопоставление сложно (см. Здесь . Сопоставление связывается, если для любой пары совпадающих ребер имеется другое ребро графа, инцидентное им обоим). Можно доказать, что эта задача полиномиально разрешима для -свободных графов.$(C_3, C_4, C_5)$

Из комментария выше: в Stefan Kratsch, Pascal Schweitzer, Изоморфизм графов для классов графов, характеризуемых двумя запрещенными индуцированными подграфами : GI является полиномиальным по времени (тривиально) разрешимым для графов, но также (менее тривиально) для ( K s , K 1 , t ) -свободных графов.$(K_s,I_t)\text{-free}$$(K_s,K_{1,t})\text{-free}$

РЕДАКТИРОВАТЬ : как отмечено в комментарии, не содержит цикл (я слишком быстро прочитал введение в статью).$K_{1,t}$

Подумав немного об этом, кажется, легко доказать следующее (оригинал?):

Отрицательный результат: для каждого конечного множества , в котором каждый Н я содержит цикл, проблему изоморфизма графов (GI) , ограниченный класс С из ( Н 1 , . . . , Н к ) -свободные графы GI-полный.$\{H_1,...H_k\}$$H_i$$\mathcal{C}$$(H_1,...,H_k)\text{-free}$

Доказательство: Установленный класс графы , в которых каждая Н я содержу цикл, и , учитывая G 1 , G 2 , пусть г есть длина самого длинного цикла H I s. Заменить каждое ребро ( u , v ) в G 1 , G 2 на путь длины l = ⌈ r / 3 $(H_1,...,H_k)\text{-free}$$H_i$$G_1,G_2$$r$$H_i$$(u,v)$$G_1,G_2$$l = \lceil r/3 \rceil$ добавление новых узлов ( у , р 1 , р 2 , . . . , р л , v ) (смотри рисунок ниже). По построению новых графов G ' 1 , G ' 2 являются ( Н 1 , . . . , Н к ) -свободных действительно возможные короткие циклы, образованные в виде треугольника , который должен иметь длину 3 ⌈ г / 3 $l$$(u,p_1,p_2,...,p_l,v)$$G'_1, G'_2$$(H_1,...,H_k)\text{-free}$ ; и легко доказать, что они изоморфны тогда и только тогда, когда исходные G 1 , G 2 изоморфны.$3\lceil r/3 \rceil + 3 > r$$G_1,G_2$

Рисунок : график на левой стороне , и эквивалент ( Н 1 , . . . , Н к ) -бесплатно графа G ' 1 справа (предположим , что самый длинный цикл H я имеет длину г = 15 , так каждое ребро в G 1 заменяется путем длины l = 5 .$G_1$$(H_1,...,H_k)\text{-free}$$G'_1$$H_i$$r=15$$G_1$$l = 5$

Мы также можем распространить отрицательный результат на проблему NPC с гамильтоновым циклом, действительно, это является непосредственным следствием следующего (оригинал?):

$k \geq 3$$G$$\leq k$

$G$$v$$outdeg(v) + indeg(v) \leq 3$$G$$G'$$v$$indeg(v )=1$$v$$indeg(v)=2$$G'$$\geq k$$G''$$G$

$(H_1,...,H_k)\text{-free}$$H_i$

MAX-CUT остается NP-полной.

Лемма 3.2 простой max-cut является NP-полной в следующих двух классах графов:

$k$$k \ge 3$

Они делят ребро дважды.

Из "MAX-CUT и отношения содержания в графах, Марцин Камински"