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

Я рассматриваю графовые классы, которые можно охарактеризовать запрещенными подграфами.

Если у класса графов есть конечный набор запрещенных подграфов, то существует тривиальный алгоритм распознавания полиномиального времени (можно просто использовать грубую силу). Но бесконечное семейство запрещенных подграфов не подразумевает твердости: есть некоторые классы с бесконечным списком запрещенных подграфов, такие, что распознавание также может быть проверено за полиномиальное время. Хордовые и совершенные графы являются примерами, но в этих случаях в запрещенном семействе есть «хорошая» структура.

Есть ли какая-то известная связь между трудностью признания класса и «плохим поведением» запрещенной семьи? Такое отношение должно существовать? Это "плохое поведение" было оформлено где-то?

cc.complexity-theory graph-theory np-hardness Виниций душ Сантуш
источник

Ответы:

Хотя кажется интуитивно понятным, что список запрещенных (индуцированных) подграфов для класса графов, обладающих NP-трудным распознаванием, должен обладать некоторой «внутренней» сложностью, я недавно обнаружил некоторые поразительные отрицательные доказательства этой интуиции в литературе. $\mathscr{C}$

Пожалуй, самое простое для описания это следующее, взятое из статьи Б. Левека, Д. Лин, Ф. Маффрея и Н. Тротиньона .

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

Пусть теперь семейство графов , которые составлены точно так же, за исключением того, что вы добавляете четыре вершины: две смежные с одной и той же вершины цикла (как и раньше), но теперь две смежные с одной и той же вершины из цикл, где снова и не являются последовательными. $F'$ $u$ $v$ $u$ $v$

Тогда класс графов с в качестве запрещенных индуцированных подграфов имеет распознавание за полиномиальное время, тогда как распознавание класса с в качестве запрещенных индуцированных подграфов является NP-трудным. $F$ $F'$

Поэтому мне трудно представить какое-либо общее условие, которому должен удовлетворять список запрещенных индуцированных подграфов, когда он приводит к классу с (NP-) жестким распознаванием, учитывая, что такое условие должно будет отделять «очень похожие» и выше. $F$ $F'$

Хьюго Нобрега
источник

Хороший ответ - это довольно деликатно.

Суреш Венкат

Интересный. Есть ли вероятность, что это как-то связано с выразительностью логики, необходимой для описания шаблона? Я думаю о чем-то похожем на формальные языки, где сложность языка может быть эквивалентно охарактеризована тем, как он определяется (регулярное выражение, формальная грамматика ...) или машиной, необходимой для его распознавания (автомат, pushdown ...) или выразительность логики, необходимой для написания формулы, характеризующей слова языка (например, MSO для обычных языков).

a3nm

Это интересная идея, но опять же я не могу не думать , что

являются настолько близки , что трудно представить себе образ «разделения» их так (скажем , с помощью

будучи описываться на языке,

не является ). Я мог бы быть слишком негативным, хотя ..! По общему признанию, я иду на «интуицию» здесь, поэтому я был бы рад оказаться неправым.

F

$F$

F^{'}

$F'$

F

$F$

F^{'}

$F'$

Уго Нобрега

@Гюго: одно ощутимое различие между ними заключается в симметрии в характеристике

- по сути нет никаких средств для разграничения вершин

. Что произойдет, если вы рассмотрите семейство циклов

длиной не менее четырех, плюс две дополнительные вершины, смежные с непоследовательными вершинами в цикле? Делает ли восстановление симметрии «другое» направление (удаление вершины из

вместо добавления одного) затруднительным?

F^{'}

$F'$

u

$u$

v

$v$

F_{0}

$F_0$

F

$F$

Стивен Стадницки

@ Steven: Думаю, нет, можно обнаружить графы в

, случайно угадав 8 узлов, образуя обе стороны графа, и выполнить алгоритм «три в дереве» на трех узлах, как в теореме 3.1. Это дает алгоритм полиномиального времени для обнаружения

F_{0}

$F_0$

F_{0}

$F_0$

Сянь-Чи Чанг 之之

Ответ @Hugo действительно хорош, и здесь я хочу добавить некоторые личные мнения.

Есть родственные семейства, подобные графам в семействе F и F '. Графы в семействе B1 в статье обычно называют пирамидами. А графики в семействе B2 обычно называют призмами. Смотрите ответ здесь для иллюстрации. В литературе по проблемам обнаружения индуцированных подграфов они использовались для обнаружения четных / нечетных дырок, которые представляют собой хордовые циклы с четной / нечетной длиной. По известной теореме о сильном совершенном графе граф G идеален, если и G, и дополнение G не содержат нечетных дырок.

Для семейств пирамид и призм фактически есть различия между ними - у одного есть индуцированное поддерево из трех листьев, а у другого нет. Это называется проблемой «три в дереве» , которая изучалась Чудновским и Сеймуром. Удивительно, что определение, существует ли индуцированное дерево, которое содержит три заданных узла, поддается обработке, в то время как проблема «четыре в центре дерева» является NP-трудной . (Центрированное дерево - это дерево с не более чем одним узлом со степенью больше 2.) Различия между F и F ', по-видимому, вызваны одной и той же причиной.

Но кажется, что полная характеризация все еще трудна, потому что мы даже не знаем сложности обнаружения графов в некоторых из семейств, которые выглядят достаточно простыми, как графы без нечетных отверстий (!). А для семейств, о которых мы знаем, что существует алгоритм полиномиального времени, например, совершенные графы и графы без четных отверстий, хотя существуют общие стратегии (основанные на разложениях) для разработки алгоритма, необходимо предоставить конкретную структурную теорему для их. Обычно это семейно-зависимый процесс, и в большинстве случаев доказательства действительно длинные. ( Вот пример для графика без четных отверстий, где бумага занимает более 90 страниц.)

Тем не менее было бы интересно иметь некоторые классификации для индуцированных проблем обнаружения подграфов, в том смысле, как проблема «три в дереве».

Сянь-Чжи Чан 張顯之
источник