When does a graph admit an orientation in which there is at most one s-t walk? Consider the following problem:

Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (directed) $s$-$t$ walk?

This can be equivalently phrased as:

Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an acyclic orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (directed) $s$-$t$ path?

What is the class of graphs for which the answer is &quot;yes&quot;? Can this problem be solved in polynomial time?

Some observations:

If the graph is bipartite, then the answer is &quot;yes.&quot;
If the graph has a triangle, then the answer is &quot;no.&quot;

The first observation follows by orienting the edges from one partition to the other. The second observation is easy to check. This led me to two incorrect guesses:

The answer is &quot;yes&quot; if and only if the graph is bipartite. (counterexample: the 5-cycle)
The answer is &quot;yes&quot; if and only if the graph is triangle-free (counterexample: the cartesian product of an edge with the 5-cycle)
It's NP-complete by a reduction from not-all-equal-3SAT. To see this, observe that


The only valid orientation of a $4$-cycle is one in which the edges alternate orientations.
Let $P$ be a three-edge undirected path, and add a degree-two vertex adjacent to the endpoints of $P$ to form a $5$-cycle. Then the only orientations of $P$ that can be extended to valid orientations of the entire $5$-cycle are the ones in which $P$ is not consistently oriented as a directed path.


We form a variable gadget for a variable $v$ that belongs to $k$ different clauses of the NAE-3SAT instance, by gluing together $k$ shared $4$-cycles on a shared edge. Then in each of the $4$-cycles, the opposite edge to the shared edge has to be oriented consistently with all of the other $4$-cycles. We will associate the truth value of the variable with this consistent orientation of these edges. Additionally, in any valid orientation of each of these $4$-cycles, there is no path from one $4$-cycle into another $4$-cycle, so these gadgets can interact with each other only in the orientation of their edges and not through the existence of longer paths.

We form a clause gadget for a 3-variable clause of the NAE-3SAT instance by gluing together three of $4$-cycle edges, opposite the shared edges of the appropriate three variable gadgets, into a 3-edge path $P$ and then adding a degree-two vertex to complete $P$ into a $5$-cycle. As discussed above, this $5$-cycle can be consistently oriented if and only if its three edges are not all oriented as a directed path, which (when glued correctly) is true if and only if the truth values associated with these orientations are not all equal.

By the way, DAGS with at most one $s$-$t$ walk for each $s$-$t$ pair have been studied previously, as "multitrees", "strongly unambiguous graphs", or "mangroves"; see https://en.wikipedia.org/wiki/Multitree