Add Lemma Restrictions

[MvKaio]

Bira and Perchuts commented about the following lemma:

If v and u are vertices of B (the partition we want to order) and the rightmost neighbor of v is to the left of the leftmost neighbor of u, then v comes before u in every optimal ordering.

This lemma can be used in the IP Solver to reduce variables.

[MvKaio]

I believe is useful to write a function that, given the instance graph, returns a list of every pair of vertices u and v that satisfy the lemma. Are you interested in writing it @lailamvl ? If you're looking into other things it is fine.

One way of writing this function is computing the intervals [l, r] of the neighborhoods and identifying which pairs do not overlap. This second part can be done with two for loops, or sorting the intervals in non-decreasing order of r; and then the good pairs for each vertex will form a prefix. The assimptotic complexity is the same, but if there are few good pairs the second option should be faster. I'm also open to discussions about it and think that similar routines will be used in the FPT algorithms.

@perchuts Can you point to the lemma here? I believe its pdf is already in the repository?

[lailamvl]

yes, i can do it

[luishgh]

This was implemented in the integration of the IP and the Crossing Matrix class and in #24 👍