On the complexity of time table and multi-commodity flow problems

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 multi-commodity 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. Finally, the two commodity real flow problem in undirected graphs is shown to be solvable in polynomial time. The time bound is O(|v|2|E|).