How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time?

Having an undirected graph, I am trying to partition all its vertices into cliques so that the number of cliques is the smallest. The problem can be formulated as an integer program, where every vertex corresponds to an integer variable (index of its clique), and the objective function is to minimize the sum of all these variables. For every edge not in the graph, a condition is created to ensure the corresponding vertex variables are not equal, like this:

$$b_k \in \{0, 1\}$$ $$x_i - x_j + M*b_k >= 1$$ $$x_j - x_i + M*(1-b_k) >= 1$$

$b_k$ indicates the relation between the values of $x_i$ and $x_j$. With a sufficiently large $M$, one of the conditions is always true, in which case the other one ensures the distance between the values is at least 1.

However, this approach seems to have exponential complexity, making it work only on very small graphs.

Assuming the number of cliques is expected to be small, and usually no edges exist across cliques, is there a better approach to this problem? I am thinking about finding the maximum independent set first and use it to fix certain variables (since they are guaranteed to be in different cliques). Will that help in increasing the speed?

  • 1
    $\begingroup$ The minimal clique cover problem is NP-hard. $\endgroup$ – Yuval Filmus Jun 13 '19 at 12:23
  • $\begingroup$ Are you also trying to solve the assignment for MFF UK? (Seems like exactly the same problem.) Got any ideas? $\endgroup$ – egst Jun 15 '19 at 8:34
  • $\begingroup$ @McSim Using indicator variables seems like a better idea than directly storing the clique index (gives less total variables), and finding a large independent set and fixing it reduces the ambiguity, but it is still inefficient. There must be some better way to remove ambiguities. $\endgroup$ – falc Jun 15 '19 at 15:39
  • $\begingroup$ The clique covering number of a graph is the chromatic number of the complement graph. So known techniques for coloring graphs with small chromatic number would be applicable. $\endgroup$ – mo2019 Jun 17 '19 at 4:38

Your Answer

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

Browse other questions tagged or ask your own question.