Re: Disjoint pairs problem

Quote:

Originally Posted by

**lucav**
path coloring, arc coloring and interval scheduling

To me it looks like a set cover problem,

http://en.wikipedia.org/wiki/Set_cover_problem

There it says the optimal approximate strategy is to greedily select the largest set in each stage.

Translated to this problem it would mean to find the largest set of non-conflicting pairs and send them together in one round. This is then repeated until all pairs have been sent. The collection of largest sets will be mutually disjoint and together cover the total set of all pairs.

Each pair is associated with a set of non-conflicting other pairs. The task is to find the largest of these associated sets. It's quite easy to calculate how many members there are in such a set. From the total number of pairs, N, it's just to subtract the number of conflicting pairs (those with the same <from> or <to>). The <from> and <to> counts can be held in two look-up tables (one for <from> and one for <to>).

Setting up the look-up tables and walking through all pairs to select the pair with the largest associated set and then actually generate the largest set from the pair is O(N). The link above indicates this must be repeated log(N) times. That would result in a total complexity of O(N * logN) on average.