Quando um gráfico admite uma orientação na qual há no máximo uma caminhada?

Considere o seguinte problema:

Entrada: um gráfico simples (não direcionado) .$G=(V,E)$

Pergunta: Existe uma orientação do satisfazendo a propriedade que, para cada s , t ∈ V existe no máximo um (dirigida) s - t caminhada?$G$$s,t \in V$$s$$t$

Isso pode ser equivalente a:

Entrada: um gráfico simples (não direcionado) .$G=(V,E)$

Pergunta: Existe uma orientação acíclica de satisfazendo a propriedade de que para cada s , t ∈ V existe no máximo um caminho (direcionado) s - t ?$G$$s,t \in V$$s$$t$

Qual é a classe de gráficos para a qual a resposta é "sim"? Esse problema pode ser resolvido em tempo polinomial?

Algumas observações:

1. Se o gráfico for bipartido, a resposta será "sim".
2. Se o gráfico tiver um triângulo, a resposta será "não".

A primeira observação segue orientando as arestas de uma partição para outra. A segunda observação é fácil de verificar. Isso me levou a duas suposições incorretas:

1. A resposta é "sim" se e somente se o gráfico for bipartido. (contraexemplo: o ciclo 5)
2. A resposta é "sim" se e somente se o gráfico estiver sem triângulo (contraexemplo: o produto cartesiano de uma aresta com o ciclo 5)

É NP-completo por uma redução do não-igual-3SAT. Para ver isso, observe que

• $4$
• $P$$P$$5$$P$$5$$P$

$v$$k$$k$$4$$4$$4$$4$$4$$4$-ciclo, para que esses gadgets possam interagir entre si apenas na orientação de suas bordas e não através da existência de caminhos mais longos.

$4$$P$$P$$5$$5$

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