"Breadth course" problem – find maximum independent set given all maximal cliques One of the undergraduate degree requirements at my university is that all Letters and Science students must take a "breadth course" in each of seven categories. If a course has multiple associated categories, you have to pick one; you can't satisfy multiple breadth requirement categories with a single course. 

For example, while CHINESE 110A Introduction to Literary Chinese is both an "arts and literature" course and an "international studies" course, you can only use it for one of the two categories. If you then take COMLIT 156 Fiction and Culture of the Americas, which satisfies "arts and literature", you've now got both of the categories taken care of.

I'm trying to write a program that determines the maximum number of categories you can fulfill with a given set of courses. I suspect I can do this by creating an undirected graph as follows:


Each node of the graph represents a particular course applied to a particular category.
The graph has a clique for every category containing all of the nodes with that category, as well as a clique for every course containing all of the nodes with that course.


For the example case, we'd make a graph that looks like this:



Then, the number of requirements fulfilled would be the size of the maximum independent set of the graph.

Where I'm having trouble is in finding that maximum independent set. I'm aware that algorithms exist to find the maximum independent set of any graph in exponential time, but is there a more efficient algorithm I could use to take advantage of the fact that I already know all the maximal cliques?
This is an instance of bipartite matching.   You have one left-vertex for each course, one right-vertex for each category, and an edge between each course and each category it can be used for.  Now you want to find a maximum matching in this bipartite graph.  There exist standard polynomial-time algorithms for finding a maximum matching in a bipartite graph.