Предисловие. Классы сложности. NP-сложные задачи

ExampleПример 1

Рассмотрим языки \[ \begin{align} \mathrm{HAMPATH} & = \left\{ \langle G\rangle \; : \; G = (V,E) \text{ -- это орграф с гамильтоновым путем}\right\} \\ \mathrm{HAMPATH}_{st} & = \left\{ \langle G, s, t\rangle \; : \; G = (V,E), \; s,t \in V, \text{в орграфе $G$ есть гамильтонов путь из $s$ в $t$}\right\} \\ \mathrm{HAMCYCLE} & = \left\{ \langle G\rangle \; : \; G = (V,E) \text{ -- это орграф с гамильтоновым циклом}\right\} \\ \mathrm{UHAMPATH} & = \left\{ \langle G\rangle \; : \; G = (V,E) \text{ -- это неор. граф с гамильтоновым путем}\right\} \\ \mathrm{UHAMPATH}_{st} & = \left\{ \langle G, s, t\rangle \; : \; G = (V,E), \; s,t \in V, \text{в неор. графе $G$ есть гамильтонов путь из $s$ в $t$}\right\} \\ \mathrm{UHAMCYCLE} & = \left\{ \langle G\rangle \; : \; G = (V,E), \text{в неор. графе $G$ есть гамильтонов цикл}\right\} \\ \end{align} \] Сведите полиномиально эти языки друг к другу.

SolutionРешение

• \(\mathrm{HAMPATH} \stackrel{?}{\leq }_p \mathrm{HAMPATH}_{st}\).

Сведение \(\mathrm{HAMPATH}\) к \(\mathrm{HAMPATH}_{st}\)

Добавляем вершины \(s'\) и \(t'\), соединённые со всеми вершинами графа (красные дуги из \(s'\), зелёные — в \(t'\)), и концы \(s\to s'\), \(t'\to t\). Шаги показывают построение; наведите курсор на вершину, чтобы подсветить её дуги.

⟶

• \(\mathrm{HAMPATH}_{st} \stackrel{?}{\leq }_p \mathrm{HAMPATH}\).

Сведение \(\mathrm{HAMPATH}_{st}\) к \(\mathrm{HAMPATH}\)

Добавляем вершину \(s'\) с единственной дугой \(s'\to s\) и вершину \(t'\) с единственной дугой \(t\to t'\). Наведите курсор на вершину, чтобы увидеть её степени и подсветить дуги.

⟶

• \(\mathrm{HAMPATH} \stackrel{?}{\leq }_p \mathrm{HAMCYCLE}\) (и аналогично \(\mathrm{UHAMPATH} \leq_p \mathrm{UHAMCYCLE}\)).

Сведение \(\mathrm{HAMPATH}\) к \(\mathrm{HAMCYCLE}\)

Добавляем новую вершину \(s\), соединённую дугами в обе стороны со всеми вершинами графа: \(s\to v\) (красные) и \(v\to s\) (зелёные). Наведите курсор на \(s\), чтобы подсветить все её дуги.

⟶

• \(\mathrm{HAMCYCLE} \stackrel{?}{\leq }_p \mathrm{HAMPATH}_{st}\) (та же конструкция дает и \(\mathrm{HAMCYCLE} \leq_p \mathrm{HAMPATH}\)).

Сведение \(\mathrm{HAMCYCLE}\) к \(\mathrm{HAMPATH}_{st}\)

