how to sort a set when elements have multiple relationships with each other

Question

I'm looking for an algorithm to perform some kind of extended array sorting when relationships between elements can contradict each other.

so we have a set I (items) consisting of n items i1...in

There is a set R (relationships) consisting of m relationships defined between items in I

the relationships can contradict each other so that, e.g., one relationship says that A>B and the other that A<B.

e.g.

r1:i1<i35

r2:i100<i4

...

rm:i45>i3

generally, r and m (sizes of sets) can be any positive integers.

the task is to sort I so the items go in such a way that preferably the lower ones (based on relationships) go before higher ones...

I'm looking for an algorithm which will sort the set so that it is as close to the "optimal" order as possible. I guess there must be a well known algorithm to solve problems like this.

Thanks!

Answer 1

I think the most sensible way to measure the quality of a particular ordering is the number of given relationships that it violates. If you decide to use this measure, then the problem is equivalent to (Minimum) Feedback Arc Set. Unfortunately, this problem is NP-hard, so no efficient (polynomial-time) algorithm is likely to exist.

In the Feedback Arc Set problem, you are given a directed graph, and asked to find a minimum-size set of edges which, if deleted, would destroy all cycles in the graph.

To see how this corresponds to your problem, observe that we can represent each item as a vertex in a graph, and each relationship as a directed edge between two vertices (pointing to, say, the smaller one). There is a conflict if and only if there is a cycle in this graph -- that is, if there is an ordered list of 2 or more distinct vertices v_1, v_2, ..., v_k such that v_i < v_(i+1) for all i < k, and also v_k < v_1. It is impossible to order these k vertices without violating at least one constraint. Conversely, if no cycle exists -- that is, if the graph is a directed acyclic graph -- then topological sort can quickly (in linear time) find a valid order that violates no constraints. Thus the size of a feedback arc set is the smallest number of edges that you would need to remove in order to obtain a graph that can be ordered without violating any constraint -- or equivalently, the smallest number of edges that must be violated in any ordering.