On the Complexity of Timetable and Multicommodity Flow Problems

TLDR

A very primitive version of Gotlieb’s timetable problem is shown to be NP‑complete, implying that all common timetable problems are NP‑complete. The study presents a polynomial‑time algorithm for binary‑teacher timetabling, proves existence of a meeting function when teachers and classes have no time constraints, and shows that the multicommodity integral flow problem is NP‑complete even with two commodities in both directed and undirected graphs.

Abstract

A very primitive version of Gotlieb’s timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multicommodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases.