¿Encontrar una asignación de cursos a días para que ningún estudiante tiene más de un examen el mismo día es NP-completo?

Question

Dada una lista de$N$ cursos,$M$ estudiantes, la lista de cursos que cada estudiante está tomando y un número entero$K$ que representa la duración de la fase de examen, ¿hay un calendario de exámenes que conste de$K$ fechas para que no haya conflictos? ¿Puedes demostrar que este problema es tan difícil como el problema de Clique-Cover (es$NP$ - complete)?

Answer 1

Deje que los cursos sean vértices. Dibuje una ventaja entre dos si esos cursos no tienen un estudiante en común, es decir, sus exámenes pueden programarse al mismo tiempo. Si resulta ser un$3$ - camarilla, entonces todos$3$ de esos cursos pueden tener sus exámenes al mismo tiempo.