The question is simple:
Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has a unique topological ordering?
I initially approached this in a greedy way: determine the longest vertex-disjoint paths, then try to merge them head to tail. This seems to not work for parallel paths however, because we may break constraints imposed by the DAG. Since an equivalent goal is to impose a Hamiltonian Path on the graph, we could always use two or fewer edges to merge parallel paths such that we end up with one long path. Perhaps we could alternate between greedily merging longest paths in succession, then merging parallel paths and repeating. I'm not convinced this will be optimal however.
For any pair of unordered nodes $A$ and $B$ it seems we have the following 4 options:
- $A$ and $B$ have no common ancestor(s) nor common descendant(s).
- $A$ and $B$ have common ancestor(s) but no common descendant(s). ($\land$ structure)
- $A$ and $B$ have no common ancestor(s) but do have common descendant(s). ($\lor$ structure)
- $A$ and $B$ have common ancestor(s) and have common descendant(s). ($\diamond$ structure)
With this, my next idea would be to go through all pairs of unordered nodes and determine which of these 4 cases it falls into, then add an edge between the nodes that would decrease the set of unordered nodes by as much as possible. Would this greedy strategy work either? I cannot think of any edge cases that would prevent this from working, but a greedy proof of this also does not seem to work.
Is there a polynomial time algorithm to answer this question? If not, is there a reduction from an NP-complete (or NP-hard) problem?
Maybe a related question would be "Given an undirected graph $G$, what is the minimum number of edges needed to be added such that the resulting graph has a Hamiltonian Path?" However, this question seems implicitly more difficult because it's NP-complete just to determine if $G$ has a Hamiltonian path, so I would think the problem becomes easier in a DAG.