9
$\begingroup$

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 "yes"? Can this problem be solved in polynomial time?


Some observations:

  1. If the graph is bipartite, then the answer is "yes."
  2. If the graph has a triangle, then the answer is "no."

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:

  1. The answer is "yes" if and only if the graph is bipartite. (counterexample: the 5-cycle)
  2. The answer is "yes" if and only if the graph is triangle-free (counterexample: the cartesian product of an edge with the 5-cycle)
$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! I had come across the multitree wiki before. It seems they are almost what I want. One difference is that I don't want the acyclic orientation of the triangle, but this is a multitree. $\endgroup$ – Austin Buchanan May 8 '15 at 5:16
  • $\begingroup$ I'd like to cite this. Would you prefer me to cite as per Suresh's answer here, or some other way? $\endgroup$ – Austin Buchanan May 8 '15 at 14:17
  • $\begingroup$ The method in Suresh's answer is fine. BTW, re multitrees: the acyclic order of a triangle is ok if you're thinking of it as the binary relation of an N-free partial order, but not for the DAG version of the definition, because the DAGs are supposed to be transitively reduced and the acyclic triangle isn't. So I think that multitrees (as DAGs) really are the same thing as in your question. $\endgroup$ – David Eppstein May 8 '15 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.