Доказательство того, что проблема выбора пути является NP-полной

Опубликовано: 17 Февраля, 2022

Предпосылка - NP-полнота
Проблема решения проблемы выбора пути спрашивает, можно ли выбрать по крайней мере k путей из заданных путей графа, так что никакие два выбранных пути не имеют общих вершин.

Чтобы доказать, что проблема является NP-полной, нам нужно показать, что она одновременно NP и NP-трудна. Мы используем PSP для обозначения нашей проблемы выбора пути.

PSP принадлежит НП:
Мы докажем это, построив средство проверки за полиномиальное время. Если какая-либо проблема находится в NP, то, имея «сертификат» (решение) проблемы и экземпляр проблемы (в данном случае граф G и положительное целое число k), мы сможем проверить (проверить независимо от того, является ли данное решение правильным или нет) сертификат за полиномиальное время.

Сертификат для PSP - это набор путей P '. Это независимые пути без общих ребер. Мы можем проверить, существуют ли k путей, независимых для данного графа G (V, E)) и путей P, следующим образом:

 Проверьте, является ли P 'подмножеством P
Если нет, то данное решение неверно
Количество путей в P 'не менее k
Если нет, то данное решение неверно

Инициализировать список логических значений длины | V |
для каждого пути p в P '
    для каждой вершины в p
        проверьте, помечено ли оно как True в нашем списке
        Если да, то данное решение неверно
        В противном случае помечает вершину как True

Поскольку ни одна вершина не была отмечена дважды,
данное решение правильное.

Вышеупомянутый верификатор является полифаймом, поскольку:

  1. Проверка того, что P 'является подмножеством P, может быть выполнена за O (| P |).
  2. Проверить количество путей в P 'можно за O (| P' |)
  3. Проверить, что все пути не пересекаются, можно за O (| V |)

Следовательно, общая временная сложность:

Следовательно, PSP имеет полиномиальную проверяемость по времени и, следовательно, принадлежит к классу NP.

Задача решения клики принадлежит NP-Hard:
Чтобы доказать, что PSP является NP Hard, мы берем некоторую задачу, которая уже была доказана как NP Hard (независимый набор в нашем случае), и показываем, что эта проблема может быть сведена к PSP за полиномиальное время. Поскольку мы знаем, что независимый набор является NP полным, это также NP сложно.

Учитывая экземпляр IS -

 G = (V, E) и k

Мы создаем экземпляр PSP следующим образом:

Создаем новый граф G '. Для каждой вершины v i в G:

  1. Обозначим путь через P i для v i .
  2. Пусть e 1 , e 2 ,…, e r - ребра, соединенные с v i . Введем вершину для каждого такого ребра в G '. Далее введем пару вершин в G '- s i , t i .

Таким образом,

Мы можем ясно видеть, что приведенное выше сокращение является полифаймом (со сложностью = O (| V | + | E |)), поскольку мы, по сути, перебираем все вершины и ребра в нашем исходном графе.

Доказательство :
Доказательство того, что проблема независимого множества сводится к проблеме выбора пути. Чтобы доказать правильность нашей редукции, докажем следующие два аргумента.

(i) ДА, экземпляр для IS => Да, экземпляр для PSP
У нас есть экземпляр ДА для ЕСТЬ.

  1. Для графа G = (V, E) существует независимое множество размера не менее k.
  2. Существует не менее k вершин, у которых нет общих ребер.
  3. В экземпляре PSP существует как минимум k путей, которые не имеют общих узлов. Поскольку мы определяем вершины G как аналогичные путям в примере PSP, а ребра G как аналогичные вершины в этих путях. И любой из этих узлов разделения пути будет означать, что некоторые две вершины в независимом множестве имеют общее ребро, что невозможно.
  4. Да, экземпляр для PSP.

(ii) ДА, экземпляр для PSP => Да, экземпляр для IS
ETP: Нет экземпляра для IS => Нет экземпляра для PSP. (Доказательство контрапозитивом.)

Мы знаем, что всякий раз, когда существует независимый набор размера не менее k, существует независимый набор размера ровно k (это можно сделать, взяв подмножество размера k из большего набора). Следовательно, контрапозитив также верен. (т. е. всякий раз, когда не может существовать независимый набор размера ровно k, не может существовать независимый набор размера не менее k).

У нас нет экземпляра IS.

  1. Для графа G = (V, E) не может существовать независимого множества размера k.
  2. Невозможно найти k вершин графа G, не имеющих общих ребер.
  3. Каждый набор S вершин размера k будет содержать vi и vj, которые имеют общее ребро.
  4. Поскольку мы определяем вершины G как аналог путей в примере PSP и ребра G как аналог вершин в этих путях, каждый набор путей размера k в случае PSP будет иметь общий узел.
  5. Не может существовать k путей, которые не имеют общих узлов в экземпляре PSP.
  6. Нет экземпляра для PSP.

Следовательно, для конкретного случая проблема IS сводится к PSP. Следовательно, PSP NP-Hard.

Таким образом, проблема выбора пути является NP-трудной. Следовательно, проблема выбора пути является NP-полной.

Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований по SDE с помощью курса теории CS по доступной для студентов цене и будьте готовы к работе в отрасли.

РЕКОМЕНДУЕМЫЕ СТАТЬИ