Czy łamigłówki „Flow free” są trudne NP?

Układanka „Flow Flow” składa się z dodatniej liczby całkowitej i zestawu (nieuporządkowanych) par odrębnych wierzchołków na wykresie siatki tak że każdy wierzchołek zawiera co najwyżej jedną parę. Rozwiązaniem takiej układanki jest zestaw niekierowanych ścieżek na wykresie, dzięki czemu każdy wierzchołek znajduje się dokładnie na jednej ścieżce, a zestaw końców każdej ścieżki jest jedną z par wierzchołków układanki. Ten obraz jest przykładem układanki Flow Flow, a ten obraz jest przykładem rozwiązania innej układanki Flow Flow.$n$$n \times n$

Czy problem „Czy istnieje rozwiązanie tej układanki Flow Free?” NP-twardy? Czy ma znaczenie to, czy podano w postaci jedno lub dwójkowej?$n$

W terminologii Nikoli Puzzles jest to znane jako „Nanbarinku” lub „Numberlink”. Opis nie zawsze wyraźnie wymienia wszystkie kwadraty, które muszą być pokryte, ale tak naprawdę jest w przypadku wszystkich sprawdzonych rozwiązań.

Według Wikipedii Numberlink problem jest NP kompletny, z odniesieniem: Kotsuma, Kouichi; Takenaga, Yasuhiko (marzec 2010), NP-Kompletność i wyliczenie łamigłówki numerycznej, raport techniczny IEICE. Teoretyczne podstawy obliczeń 109 (465): 1–7

Nie sprawdziłem drobnego druku.

Dodany. Po komentarzu od domotorp Numberlink zwykle ma dodatkowe ograniczenie. Rzeczywiście, cytując z Adcock etal:

Nasz wynik twardości można porównać do dwóch poprzednich prób twardości NP: dowód Lyncha z 1975 r. Bez ograniczenia „obejmujący wszystkie wierzchołki” oraz dowód Kotsuma i Takenaga z 2010 r., Gdy ścieżki są ograniczone, aby mieć jak najmniej zakrętów w klasie homotopii.

Adcock i in. Zig-Zag Numberlink jest NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi: 10.2197 / ipsjjip.23.239