Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while respecting prerequisites.

Equivalently: suppose I have a dag $G=(V,E)$, and a positive integer $k$. The desired output is a sequence $S_1,\dots,S_m$ of vertices that minimizes $m$, subject to the constraint that $S_1 \cup \dots \cup S_m = V$, $|S_i| \le k$ for all $k$, and every edge goes from some set $S_i$ to $S_j$ where $i<j$ (i.e., there is no edge $v \to w$ where $v\in S_i$, $w\in S_j$, and $i \ge j$).

Is there a polynomial-time algorithm for this problem?

Approaches I've considered:

The obvious greedy strategy is a variant of Kahn's algorithm is: in each semester, arbitrarily pick $k$ courses whose prerequisites have all been previously taken, and take those $k$ courses. Unfortunately, this algorithm is not guaranteed to generate an optimal schedule. For example, in the graph with vertices $v_1,v_2,v_3,v_4$ and the single edge $v_1 \to v_2$, with $k=2$ this algorithm might generate the schedule $\{v_3,v_4\},\{v_1\},\{v_2\}$, which is longer than the optimal schedule $\{v_1,v_3\},\{v_2,v_4\}$.

The next natural idea is to modify the above approach by breaking ties in favor of vertices that are part of longer dependency chains. I'm not sure whether this works or not.

Inspired by taking school courses efficiently.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.