H-свободный раздел

Это вопрос, навеянный проблемой H-свободного разреза . Для данного графа разбиение его множества вершин на частей является -свободным, если не индуцирует копию для всех , . $V$ $r$ $V_1, V_2, \ldots, V_r$ $H$ $G[V_i]$ $H$ $i$ $1 \leq i \leq r$

Я хочу рассмотреть следующий вопрос:

Какое наименьшее для которого существует свободное разбиение на частей? $r$ $H$ $r$

Обратите внимание, что когда - одно ребро, то это равносильно нахождению хроматического числа и уже является NP-полным. Я задаюсь вопросом, легче ли показать NP-полноту для любого фиксированного для этой проблемы (проще, чем показывать его для free-cut). Я даже думал, что это может быть очевидно, но я никуда не попал. Вполне возможно, я что-то упускаю довольно просто, и если это так, я был бы признателен за некоторые указатели! $H$ $H$ $H$

graph-theory np-hardness co.combinatorics Neeldhara
источник

Вы имеете в виду: для всех

и для всех

подграф группы

индуцированный

, не изоморфен

i

$i$

U \subseteq V_{i}

$U \subseteq V_i$

G

$G$

U

$U$

H

$H$

Юкка Суомела

Я думаю, что ответ RJK на другую проблему, связанную с этим, относится к этой проблеме (на самом деле лучше, чем к другой проблеме).

Цуёси Ито

@Jukka: Я так и делаю. Спасибо за указатель, и прости меня за то, что я слишком ленив (по крайней мере сейчас), чтобы обновить вопрос соответственно!

Нилдхара

@Tsuyoshi: Да, и теперь у меня есть более сложная версия ответа! Тем не менее, я должен сказать, что я опубликовал это, потому что я оказался в ситуации «я попал в тупик, думая о X и Y, кажется, связан и легче начать». Я просто подумал, что должен поделиться деталями Y для остальных, кто думал о X, и это не было изначально предназначено для запроса ссылки :)

Neeldhara

Серж Гасперс сослался на старую (1980 г.) статью Льюиса и Яннакакиса, которая кажется здесь очень актуальной!

RJK

Ответы:

Самые ранние ссылки, которые я знаю на этот тип проблемы, следующие. Они также упоминаются в статье Коуэна, Годдарда и Иезурума, о которой я упоминал в другой ветке.

Эндрюс и Якобсон. (1985) Об обобщении хроматического числа. В учеб. 16-я Юго-восточная международная конференция по комбинаторике, теории графов и вычислительной технике (Бока-Ратон, 1985), Congr. Numer. 47 33–48.

Коуэн, Коуэн и Вудолл. (1986) Дефектные раскраски графов на поверхностях: разбиения на подграфы ограниченной валентности. J. Теория графов 10 187–195.

Харари. (1985) Условная окрашиваемость в графах. В Графиках и Приложениях (Boulder 1982), Wiley-Interscience, pp. 127–136.

Харари и Джонс (урожденная Фрагно). (1985) Условная окрашиваемость II: двудольные вариации. В учеб. Конференция Sundance по комбинаторике и смежным вопросам (Sundance 1985), Congr. Numer. 50 205–218.

AFAIK, пока нет бумаги, дающей явную дихотомию P / NP-c для различных вариантов H. Однако это было сделано Адом и Несетрилом для другого типа обобщения хроматического числа, «H-раскрасок». ", гомоморфизму.

RJK
источник

Большое спасибо за ваш очень подробный ответ - высоко ценится. Это существенное дополнение к моему списку чтения, оно должно занять меня некоторое время!

Нилдхара

Что ж, не проблема, хотя, как я уже упоминал ранее, помимо статьи JGT, их довольно сложно отследить. (На самом деле, я должен признать, что у меня пока что мало что получалось, несмотря на то, что у меня был доступ к большому количеству канадских университетских библиотек.) В любом случае, статья Коуэна, Годдарда и Иезурума, вероятно, наиболее актуальна и отвечает на вопрос вашего / Морона о H будучи неподвижной звездой, даже ограниченной плоскими графами. Вероятно, самые хорошие открытые (я думаю?) Классы H, в которые можно погрузить зубы, были бы циклами или кликами.

RJK

$F_1$ $F_2$ $F_1$ $F_2$ $F_1$ $F_2$

(F-free = {для всех H в F, H-free})

См. Www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf.

Аравиндом
источник