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

1

I don't think the proposed greed algorithm works. Consider the following sequence of DAGs:

$G_1 = (\{1,2,3,4\},\{(1,2), (3,4)\})$

$G_2 = (\{1,2,3,4\},\{(2,3), (4,1)\})$

$G_3 = (\{1,2,3,4\},\{(3,2)\})$

Clearly every arc of $G_1$ will always be part of the solution. Note that, when considering $G_2$, it won't be possible to pick both arcs. If the algorithm picks the arc $(2,3)$ the solution will be suboptimal. On the other hand, if it picks $(4,1)$ instead, it will also be able to pick $(3,2)$ in the next iteration. Hence, the algorithm has to consider the future when deciding which arc to add to the solution. Actually, I'm not even sure if the problem can be solved efficiently.

  • 1
    As I said, I'm not sure the problem can be solved efficiently. It wouldn't surprise me if it's NP-hard.2012-10-15