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

Пример 7.43

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

?

Пример 7.46

TSP является NP-полной.

?

Пример 7.47

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

?

Пример 7.49

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

?

Пример 7.51

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

?

Пример 7.52

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

?

Задача 7.5.1

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

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

?

(a)

Max-3Sat.

(b)

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

(c)

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$ является $\mathrm{NP}$ -полной.

?

(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)

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)

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-LP является NP-полной для некоторого $r>1$ .

(b)

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

(c)

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

Задача 7.5.5

(a)(b)

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

?

(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-полные задачи оптимизации