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

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

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

В терминологии « Пазлы Николи» это называется «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