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

15

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.nn×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

Juho
źródło
Z pewnością trudnym ograniczeniem jest pokrycie wszystkich kwadratów; w przeciwnym razie problem zostałby rozwiązany przez algorytm wielomianowy dla problemu Mengera z rozłącznym wierzchołkiem.
David Eisenstat

Odpowiedzi:

5

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

Hendrik Jan
źródło
Ma to dodatkowe ograniczenie, dotyczące problemu PO patrz doi.org/10.2197/ipsjjip.23.239 .
domotorp
@domotorp Thanks! Skopiowałem twoje informacje do oryginalnej odpowiedzi.
Hendrik Jan
Interesujące jest to, że płaskość wykresu ze stałymi współrzędnymi jest w P, ale dodanie przestrzeni siatki sprawia, że ​​NP-trudne. Nawet dla grafu dwustronnego.
rus9384