Topological sort with alternative choices of predecessors

Question

I have a family of directed graphs over the same set of nodes $V$ defined as follows.

Each node $v \in V$ has $k_v$ alternative choices for its set of predecessors. In other words, I am given a relation $\rho\colon V \to 2^{V}$ such that $|\rho(v)| = k_v$ (where $\rho(v) = \{S \subset V \mid (v, S) \in \rho\}$, I'm abusing the relation notation a little bit). This relation induces a family of graphs: if we pick one predecessor set $S_v \in \rho(v)$ for each $v$, we obtain a fixed set of edges $E = \{ (u, v) \mid u \in S_v \}$ for the entire graph.

There are $\prod\limits_{v \in V} k_v$ such possible graphs, some of them are acyclic, some are not. I want to find at least one acyclic graph among these possibilities, and sort it topologically. Can it be done in polynomial time (i.e., faster than enumerating all possible combinations of choices explicitly)?

(As an illustrative application, imagine a package manager where some packages depend on either one of these other packages, because they all provide similar capabilities.)

Answer 1

Yes, a valid ordering and a graph that goes with it can be found in polynomial time. I think it's easier to understand this if you look for the topological ordering first, and the graph second.

What you are trying to find is an ordering of the vertices with the property that, for each vertex $v$, at least one of its predecessor sets appears in its entirety before $v$. This can easily be found by a greedy algorithm if it exists:

Initialize an empty ordering and then, while the ordering does not include all of the vertices:

• Find a vertex $v$ such that one of the predecessor sets of $v$ has already been included in the ordering

• Add $v$ to the end of the ordering

If this succeeds, you have found your topological ordering, and you can choose the graph to be the one that connects each $v$ to its previously-appearing predecessor set. If it fails, then you have found a subset $S$ of vertices (the ones not yet added) so that every predecessor set of a vertex in $S$ contains another vertex in $S$, blocking any solution from existing.

Incidentally, the class of valid orderings for a problem of this type form an antimatroid, and all antimatroids can be represented in this way. This idea that you might have more than one way of satisfying the prerequisites for an object but that, once satisfied, a vertex can never become un-satisfied, is the defining principle of an antimatroid.