# "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?

• So, you're asking if number of maximal cliques is linear in the amount of edges, does it make task easier? Oct 16, 2017 at 1:42
• @rus9384 I'm trying to ask if already knowing all the maximal cliques makes the task easier somehow. As in, I have a set of sets of nodes, where each of those sets is a maximal clique of the graph. Can I use that information to more efficiently find the maximum independent set? Oct 16, 2017 at 3:27
• I'm not sure your independent set formulation really captures the essence of the problem. There are seven course category variables which must each be assigned to one value from some subset of course identifiers (these are the courses in that category), so that all the variables are assigned different values. This forms a bipartite graph (the variables form one part, the identifiers the other, and each variable is connected to the courses that satisfy that requirement). The problem can then be solved using a maximum matching algorithm. Oct 16, 2017 at 22:56
• If you are simply asking about the abstract problem of finding a largest independent set, given the graph and all its maximal cliques, then the example is misleading (you specify that a course cannot satisfy more than one requirement). Oct 16, 2017 at 23:01
• @AndrásSalamon Thanks for the tip! Bipartite matching seems like a much better solution to my problem than my independent set idea. If you copy-pasted that comment into an answer, I'd be happy to mark it as accepted. Oct 17, 2017 at 2:51

The question asks about the complexity of the following decision problem:

Independent Set with Maximal Cliques
Input: graph $G$, set $C$ of maximal cliques in $G$, positive integer $k$
Question: is there an independent set $S \subseteq V(G)$ with at least $k$ elements?

The intuition is presumably that $C$ can be quite large, so instead of $|V(G)|$ or $m=|E(G)|$, we instead have $|C|$ as being the dominant term of the instance size $n = |V(G)|+m+|C|$. It is quite easy for $|C|$ to be superpolynomial in $|V(G)|$ when $G$ has many edges, and then brute force will decide the problem in subexponential time. So this problem "should" be easier than if $C$ isn't provided.

The way to break this intuition is to show that even when $|C|$ is quite small (for instance, because the graph contains no triangles and hence no larger cliques either) the problem still remains NP-hard.

This is the case. By Poljak's construction, every graph $G$ can be 2-subdivided by inserting two new vertices into every edge, turning each edge into a a path of length 3. This ensures that the modified graph $G'$ is triangle-free. Moreover, $G'$ has an independent set with at least $m+k$ elements iff $G$ has an independent set with at least $k$ elements. This is a logspace reduction from Independent Set to the special case of Independent Set with Maximal Cliques where $C = E(G)$. Hence the problem remains NP-hard even if $C$ is given.

• Svatopluk Poljak, A note on stable sets and colorings of graphs, Comment. Math. Univ. Carolin. 15 (1974) 307-309. (PDF)

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.