Берём произвольную вершину \(v_1\) и копируем её: новая вершина \(v_1'\) получает те же дуги (красные). Затем добавляем \(s\) и \(t\) с дугами \(s\to v_1'\) и \(v_1\to t\) (зелёные). Наведите курсор на \(v_1\) и \(v_1'\), чтобы сравнить их дуги.

⟶

• \(\mathrm{HAMPATH}_{st} \stackrel{?}{\leq }_p \mathrm{UHAMPATH}_{st}\).

Сведение \(\mathrm{HAMPATH}_{st}\) (орграф) к \(\mathrm{UHAMPATH}_{st}\) (неориентированный граф)

Каждую вершину \(v\), кроме \(s\) и \(t\), расщепляем на тройку \(v^{\mathrm{in}}-v^{\mathrm{mid}}-v^{\mathrm{out}}\); для \(s\) оставляем только \(s^{\mathrm{out}}\), для \(t\) — только \(t^{\mathrm{in}}\). Дуга \(u\to v\) становится ребром \(\{u^{\mathrm{out}},v^{\mathrm{in}}\}\). Наведите курсор на вершину нижнего графа, чтобы увидеть, какой вершине исходного орграфа она отвечает.

• \(\mathrm{UHAMPATH}_{st} \stackrel{?}{\leq }_p \mathrm{HAMPATH}_{st}\).

Сведение \(\mathrm{UHAMPATH}_{st}\) к \(\mathrm{HAMPATH}_{st}\)

Каждое ребро \(\{u,v\}\) заменяем парой встречных дуг \(u\to v\) и \(v\to u\); вершины, включая \(s\) и \(t\), не меняются. Кнопка ниже прокладывает один и тот же гамильтонов \(s\)–\(t\)-путь в обоих графах: слева по рёбрам, справа — по дугам в нужную сторону.

⟶

ExampleПример 2

Покажите, что определение наличия в графе клики произвольного заданного размера является NP-сложной задачей.

SolutionРешение

Докажем

\[ \mathrm{3SAT} \leq _p \mathrm{CLIQUE} \]

где

\[ \mathrm{CLIQUE} = \left\{ \langle G,k\rangle \; : \; \text{$G$ -- это неор. граф, $k \in \mathbb {N}$, в $G$ есть клика размера $k$}\right\} \]

Пусть \(\phi\) – это 3КНФ-формула с \(k\) клозами \(c_1, \ldots , c_k\). Построим по ней граф \(G\): для каждого клоза \(c_i = (a_i \lor b_i \lor d_i)\) заведем тройку вершин, помеченных литералами \(a_i\), \(b_i\), \(d_i\). Ребром соединим каждую пару вершин из разных троек, кроме пар противоречащих литералов вида \(x\) и \(\bar{x}\); внутри тройки ребер нет. Положим \(f(\phi ) = \langle G, k \rangle\); построение выполняется за полиномиальное время.

Пусть \(\phi\) выполнима. Зафиксируем выполняющий набор и выберем в каждом клозе по одной вершине с истинным литералом. Выбранные \(k\) вершин лежат в разных тройках и попарно непротиворечивы (все их литералы истинны одновременно), поэтому попарно соединены ребрами – получили клику размера \(k\).

Обратно, пусть в \(G\) есть клика размера \(k\). Внутри троек ребер нет, поэтому клика содержит ровно по одной вершине из каждой тройки. Литералы этих вершин попарно непротиворечивы, значит, существует набор значений переменных, делающий все их истинными (переменным, не встретившимся среди литералов клики, даем произвольные значения). Такой набор делает истинным хотя бы один литерал в каждом клозе, т.е. выполняет \(\phi\).

Сведение \(\mathrm{3SAT}\) к \(\mathrm{CLIQUE}\)

Граф для формулы \(\phi=(x_1\lor x_1\lor x_2)\land(\bar x_1\lor\bar x_2\lor\bar x_2)\land(\bar x_1\lor x_2\lor x_2)\), \(k=3\): по тройке вершин на клоз, рёбра — между непротиворечивыми литералами разных троек (внутри клоза рёбер нет). Выберите набор значений: истинные литералы подсвечиваются, и если каждый клоз выполнен, из них складывается клика размера \(3\).

\(x_1=\) \(x_2=\)

ExampleПример 3

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

SolutionРешение

Докажем

\[ \mathrm{3SAT} \leq _p \mathrm{HAMPATH}_{st} \]

Допустим, есть формула

\[ \phi = \underbrace{\left(x_1 \lor \bar{x}_2 \lor x_3 \right)}_{c_1} \land \underbrace{\left(\bar{x}_1 \lor x_2 \lor x_4\right)}_{c_2} \land \underbrace{\left(\bar{x}_1 \lor x_3 \lor x_5\right)}_{c_3} \land \underbrace{\left(x_1 \lor \bar{x}_4 \lor \bar{x}_5\right)}_{c_4} \]

Необходимо построить \(f(\phi ) = (G,s,t)\). Для каждой переменной \(x_i\) заведем <<ромб>> с горизонтальной цепочкой вершин внутри, а для каждого клоза \(c_j\) – отдельную вершину. Гамильтонов путь из \(s\) в \(t\) вынужден проходить ромбы сверху вниз, и в каждом ромбе он проходит цепочку либо слева направо (это отвечает \(x_i = 1\)), либо справа налево (\(x_i = 0\)). Если литерал \(x_i\) входит в клоз \(c_j\), то из цепочки \(i\)-го ромба можно сделать <<крюк>> в вершину \(c_j\) и вернуться, двигаясь слева направо; для литерала \(\bar{x}_i\) – двигаясь справа налево. Тогда гамильтонов путь, посещающий все вершины-клозы, существует в точности тогда, когда есть набор значений переменных, при котором в каждом клозе есть истинный литерал.

Сведение \(\mathrm{3SAT}\) к \(\mathrm{HAMPATH}_{st}\)

Пять «ромбов» переменных \(x_1,\ldots,x_5\) (\(s\) — верхняя вершина, \(t\) — нижняя) и вершины-клозы \(c_1,\ldots,c_4\) справа. Схема упрощена: показаны только «крюки» из ромба \(x_1\) (красные — для вхождений \(x_1\) в \(c_1\) и \(c_4\), проходятся слева направо; зелёные — для \(\bar x_1\) в \(c_2\) и \(c_3\), справа налево), а цепочка внутри ромба сокращена до трёх вершин (в честной конструкции их \(3k+1\)). Выберите значение \(x_1\), чтобы проложить путь: направление обхода ромба кодирует значение переменной, а заход в клоз возможен только «по ходу».

\(x_1=\)