¿Cuándo admite un gráfico una orientación en la que hay como máximo una primera caminata?

Considere el siguiente problema:

Entrada: un gráfico simple (no dirigido) .$G=(V,E)$

Pregunta: ¿Existe una orientación de satisfaga la propiedad de que para cada s , t ∈ V hay a lo sumo una s - t walk (dirigida) ?$G$$s,t \in V$$s$$t$

Esto puede expresarse de manera equivalente como:

Entrada: un gráfico simple (no dirigido) .$G=(V,E)$

Pregunta: ¿Existe una orientación acíclica de satisfaga la propiedad de que para cada s , t ∈ V hay a lo sumo una ruta s - t (dirigida) ?$G$$s,t \in V$$s$$t$

¿Cuál es la clase de gráficos para los cuales la respuesta es "sí"? ¿Se puede resolver este problema en tiempo polinómico?

Algunas observaciones

1. Si el gráfico es bipartito, la respuesta es "sí".
2. Si la gráfica tiene un triángulo, entonces la respuesta es "no".

La primera observación sigue orientando los bordes de una partición a la otra. La segunda observación es fácil de verificar. Esto me llevó a dos conjeturas incorrectas:

1. La respuesta es "sí" si y solo si el gráfico es bipartito. (contraejemplo: el ciclo 5)
2. La respuesta es "sí" si y solo si la gráfica no tiene triángulos (contraejemplo: el producto cartesiano de una arista con el ciclo 5)

Es NP-completo por una reducción de no-todo-igual-3SAT. Para ver esto, observe que

• $4$ ciclo es aquella en la que los bordes alternan las orientaciones.
• $P$$P$$5$$P$$5$$P$

$v$$k$$k$$4$$4$$4$$4$$4$$4$-ciclo, por lo que estos gadgets pueden interactuar entre sí solo en la orientación de sus bordes y no a través de la existencia de rutas más largas.

$4$$P$$P$$5$$5$ ciclo de puede orientarse de manera consistente si y solo si sus tres bordes no están todos orientados como una ruta dirigida, lo cual (cuando está pegado correctamente) es verdadero si y solo si los valores de verdad asociados con estas orientaciones no son todos igual.

$s$$t$$s$$t$