Les puzzles «sans flux» sont-ils durs en NP?

Un puzzle "Flow Free" se compose d'un entier positif et d'un ensemble de paires (non ordonnées) de sommets distincts dans le graphique de grille sorte que chaque sommet se trouve dans au plus une paire. Une solution à un tel casse-tête est un ensemble de chemins non orientés dans le graphique de sorte que chaque sommet se trouve exactement dans un chemin et que chaque extrémité de chemin soit l'une des paires de sommets du casse-tête. Cette image est un exemple de puzzle Flow Free et cette image est un exemple de solution à un autre puzzle Flow Free.$n$$n \times n$

Le problème "Existe-t-il une solution à ce puzzle Flow Free?" NP-dur? Est-il important que soit donné en unaire ou binaire?$n$

Dans la terminologie de Nikoli Puzzles, cela s'appelle "Nanbarinku" ou "Numberlink". La description ne mentionne pas toujours explicitement que tous les carrés doivent être couverts, mais c'est bien le cas dans toutes les solutions que j'ai vérifiées.

Selon Wikipedia Numberlink, le problème est NP complet, avec référence: Kotsuma, Kouichi; Takenaga, Yasuhiko (mars 2010), NP-Completeness and Enumeration of Number Link Puzzle, rapport technique IEICE. Fondements théoriques de l'informatique 109 (465): 1–7

Je n'ai pas vérifié les petits caractères.

Ajoutée. Suite à un commentaire de domotorp , Numberlink a généralement une contrainte supplémentaire. En effet, citant Adcock et al:

Notre résultat de dureté peut être comparé à deux précédentes épreuves de dureté NP: l'épreuve de Lynch de 1975 sans la contrainte «couvrir tous les sommets» et la preuve de Kotsuma et Takenaga de 2010 lorsque les chemins sont restreints pour avoir le moins de coins possibles dans leur classe d'homotopie.

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