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
- is still acyclic
- 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?