Sind "Flow Free" -Rätsel NP-schwer?

Ein "Flow Free" -Puzzlespiel besteht aus einer positiven ganzen Zahl und einer Reihe von (ungeordneten) Paaren unterschiedlicher Eckpunkte im Gitterdiagramm sodass sich jeder Eckpunkt in höchstens einem Paar befindet. Eine Lösung für ein solches Puzzle ist eine Reihe ungerichteter Pfade in der Grafik, sodass sich jeder Scheitelpunkt auf genau einem Pfad befindet und die Endmenge jedes Pfads eines der Scheitelpunktpaare des Puzzles ist. Dieses Bild ist ein Beispiel für ein Flow Free-Puzzle, und dieses Bild ist ein Beispiel für eine Lösung für ein anderes Flow Free-Puzzle. $n$ $n \times n$

Ist das Problem "Gibt es eine Lösung für dieses Flow Free-Puzzle?" NP-schwer? Ist es wichtig, ob unär oder binär angegeben wird? $n$

np-hard square-grid Juho
quelle

Sicherlich deckt die schwierige Einschränkung alle Quadrate ab. Andernfalls wäre das Problem durch einen Polynom-Zeit-Algorithmus für das vertex-disjunkte Menger-Problem lösbar.

David Eisenstat

Antworten:

In der Terminologie von Nikoli Puzzles ist dies als "Nanbarinku" oder "Numberlink" bekannt. In der Beschreibung wird nicht immer explizit erwähnt, dass alle Quadrate abgedeckt werden müssen, dies ist jedoch in der Tat bei allen von mir überprüften Lösungen der Fall.

Laut Wikipedia Numberlink ist das Problem NP vollständig, mit Verweis: Kotsuma, Kouichi; Takenaga, Yasuhiko (März 2010), NP-Vollständigkeit und Aufzählung von Zahlenverknüpfungsrätseln, IEICE-Fachbericht. Theoretische Grundlagen von Computing 109 (465): 1–7

Ich habe das Kleingedruckte nicht überprüft.

Hinzugefügt. Nach einem Kommentar von domotorp hat Numberlink normalerweise eine zusätzliche Einschränkung. In der Tat zitiert Adcock et al:

Unser Härteergebnis kann mit zwei früheren NP-Härteprüfungen verglichen werden: Lynchs Prüfung von 1975 ohne die Einschränkung „Alle Scheitelpunkte abdecken“ und Kotsumas und Takenagas Prüfung von 2010, wenn die Pfade auf möglichst wenige Ecken innerhalb ihrer Homotopieklasse beschränkt sind.

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

Hendrik Jan
quelle

Dies hat eine zusätzliche Einschränkung für das Problem des OP, siehe doi.org/10.2197/ipsjjip.23.239 .

Domotorp

@domotorp Danke! Ich habe Ihre Informationen in die ursprüngliche Antwort kopiert.

Hendrik Jan

Es ist interessant, dass die Planarität von Graphen mit festen Koordinaten in P liegt, aber das Hinzufügen von Rasterraum macht es NP-schwierig. Auch für zweigliedrige Graphen.

Rus9384