2
$\begingroup$

Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy multiple graduation requirements (e.g., writing, quantitative literacy, and art), each class may only count for up to two graduation requirements for a single student. We wish to be able to determine the mapping of courses (within a given transcript) to graduation requirements that satisfies the most graduation requirements in order to see if a student can graduate, and, if not, what graduation requirements are unmet. I've tried writing this up semi-formally:

Given:

  • A set of graduation requirements $\cal G$.
  • A set of classes $\cal C$ offered at the college.
  • A map ${\cal M: C} \rightarrow 2^\cal G$ indicating which classes fulfill which requirements. A given class can fulfill anywhere from 0 to $|\cal G|$ requirements.
  • A set of classes $\cal T$ (for transcript) $\subseteq \cal C$.

Determine:

  • A set $\cal S$ of $(c, g)$ pairs, where $c \in \cal T, g \in \cal M(c)$ that maximizes coverage of $\cal G$ but contains no more than 2 pairs with the same $c$.

Is there a name and known algorithm to solve this problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ It's been decades since I took a theory course (or used TeX), so I realize my formalisms may be laughable (especially the last bullet point). Feel free to improve them and to mock me. :-) $\endgroup$
    – Ellen Spertus
    Commented Jan 15, 2016 at 18:23

2 Answers 2

Reset to default
3
$\begingroup$

This can be reduced to maximum bipartite matching.

Each left-side vertex represents a course. Each right-side vertex represents a requirement. Add an edge $c \to g$ if course $c$ satisfies requirement $g$. To deal with the fact that each course is allowed to be used satisfy at most 2 requirements (per course), we'll have two vertices for each course. In other words, we'll make two copies of each course, so the number of vertices on the left side is twice the number of courses.

Then, look for a maximum matching in this graph. The matching will tell you which requirements are covered and by which courses. You can use any standard algorithm for finding a maximum matching in a bipartite graph: a network flow based algorithm, or Hopcroft-Karp, or any other such algorithm.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you, although I don't see how this handles a c1 being able to satisfy requirements g1, g2, and g3, in general but only able to satisfy 2 for a given transcript. $\endgroup$
    – Ellen Spertus
    Commented Jan 15, 2016 at 20:59
  • $\begingroup$ This seems like a more straightforward solution than the flow network model. $\endgroup$
    – G. Bach
    Commented Jan 15, 2016 at 21:11
  • 1
    $\begingroup$ @espertus You make two copies of $c_1$, call them $c_1^{(1)}$ and $c_1^{(2)}$, and you connect both of them to $g_1, g_2, g_3$. For each copy of $c_1$, you can only pick at most one of the three requirements since you're looking for a matching, and so you satisfy a total of at most two requirements that $c_1$ covers since you only have two copies of $c_1$. $\endgroup$
    – G. Bach
    Commented Jan 15, 2016 at 21:14
  • $\begingroup$ Incidentally, you get something like the network I describe if you add a source and a sink to this bipartite graph along with the relevant unit-capacity edges. $\endgroup$
    – G. Bach
    Commented Jan 15, 2016 at 21:22
3
$\begingroup$

Just to be sure, I assume that $\mathcal{G}^* = 2^\mathcal{G}$, i.e. that $\mathcal{G}^*$ is the power set of $\mathcal{G}$.

Alright, we can use the following flow network $(V,E,\text{cap})$: let $V = \{s\} \uplus \mathcal{T} \uplus \mathcal{G} \uplus \{t\}$. Now let $E = \{(s, c) : c \in \mathcal{T}\} \uplus \{(g,t) : g \in \mathcal{G}\} \uplus \{(c,g) : c\in \mathcal{T} \wedge g \in \mathcal{G} \wedge g \in \mathcal{M}(c)\}$. Finally, we need capacity constraints:

\begin{align}\text{cap}(s,c) &= \min\{|\mathcal{M}(c)|,2\} \qquad &\text{(every class covers at most 2 requirements)}\\ \text{cap}(g,t) &= 1\\ \text{cap}(c,g) &= 1 \end{align}

Now we run maxflow to find an $s-t-$flow and we are done; while there may be fractional maximum flows, finding an integral one is easily done via an augmenting path algorithm (since all capacities are integral).

The problem reminds me of maximum matching, but I can't reduce it to matching off the cuff. Maybe some generalization, not sure.

Improve this answer
$\endgroup$
3
  • $\begingroup$ No, I misused G*. I meant that each C was mapped to one or more G. I apologize. I've edited my question. $\endgroup$
    – Ellen Spertus
    Commented Jan 15, 2016 at 20:51
  • $\begingroup$ Actually, I'm not sure if I misused it. I mean that M = {(c, g)} where c \in C, g \in G, and class c satisfies graduation requirement g. $\endgroup$
    – Ellen Spertus
    Commented Jan 15, 2016 at 21:00
  • $\begingroup$ @espertus If you mean that $\forall c \in \mathcal{C}: \mathcal{M}(c) \subseteq \mathcal{G}$, then you did use $\mathcal{G}^*$ as notation for the power set of $\mathcal{G}$ and this network will solve your problem. Going by your last comment, this is what you meant. $\endgroup$
    – G. Bach
    Commented Jan 15, 2016 at 21:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.