Какова сложность этой проблемы пути?

Экземпляр: неориентированный граф с двумя выделенными вершинами s ≠ t и целым числом k ≥ 2 .$G$$s\neq t$$k\geq 2$

Вопрос: существует ли путь в G , такой, что путь касается не более k вершин? (Вершина затрагивается путем, если вершина находится либо на пути, либо имеет соседа на пути.)$s-t$$G$$k$

Эта проблема была изучена в:

Шири Чечик, Мэтью П. Джонсон, Мерав Партер, Дэвид Пелег: уединенные проблемы с подключением. ЕКА 2013: 301-312.

http://arxiv.org/pdf/1212.6176v1.pdf

Они назвали это проблемой уединенного пути. Это действительно NP-сложный, и версия оптимизации не имеет приближения с постоянным множителем.

Мотивация, которую обеспечивают авторы, - это настройка, в которой информация отправляется по пути, и ее могут видеть только соседи и узлы в пути. Цель состоит в том, чтобы минимизировать воздействие.

Изменить: Пожалуйста, смотрите ответ user20655 ниже для ссылки на документ, уже доказывающий серьезность этой проблемы. Я оставлю свой исходный пост на тот случай, если кто-нибудь захочет увидеть это альтернативное доказательство.

===============

$X = \{x_1, x_2, \cdots\, x_n\}$$C = \{c_1, c_2, c_3, \cdots\}$

$x_i$$c_i$$m = 2n+|C|$$m$$p_1, p_2, \cdots, p_{m}$

$s$$t$$x_i$$\bar{x_i}$$c_j$$p_i$$c_j$

$x_i$$c_j$$x_i$$\overline{x_i}$$c_j$$\overline{x_i}$$x_i$$\overline{x_i}$$x_{i+1}$$\overline{x_{i+1}}$$s$$x_1$$\overline{x_1}$$t$$x_n$$\overline{x_n}$$c_i$$p_j$

$\{P_i\}$$c_j$$c_j$

$Q + 2n + 2$$Q$

1. $s$$t$$y_i \in \{x_i, \overline{x_i}\}$$y_{i+1} \in \{x_{i+1}, \overline{x_{i+1}}\}$$x_i$$\overline{x_i}$$i \in 1, \cdots, n$(это интуитивно понятно, так как удаление одного из двух параметров из любой выбранной переменной дважды приводит к правильному пути со стоимостью, не превышающей ту, в которой мы оба держали).
2. $m+2$$s, x_1, x_2, \cdots, x_n, t$$s$$t$$\{x_i\}$$\{\overline{x_i}\}$$\{c_i\}$ $s-t$$s$$t$$c_i$$x_i$$x_j$$\{p\}$$\geq m+5$
3. $s$$t$$c_j$$c_j$$Q$$Q$$c_j$
4. $x_i$$\overline{x_i}$$s$$t$$2n + 2$$c_i$$Q$

$\leq k$$\leq k + 2n + 2$