I puzzle "liberi da flusso" sono np-hard?

Question

Un puzzle "Flow Free" è costituito da un numero intero positivo $ n $ e una serie di coppie (non ordinate) di vertici distinti nei $ n tempi n $ grafico della griglia in modo tale che ogni vertice sia al massimo una coppia. Una soluzione a un tale puzzle è un insieme di indiretti percorsi Nel grafico in modo tale che ogni vertice sia esattamente in un percorso e il set di estremità di ogni percorso è una delle coppie di vertici del puzzle. Questa immagine è un esempio di un puzzle senza flusso e questa immagine è un esempio di soluzione a un puzzle diverso dal flusso.

Il problema è "esiste una soluzione a questo puzzle senza flusso?" NP-Hard? Importa se $ n $ sia dato in unario o binario?