5
$\begingroup$

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:

  1. $A$ and $B$ have no common ancestor(s) nor common descendant(s).
  2. $A$ and $B$ have common ancestor(s) but no common descendant(s). ($\land$ structure)
  3. $A$ and $B$ have no common ancestor(s) but do have common descendant(s). ($\lor$ structure)
  4. $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.

$\endgroup$
  • $\begingroup$ Hamiltonian Path is NP-complete on general digraphs, but not for DAGs. You can answer it using a DP that computes the critical path (longest path in a DAG), and checking whether that path has length $n$: choose any topological order and then compute, from last to first, the length of the longest path leaving the current vertex by adding 1 to the maximum of the already-computed solutions of its children. $\endgroup$ – j_random_hacker Apr 10 at 10:40
  • $\begingroup$ @j_random_hacker yes that's exactly my point. This problem should be easier because it's in a DAG, but I am not sure. $\endgroup$ – ryan Apr 10 at 14:02

Your Answer

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

Browse other questions tagged or ask your own question.