Given a simple graph $G$ with $n$ disjoint cliques. Cliques may contain a different number of vertices. Each vertex belongs to one of this cliques. $G$ may also contain edges between two vertices from different cliques.

Question: can I select one vertex from each clique such that no two of my selected vertices are connected by an edge in polynomial time? If yes, how? If no, is there any "approximate" solution?

Comment: of course, it is possible that no solution exists to a graph. It would be great, if we could detect an impossible situation quickly (in polynomial time). This quick detection would be effective not only to quickly find a solution, but to apply secondary aspects while we "scan" the solution.


This is a solution (red dots):

Solvable graph

This is an unsolvable graph:

Unsolvable graph

  • $\begingroup$ Are you given the cliques (ie which clique each vertex is part of) or do you have to infer them ? $\endgroup$ Mar 8 '15 at 14:12
  • $\begingroup$ We have a specified set of cliques containing specified sets of vertices. Plus we have a set of additional inter-clique edges. $\endgroup$ Mar 8 '15 at 17:20
  • $\begingroup$ Are you given that the cliques are maximal? $\endgroup$ Mar 9 '15 at 14:12
  • $\begingroup$ Good point. No. Given a set of cliques, but additional edges can create larger cliques. No information about maximum cliques. $\endgroup$ Mar 9 '15 at 14:30
  • $\begingroup$ If the cliques aren't maximal, then there can't be a solution, so one may as well assume that they are. $\endgroup$
    – Casteels
    Mar 9 '15 at 15:31

As an answer, I'll post a reduction from SAT to show the NP-Hardness of the problem.

Assume we are given a SAT instance in Conjunctive normal form, and Let $C = \{C_1, \ldots, C_m\}$ be its set of clauses.

Construct a graph $G$ by first adding $m$ disjoint cliques, one for each clause. Denote by $G_i$ the clique for $C_i$. Now, $G_i$ has as many vertices as $C_i$, one for each literal appearing in $C_i$. If $C_i = \{x_{1}, x_{2}, \ldots, x_{k}\}$, then $G_i$ has vertex set $V(G_i) = \{v_{i_1}, v_{i_2}, \ldots, v_{i_k}\}$, where the $v_{i_j}$ corresponds to $x_j$, the $j$-th literal of the $C_i$ clause. Note that some of these literals might be negated.

We then add an edge between each vertex pair $v \in V(G_i), w \in V(G_j)$ such that the literal corresponding to $v$ is the negation of the one corresponding to $w$. This guarantees that no solution of $G$ includes both a literal and its negation.

We now want to show that the SAT instance is satisfiable if and only if $G$ has a solution (an independent set of size $m$).

Suppose that the SAT instance is satisfiable by the set of literals $X = \{x_1, \ldots, x_n\}$. We then construct a solution for $G$.
For each $G_i$, there must exists a vertex $v \in V(G_i)$ corresponding to the literal $x$, such that $x \in X$ (because the $C_i$ clause is satisfied by $X$). Simply pick one such vertex in each $G_i$. Since $X$ does not contain both a literal and its negation, no pair of chosen vertices shares an edge, and therefore we have a solution.

Conversely, let $V = \{v_1, \ldots, v_m\}$ be a solution for $G$. Now, the set of literals corresponding to the ones in $V$ must be an assignment that satisfies the SAT instance, as finding $V$ corresponds to picking one literal per clause without picking both a literal and its negation.


Let's sketch a transformation of an instance of a graph $G$ to a SAT-instance in CNF (as asked by OP in the comments).

For each vertex $v_i \in V(G)$, add variable $v_i$ to the SAT instance.

Given an assignation for the SAT instance, we will interpret $v_i = True$ as choosing $v_i$ in $G$ in a solution. So we want to make the SAT instance satisfiable if for each clique $K$, there is some $v \in V(K)$ that the assignment sets to true, and that avoids setting two adjacent vertices to true.

Take a clique $K$ with $V(K) = \{v_1, \ldots, v_k\}$. To enforce choosing one of its vertices, add the clause $(v_1 \vee v_2 \vee \ldots \vee v_k)$. Do that for every clique.

Then, for two adjacent vertices $v_i, v_j \in V(G)$, we prevent setting both to true by adding the clause $\neg(v_i \wedge v_j) \equiv (\overline{v_i} \vee \overline{v_j})$. Do that for every pair of adjacent vertices.

Then, any satisfying assignment must choose one vertex per clique, and cannot choose two adjacent vertices.

  • $\begingroup$ Set of possible $C$s is a special subset of set of all possible CNF, am I right? $\endgroup$ Mar 11 '15 at 14:23
  • $\begingroup$ I'm not sure I get the question. Maybe I wasn't formal enough though. The clauses can consist of anything. Let's take an example...Say the SAT formula is $(x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee x_4) $, then we'll say $C_1 = \{x_1, x_2, \overline{x_3}\}$ and $C_2 = \{\overline{x_1}, x_4\}$. $\endgroup$ Mar 11 '15 at 14:44
  • $\begingroup$ Okay, I see that all formula can be transformed to a graph. (While a subset of graphs described by me can be transformed to a CNF formula.) Well, this is a hard problem. $\endgroup$ Mar 11 '15 at 15:56
  • $\begingroup$ Yes, and with a little bit of work, you can transform any of your graph into a CNF formula. So approximation algorithms or heuristics related to SAT may possibly be of use to you. $\endgroup$ Mar 11 '15 at 16:00
  • $\begingroup$ Can you write a sketch about your concept of this "little bit" of work? It does not seems too easy to me with a large amount of cliques and vertices. $\endgroup$ Mar 12 '15 at 19:04

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.