algorithmic problem

[gusl]

Given a set L of permutations of a list, compute the maximal partial order (DAG) under which all lists in L are topological sorts. How would you do this? Can you do better than O(m n^2 k^2)? (m = number of lists in L, k = # of things in domain = the size of the elements of L)
Sounds like an ILP problem.

One idea: whenever a cycle is detected, all the elements are deemed incomparable.

Comments

[rdore.livejournal.com]

Oh ok. Well suppressing log factors, I think the complexity is O(mk+k²). Make a graph on the k objects by throwing in all the consecutive pairs from all the lists. This is O(mk). Then detect all the strongly connected components - O(k²). Remove the edges of the strongly connected components - O(k²). Then take the transitive closure - I think this is O(k²) at least for a DAG, not sure.