Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Is there a name/algorithm for this problem related to set cover and CSP?

, ,
Problem Detail:

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?

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.