Вычисление макс. H-свободных множеств

11

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

Для фиксированного графа H, заданного входного графа G, сложно ли определить размер наибольшего множества без H в G?

Есть ли разумный способ построить «таблицу» графов H (или классов H), чтобы заполнить записи правильными ответами «да» или «нет» на поставленный выше вопрос? (Давайте представим, что «no» = P, и даже то, что запись «no» означает, что существует алгоритм polytime для генерации наибольшего множества H-free.)

Если это не так, существуют ли нетривиальные классы H, для которых ответ - да? ... нет?

Я копался в поисках двух запросов об обобщенных / без H-хроматических числах - здесь и здесь - когда мне пришло в голову, что (якобы более простая) "двойная" проблема H-свободного аналога номера независимости также может быть открытым. Мне известны классические работы по связанной проблеме для случайных графов, ср. например, Erdos, Suen and Winkler (1995) или Bollobas and Thomason (2000), которые все еще ведут очень активную исследовательскую работу. Так что, возможно, уже есть какая-то работа, которую я еще не видел, касающаяся этого более основного вопроса, и что грубый поиск в интернете не раскрыл (отсюда тэг reference-request).

RJK
источник
3
Если k и H оба фиксированы, вы можете просто перечислить все подмножества вершин размера k и проверить, содержат ли они H в качестве индуцированного подграфа. Это будет алгоритм полиномиального времени.
Робин Котари
извините за глупость: редактирование, чтобы удалить все экземпляры k!
RJK

Ответы:

10

Предположим, что имеет как минимум две вершины. Семейство всех -свободных графов является наследственным на индуцированных подграфах, и свойство быть -свободным нетривиально, где свойство нетривиально, если оно истинно для бесконечного числа графов, и ложно для бесконечно большого числа графов. Таким образом, применим результат Льюиса и Яннакакиса [1], показывающий, что для всех имеющих хотя бы две вершины, задача NP-полна.H H HHHHH

[1] Джон М. Льюис, Михалис Яннакакис: Проблема удаления узлов для наследственных свойств является NP-полной. J. Comput. Сист. Sci. 20 (2): 219-230 (1980)

Серж Гасперс
источник
Пятно на! Спасибо за ссылку! Может быть, этот тип подхода также может быть (был?) Применен для проблемы разделения?
RJK
1
Я не слежу за рассуждениями здесь. Задача NP-трудна даже тогда, когда H не имеет ребер, если H имеет хотя бы две вершины.
Андрас Саламон
@Andras. Да, ты прав. Я немного обобщу, что мой ответ из имеет хотя бы одно ребро, чтобы имело как минимум две вершины. Вы получите голосование, конечно. HHH
Серж Гасперс
Этот ответ (редакция 2) относится к проблеме поиска наибольшего индуцированного подграфа, который не содержит H в качестве подграфа . Результат Льюиса и Яннакакиса относится к задаче нахождения наибольшего индуцированного подграфа, который не содержит H в качестве индуцированного подграфа , но условие на H для свойства, являющегося нетривиальным, отличается.
Цуёси Ито
@ Tsuyoshi: Под графом нет , я имею в виду, что граф не имеет как индуцированный подграф (как в вопросе). HHH
Серж Гасперс