Банк задач по математике

Пример 7.43

Покажите, что $\mathrm{Min-VC}$ является NP-полной задачей поиска.

?

Примечание.

?

$\mathrm{Min-VC}$ : для данного графа $G$ найти минимальное вершинное покрытие графа $G$ .

Пример 7.46

$\mathrm{TSP}$ является NP-полной.

?

Примечание.

?

Задача коммивояжёра (TSP): Дан полный граф $G=(V, E)$ с функцией стоимости $c: E \rightarrow \mathbf{N}$ и целое $k$ , определить, существует ли тур (то есть гамильтонов цикл) графа $G$ с суммарной стоимостью рёбер, не превышающей $k$ .

Пример 7.47

Задача $r$ -Approx- $\mathrm{TSP}$ является NP-полной для всех $r>1$ .

?

Примечание.

?

Задача коммивояжёра (TSP): Дан полный граф $G=(V, E)$ с функцией стоимости $c: E \rightarrow \mathbf{N}$ и целое $k$ , определить, существует ли тур (то есть гамильтонов цикл) графа $G$ с суммарной стоимостью рёбер, не превышающей $k$ .

Для графа $G$ с функцией стоимости $c$ на его рёбрах пусть $K^{*}(G, c)$ обозначает минимальную стоимость маршрута графа $G$ . Для $r>1$ приближённая версия $r$ -Approx-TSP спрашивает: для данного полного графа $G=(V, E)$ с функцией стоимости $c: E \rightarrow \mathrm{N}$ найти маршрут графа $G$ суммарной стоимостью не более $r \cdot K^{*}(G, c)$ .

Пример 7.49

Задача $r$ -Approx- $\mathrm{VC}$ является NP-полной для некоторого $r>1$ .

?

Примечание.

?

Вершинное покрытие (VC): Даны граф $G$ и положительное целое $k$ , определить, есть ли в $G$ вершинное покрытие размера не более $k$ .

Пусть $vc^{*}(G)$ обозначает размер минимального вершинного покрытия графа $G$ . Для $r>1$ приближённая версия $r$ -Approx-VC спрашивает: для данного графа $G$ найти вершинное покрытие $C$ графа $G$ такое, что $\left|C\right| \leq r \cdot vc^{*}(G)$ .

Пример 7.51

Для каждого $d \geq 3$ задача $r$ -Approx- $\mathrm{VC}$ - $d$ является NP-полной для некоторого $r>1$ .

?

Примечание.

?

Вершинное покрытие (VC): Даны граф $G$ и положительное целое $k$ , определить, есть ли в $G$ вершинное покрытие размера не более $k$ . VC- $d$ обозначает задачу VC, ограниченную графами степени не более $d$ .

Пусть $vc^{*}(G)$ обозначает размер минимального вершинного покрытия графа $G$ . Для $r>1$ приближённая версия $r$ -Approx-VC- $d$ спрашивает: для данного графа $G$ степени не более $d$ найти вершинное покрытие $C$ графа $G$ такое, что $\left|C\right| \leq r \cdot vc^{*}(G)$ .

Пример 7.52

Для $1<r<\sqrt{2}$ задача $r$ -Approx- $\mathrm{BST}$ является NP-полной.

?

Примечание.

?

Bottleneck Steiner Tree ( $\mathrm{BST}$ ): для данного множества $P=\left\{ p_{1}, p_{2}, \ldots , p_{n}\right\}$ из $n$ точек на евклидовой плоскости и положительного целого числа $k$ найти дерево Штейнера над терминальными точками $p_{1}, p_{2}, \ldots , p_{n}$ не более чем с $k$ точками Штейнера, такое что длина самого длинного ребра дерева минимальна.

Для $r>1$ приближённая версия $r$ -Approx-BST спрашивает: для тех же данных найти дерево Штейнера не более чем с $k$ точками Штейнера, длина самого длинного ребра которого не более чем в $r$ раз превышает оптимальную (минимальную) длину самого длинного ребра.

Задача 7.5.1

(a)(b)(c)(d)

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

?

(a)

Max- $3\mathrm{SAT}$ .

(b)

Версия оптимизации KNAPSACK.

(c)

$\mathrm{LP}$ (версия оптимизации): для данного графа $G$ найти самый длинный простой путь в $G$ .

(d)

Для данного положительного целого числа $n$ найти его наибольший простой делитель.

Задача 7.5.2

(a)(b)(c)(d)

Для каждой из следующих задач оптимизации покажите, что она NP-полна:

?

