Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 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.

share|improve this answer
    
Granted. The greedy algorithm I posed does not find the optimal solution. What could be done to improve upon it? –  MRocklin Oct 15 '12 at 19:50
1  
As I said, I'm not sure the problem can be solved efficiently. It wouldn't surprise me if it's NP-hard. –  Vinicius dos Santos Oct 15 '12 at 19:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.