Пазлы “Flow Free” NP-сложны?

15

Головоломка «Поток свободен» состоит из натурального числа и набора (неупорядоченных) пар различных вершин в графе сетки , так что каждая вершина находится не более чем в одной паре. Решением такой головоломки является набор неориентированных путей в графе, так что каждая вершина находится на одном пути, а множество концов каждого пути является одной из пар вершин головоломки. Это изображение является примером головоломки Flow Free, и это изображение является примером решения другой головоломки Flow Free.n × nnn×n

Является ли проблема "Существует ли решение этой головоломки Flow Free?" NP-трудной? Имеет ли значение в одинарном или двоичном виде?n

Юхо
источник
Конечно, хитрое ограничение охватывает все квадраты; в противном случае задача была бы разрешима алгоритмом полиномиального времени для непересекающейся вершины задачи Менгера.
Дэвид Эйзенстат

Ответы:

5

В терминологии « Пазлы Николи» это называется «Nanbarinku» или «Numberlink». В описании не всегда явно упоминаются все квадраты, которые должны быть покрыты, но это действительно так во всех проверенных мной решениях.

Согласно Wikipedia Numberlink, проблема в NP завершена, со ссылкой: Коцума, Куичи; Такенага, Ясухико (март 2010 г.), NP-Полнота и перечисление головоломки номерной ссылки, технический отчет IEICE. Теоретические основы вычислительной техники 109 (465): 1–7

Я не проверял мелкий шрифт.

Добавлен. После комментария от domotorp , Numberlink обычно имеет дополнительное ограничение. Действительно, цитата из Adcock etal:

Наш результат твердости можно сравнить с двумя предыдущими доказательствами твердости NP: доказательство Линча 1975 года без ограничения «покрыть все вершины» и доказательство Коцума и Такенага 2010 года, когда пути ограничены, чтобы иметь наименьшее количество возможных углов в своем гомотопическом классе.

Adcock et al. Zig-Zag Numberlink является NP-Complete, Журнал обработки информации 23 (2015) 239-245, doi: 10.2197 / ipsjjip.23.239

Хендрик Ян
источник
Это имеет дополнительное ограничение, для проблемы OP, см. Doi.org/10.2197/ipsjjip.23.239 .
Domotorp
@domotorp Спасибо! Я скопировал вашу информацию в исходный ответ.
Хендрик янв
Интересно, что планарность графа с фиксированными координатами находится в P, но добавление пространства сетки делает его NP-трудным. Даже для двудольного графа.
rus9384