2
$\begingroup$

I have a sequence of directed acyclic graphs, $G_i$. The union of their edge sets may not be a DAG. I want to find an edge set that is maximal in some sense but still acyclic.

Alternatively I have a sequence of inconsistent partial orders would like like to find a linear ordering that is maximal in some sense. (I will eventually do a topological sort on the DAG described above).

I want to merge these graphs so that the result

  1. is still acyclic
  2. contains as many edges as possible from the graphs that occur earlier in the sequence. It is better to add one edge from graph $G_2$ even if that edge stops us from adding 100 edges from $G_3$.

An algorithm to solve this problem might be the following

Start with no edges  for each graph Gi     for each edge in Gi         if adding that edge does not cause a cycle             add it 

This contain a number of checks for cycles. Is there a method with lower complexity?

1 Answers 1