Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a circular permutation like this for every possible pair. Of course, if the two points are neighbours on the circle, there would be one set containing all other points except that pair. It is like the numbers on a watch, if you choose 9 and 12 as the pair, the other numbers will be in two sets, depending on which side of the chosen pair: {10,11} and {1,2,3,4,5,6,7,8} So, we would know who the neighbours are by looking at partitions if we had the full partition info for all pairs. However, lets say that we have partial information about the partitions for all pairs.
For every pair, we have a few sets of points. The points in the same set are known to be on the same side if we draw a line connecting the given pair. In our info, there can be more than two sets with many missing points for a pair. This only means the points in the same set will be on the same side, and some of them will merge in the full known case, because there are two sides for a pair, one if they are neighbours. For example, the given sets for (9,12) pair above could be :{1,2} and {6,8,5}. Also, there are no single point sets, there are at least two points in each set.The number of points missing from the sets varies for pairs, but half of the total is missing. The question is:
Can we construct the circular permutation from partial partitions for all pairs, if yes, how?
This can be formulated as a constraint satisfaction problem, but I want to know if the constraint structure here makes it tractable or still NP-complete?
Also, I could not find the name of this particular set of partitions for all pairs after looking at some combinatorics books and chatbots. I would also appreciate if you direct me to a source that has this problem setting and hopefully a solution.
