2
$\begingroup$

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:

a graph with three nodes: "CHINESE 110A, arts/lit", "CHINESE 110A, international", and "COMLIT 156, arts/lit". There are two links, one between the two Chinese nodes and one between the two arts/lit nodes.

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?

$\endgroup$
  • $\begingroup$ So, you're asking if number of maximal cliques is linear in the amount of edges, does it make task easier? $\endgroup$ – rus9384 Oct 16 '17 at 1:42
  • $\begingroup$ @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? $\endgroup$ – Carter Sande Oct 16 '17 at 3:27
  • 2
    $\begingroup$ 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. $\endgroup$ – András Salamon Oct 16 '17 at 22:56
  • $\begingroup$ 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). $\endgroup$ – András Salamon Oct 16 '17 at 23:01
  • $\begingroup$ @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. $\endgroup$ – Carter Sande Oct 17 '17 at 2:51
2
$\begingroup$

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)
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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