Il metodo più semplice è fare quello che dici, cioè X->Y, Y->Z.
Per evitare di visitare Z prima di Y basta marcarlo come non visitabile nel grafo da subito quando fai le visite da X->Y e smarcarlo una volta arrivato a Y.
Ho scoperto che non risolve il problema.
Guarda questo grafo
Ipotesi: la visita iniziale mi trova come cammino XY quello passante per A e non per B.
Se mi segno Z e mi trovo X->A->Y, poi trovo Y->A->Z e non è semplice.
Se mi segno tutti i vertici del cammino tra X e Y per non usarli, ovviamente non trovo il cammino tra X e Z perchè non ho a disposizione A.
Il problema di fondo è beccare il cammino X-B-Y, ma quello è casuale, dipende dalla visita e dagli ordini delle liste di adiacenza. So?
EDIT abbiano postato insieme. Il tuo W sarebbe il mio A (anche se in reatà Y è raggiungibile anche da B, che ho inserito appunto per citare il problema dell'ultima riga, ovvero trovare il "giusto" cammino verso Y)