(a)

Для данного ориентированного графа найти минимальное подмножество рёбер такое, что каждый ориентированный цикл содержит хотя бы одно ребро из этого подмножества.

(b)

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

(c)

Для данных целых чисел $a_{1}, a_{2}, \ldots , a_{n}, b_{1}, b_{2}, \ldots , b_{n}, s$ и $t$ найти $x_{1}, x_{2}, \ldots$ , $x_{n} \in \left\{ 0,1\right\}$ , максимизирующие значение $x_{1}+x_{2}+\cdots +x_{n}$ , при следующих ограничениях:

\begin{aligned} a_{1} x_{1}+a_{2} x_{2}+\cdots +a_{n} x_{n} & \leq s, \\ b_{1} x_{1}+b_{2} x_{2}+\cdots +b_{n} x_{n} & \leq t. \end{aligned}

(d)

Для данного графа найти колесо максимального размера. (Колесо размера $k$ — это подграф из $k+1$ вершин, в котором $k$ вершин образуют простой цикл, а оставшаяся вершина соединена со всеми этими $k$ вершинами.)

Задача 7.5.3

(a)(b)(c)(d)

Покажите, что для каждой из следующих задач оптимизации II существует коэффициент приближения $r>1$ такой, что $r$ -Approx- $\Pi$ является $N P$ -полной.

?

(a)

Network SMT: для данного графа $G=(V, E)$ , функции веса рёбер $w: E \rightarrow \mathrm{~ N}$ и подмножества $P \subseteq V$ найти связный подграф с минимальным суммарным весом рёбер, соединяющий вершины из $P$ .

(b)

Connected-VC: для данного графа $G$ найти минимальное вершинное покрытие $C$ такое, что подграф $\left.G\right|_{C}$ , порождённый $C$ , связен.

(c)

$\mathrm{TSP}$ with Triangle Inequality: для данного полного графа $G$ и функции расстояния $d: E \rightarrow \mathrm{~ N}$ , удовлетворяющей неравенству треугольника, найти гамильтонов цикл с минимальным суммарным расстоянием. (Функция расстояния $d: E \rightarrow \mathbf{N}$ удовлетворяет неравенству треугольника, если $d(\left\{ a, b\right\} )+d(\left\{ b, c\right\} ) \geq d(\left\{ a, c\right\} )$ для любых трёх вершин $a, b, c$ .)

(d)

$\mathrm{TSP}$ with $(1,2)$ -Distance: для данного полного графа $G$ и функции веса рёбер $d: E \rightarrow \left\{ 1,2\right\}$ найти гамильтонов цикл с минимальным суммарным расстоянием.

Задача 7.5.4

(a)(b)(c)

Для графа $G$ его рёберно-квадратный граф $G^{2}$ — это граф, полученный из $G$ заменой каждого ребра $\left\{ u, v\right\}$ на копию $G$ , называемую $G_{u, v}$ , и соединением как $u$ , так и $v$ с каждой вершиной в $G_{u, v}$ .

?

(a)

Покажите, что $r$ -Approx- $\mathrm{LP}$ является NP-полной для некоторого $r>1$ .

(b)

Покажите, что если самый длинный простой путь в $G$ имеет длину $\ell$ , то самый длинный простой путь в $G^{2}$ имеет длину не менее $\ell^{2}$ . Более того, по данному пути длины $m$ в $G^{2}$ путь длины $\sqrt{m}-1$ в $G$ можно найти за полиномиальное время.

(c)

Покажите, что $r$ -Approx- $\mathrm{LP}$ является NP-полной для всех $r>1$ .

Задача 7.5.5

(a)(b)

Покажите, что для каждой из следующих задач оптимизации $\Pi$ существует константа $\varepsilon >0$ такая, что $n^{\varepsilon }$ -Approx- $\Pi$ является $N P$ -полной.

?

(a)

Раскраска вершин: для данного графа $G=(V, E)$ найти раскраску $V$ (т.е. функцию $c: V \rightarrow \left\{ 1,2, \ldots , m\right\}$ ) с минимальным числом $m$ цветов такую, что никакие две смежные вершины не имеют одинакового цвета.

(b)

Раскраска рёбер: для данного графа $G=(V, E)$ найти раскраску $E$ (т.е. функцию $c: E \rightarrow \left\{ 1,2, \ldots , m\right\}$ ) с минимальным числом $m$ цветов такую, что никакие два смежных ребра (рёбра с общей вершиной) не имеют одинакового цвета.

NP-полные задачи оптимизации