NP-полнота Основные NP-полные задачи

Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество на k вершинах? Независимым множеством называется такое подмножество вершин V V, что любые две его вершины не соединены ребром в G.

Независимое множество Теорема 3.1 (Karp 1972) Задача «Независимое множество» является NP-полной.

Идея доказательства «Выполнимость» «Независимое множество» «Выполнимость»: –множество переменных X, –набор дизъюнкций Z ={Z 1,…,Z m } c Z i ={λ i1,…, λ ik i } (i = 1,…,m), где λ ij литералы на X. Построим граф G, такой что G имеет независимое множество размера m тогда и только тогда, когда существует набор значений истинности, при котором выполнены все m дизъюнкций.

Сведение Z i : клика на k i вершинах (вершина соответствует литералу в дизъюнкции) Вершины разных клик связаны между собой ребром, если они соответствуют литералу и его отрицанию.

Пример

Доказательство Пусть в G есть независимое множество размера m. Тогда, оно содержит по одному элементу в каждой клике и не содержит двух вершин, соответствующих литералу и его отрицанию. То есть, эти вершины определяют по литералу в каждой дизъюнкции. Положим каждому такому литералу значение true и дополним до набора значений истинности, который выполняет все дизъюнкции.

Доказательство Пусть существует набор значений истинности, при котором выполнены все m дизъюнкций. Выберем в каждой дизъюнкции один литерал со значением true. Множество соответствующих вершин определяет искомое независимое множество.

Задача «Вершинное покрытие» Условие. Задан граф G и целое число k. Вопрос. Существует ли вершинное покрытие мощности k? Вершинное покрытие это множество вершин V V такое, что каждое ребро имеет граничную точку в V.

Задача «Клика» Условие. Задан граф G и целое число k. Вопрос. Существует ли клика мощности k? Кликой называется такое подмножество вершин V V, что любые две его вершины соединены ребром в G.

Вершинное покрытие и клика Теорема 3.2 (Karp 1972) Задача «Вершинное покрытие» и задача «Клика» являются NP-полными.

Задача «Гамильтонов цикл» Условие. Задан граф G. Вопрос. Существует ли в G гамильтонов цикл?

Гамильтонов цикл Теорема 3.3 (Karp 1972) Задача «Гамильтонов цикл» является NP-полной.

Идея доказательства «Вершинное покрытие» «Гамильтонов цикл» «Вершинное покрытие»: G = (V,E), k 0, целое. Построим граф G = (V,E), такой что G имеет гамильтонов цикл тогда и только тогда, когда в G есть вершинное покрытие H, состоящее из не более чем k элементов. Пусть |E| = m.

Построение графа G |V| = 12m+k Каждому ребру (v i, v j ) в исходном графе соответствует 12 вершин u ij1, u ij2, u ij3, u ij4, u ij5, u ij6, u ji1, u ji2, u ji3, u ji4, u ji5, u ji6. k дополнительных вершин a 1, a 2,…, a k.

Компонента (v i, v j ) u ij1 u ij2 u ij3 u ij4 u ij5 u ij6 u ji1 u ji2 u ji3 u ji4 u ji5 u ji6 v i H, v j H v i H, v j H v i H, v j H

Компонента v i Пусть r степень вершины v i. Упорядочим произвольным образом ребра, инцидентные v i : (v i, v j 1 ), (v i, v j 2 ),…, (v i, v j r ). Все компоненты, соответствующие ребрам, инцидентным v i, соединяются вместе следующими ребрами:

Компонента вершины u ij 1 1 u ij 1 6 u ij 2 1 u ij 2 6 u ij r 1 u ij r 6 u ij 3 1 u ij 3 6

Дополнительные вершины в G Дополнительная вершина a l соединена с первой и последней вершиной компоненты v i. Пусть r степень вершины v i.

Компонента вершины u ij 1 1 u ij 1 6 u ij 2 1 u ij 2 6 u ij r 1 u ij r 6 u ij 3 1 u ij 3 6