A complexity analysis and an algorithmic approach to student sectioning in existing timetables

We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign $m$ students to $k$ sectioned courses with respect to a given timetable with $l$ timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in $O(k^2{l}^{2}log({\mathrm{sum}}_A))$ , where ${\mathrm{sum}}_A$ is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NP‐complete problem: