В графе независимое множество - это подмножество вершин, которое не содержит ребра в качестве индуцированного подграфа. Проблема нахождения наибольших независимых множеств в графе является фундаментальным и сложным в этом вопросе. Давайте рассмотрим более общий вопрос поиска (размера) наибольшего множества 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).
Ответы:
Предположим, что имеет как минимум две вершины. Семейство всех -свободных графов является наследственным на индуцированных подграфах, и свойство быть -свободным нетривиально, где свойство нетривиально, если оно истинно для бесконечного числа графов, и ложно для бесконечно большого числа графов. Таким образом, применим результат Льюиса и Яннакакиса [1], показывающий, что для всех имеющих хотя бы две вершины, задача NP-полна.H H HH H H H
[1] Джон М. Льюис, Михалис Яннакакис: Проблема удаления узлов для наследственных свойств является NP-полной. J. Comput. Сист. Sci. 20 (2): 219-230 (1980)
источник