Независимое множество с dist(u, w) > 2
Мне нужна помощь в решении проблемы сокращения:
Для графа G и числа k существует множество V' в V(G) такое, что |V'| >= k и dist(u,v) > 2 для всех u, v в V'?
На первый взгляд это выглядит как проблема с независимым набором, но расстояние между двумя узлами должно быть не менее 3, а не 2. Есть ли какой-нибудь совет, как мне уменьшить эту проблему, чтобы доказать, что она находится в NPC?
между ними должно быть 2 вершины, а не одна. Да, это эквивалентно >= 3.
Я думаю, что неправильно понял вашу проблему. Вы говорите, что расстояние между двумя узлами должно быть не менее 3 в изложенной вами задаче, но не в задаче о независимом наборе, и поэтому они не являются эквивалентными задачами. Я сначала прочитал наоборот.
Ответы 1
Предположим, вам задана обычная задача о независимом множестве (то есть граф G и число k, и вас спросили, существует ли такое подмножество вершин G, что все они находятся на расстоянии 2 или более друг от друга).
Во-первых, если k или k+1 равно |V|, просто проверьте все возможные подграфы. Итак, предположим, что k+1 < |V|.
Если вам дали задачу о независимом множестве, начните с добавления вершины в середине каждого ребра. Добавьте одну дополнительную вершину * и присоедините * к каждой из других новых вершин.
Утверждение: существует решение проблемы размера k+1 в этом новом графе тогда и только тогда, когда в исходном графе существует независимое множество размера k.
Для прямого направления предположим, что в этом новом графе есть набор вершин размера k+1, так что каждая пара вершин находится на расстоянии не менее 3. Тогда в этом наборе может быть не более 1 новой вершины (поскольку они все находятся на расстоянии 1 или 2 друг от друга), поэтому у вас есть независимый набор размера k в исходном графе.
В обратном направлении, если в исходном графе есть независимый набор размера k, то в новом графе есть решение размера k+1 — вершины независимого набора размера k плюс добавленная вершина ребра. это не инцидентно ни одной из вершин независимого множества (вот почему нам нужно k+1 < |V|).
Таким образом, мы показали, что если у вас есть решение задачи с полиномиальным временем, вы можете решить задачу о независимом множестве также за полиномиальное время.
То, что проблема NP, легко увидеть — очевидно, можно проверить подграф, чтобы увидеть, является ли это решением за полиномиальное время.
Таким образом, проблема в вопросе является NP-полной.
«добавленная вершина ребра, не инцидентная ни одной из вершин в независимом множестве» хммм, не понимаю, почему должно быть такое ребро, даже с учетом предположения. Вы можете просто сделать клику из разделяющих вершин вместо добавления *.
@DavidEisenstat, ты прав насчет края. Вы видите легкое решение?
Соедините каждую пару средних вершин. Затем, предполагая отсутствие изолированных вершин (достаточно легко обрабатывать их вне редукции), решения будут (1) чем-то, что соответствует независимому множеству в исходном графе (2) ровно одной средней вершине.
Почему расстояние должно быть не менее 3? Разве
dist(u,v) = 2не означает, что междуuиvесть еще одна вершина? Также в вашем заявлении о проблеме говоритсяdist(u,v) > 2, что для меня эквивалентноdist(u,v) >= 3.