¿Son los rompecabezas “Flow Free” NP-hard?

Un rompecabezas "Flow Free" consiste en un entero positivo y un conjunto de pares (desordenados) de vértices distintos en el gráfico de cuadrícula n × n , de modo que cada vértice esté en un par como máximo. Una solución para tal rompecabezas es un conjunto de rutas no dirigidas en el gráfico de manera que cada vértice esté exactamente en una ruta y el conjunto de extremos de cada ruta sea uno de los pares de vértices del rompecabezas. Esta imagen es un ejemplo de un rompecabezas Flow Free, y esta imagen es un ejemplo de una solución a un rompecabezas Flow Free diferente.$n$$n \times n$

¿Es el problema "Existe una solución para este rompecabezas de Flow Free?" NP-hard? ¿Importa si se da en unario o binario?$n$

En la terminología de Nikoli Puzzles, esto se conoce como "Nanbarinku" o "Numberlink". La descripción no siempre menciona explícitamente que todos los cuadrados deben ser cubiertos, pero este es el caso en todas las soluciones que verifiqué.

Según Wikipedia Numberlink, el problema es NP completo, con referencia: Kotsuma, Kouichi; Takenaga, Yasuhiko (marzo de 2010), NP-Completeness and Enumeration of Number Link Puzzle, informe técnico de IEICE. Fundamentos teóricos de la informática 109 (465): 1–7

No revisé la letra pequeña.

Adicional. Después de un comentario de domotorp , Numberlink generalmente tiene una restricción adicional. De hecho, citando de Adcock etal:

Nuestro resultado de dureza se puede comparar con dos pruebas de dureza NP anteriores: la prueba de Lynch de 1975 sin la restricción de "cubrir todos los vértices" y la prueba de Kotsuma y Takenaga de 2010 cuando las rutas están restringidas para tener la menor cantidad posible de esquinas dentro de su clase de homotopía.

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