Is there a name/algorithm for this problem related to set cover and CSP? 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?
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) &amp;= \min\{|\mathcal{M}(c)|,2\} \qquad &amp;\text{(every class covers at most 2 requirements)}\\
\text{cap}(g,t) &amp;= 1\\
\text{cap}(c,g) &amp;= 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.