070-2015

MO640 - Multiple-choice question

To test for the C1P on a connected component of the strict overlap graph, we need to keep a linear order (called Path in the figure below) of twin classes, and update the structure with each new set added.

Suppose that a certain number of sets have been processed, with the C1P being satisfied so far, and  arriving at the structure shown below.



When adding a new set S, the current classes can be classified into three categories:

•  empty (no elements in common with S),
•  full (contained in S), or
•  partial (some, but not all, ements contained in S).

 Adding set S = {3, 4, 8, 9} to this data structure: 

1. ... the C1P would be destroyed because there is a twin class of new elements but not a suitable extremity in the path to place it.
2. ... the C1P would still hold true.
3. ... the C1P would be destroyed because some class is partial and there is no empty neighbour or free extremity to place the subclass disjoint from S.
4. ... the C1P would be destroyed because the updated classes contained in S do not form a consecutive block.
5. None of the above.

Original idea by: Celso A. W. Santos