069-2015

MO640 - Multiple-choice question

When testing for the C1P on a connected component of the strict overlap graph, one startegy is to keep a linear order of twin classes for the sets already processed, and update this structure for each new set added.

Suppose a correct twin-class path for an already processed subfamily that has the C1P is as follows:

 

 Which of the following sets would violate the consecutive ones property if added?

1. {1, 3, 6, 7}
2. {2, 7}
3. {3, 4, 6}
4. {4, 5, 7, 8}
5. None of the above.

Original idea by: Juan Felipe Hernández Albarracín