Clique Cover Problem

Clique Cover Problem#

Here we show how to solve clique cover problems using JijSolver and JijModeling. This problem is also mentioned in 6.2. Clique Cover on Lucas, 2014, “Ising formulations of many NP problems”.

What is the clique cover problem?#

This problem is finding the minimum number of cliques (complete graphs) into which a given graph can be partitioned. This problem is known as NP-complete.

Complete graphs#

A complete graph is a graph whose two vertices are all adjacent to each other (not including loops or multiple edges). We show two examples below.

As we mentioned before, a vertex in a complete graph is adjacent to all other vertices. A complete undirected graph \(G = (V, E)\) has \({}_V C_2 = \frac{1}{2} V(V-1)\) edges, that is, the number of edges is equal to the number of combinations choosing two vertices from \(V\). Based on minimizing the difference in the number of edges from a complete graph, we describe a mathematical model for the clique cover problem.

Construction of a mathematical model#

First, we introduce binary variables \(x_{v, n}\) which are 1 if vertex \(v\) belongs to \(n\)-th subgraph and 0 otherwise.

Constraint: the vertices must belong to one clique#

In this problem, each vertex can belong to one subgraph.

\[ \sum_{n=0}^{N-1} x_{v, n} = 1 \quad (\forall v \in V) \tag{1} \]

Objective function : minimize the difference in the number of edges from a complete graph#

We consider \(n\)-th subgraph \(G (V_n, E_n)\). If this subgraph is complete, the number of edges of this subgraph is \(\frac{1}{2} V_n (V_n -1)\) from the previous discussion. In face, \(n\)-th subgraph has \(\sum_{(uv) \in E_n} x_{u, n} x_{v, n}\) edges. The more difference between the two is zero, the closer a subgraph is to a clique. Therefore, we set the objective function as follows.

\[ H = \sum_{n=0}^{N-1} \left\{ \frac{1}{2} \left( \sum_{v=0}^{V-1} x_{v, n} \right) \left( \sum_{v=0}^{V-1} x_{v, n} -1\right) - \sum_{(uv) \in E} x_{u, n} x_{v, n} \right\} \tag{2} \]

Modeling by JijModeling#

Next, we show an implementation using JijModeling. We first define variables for the mathematical model described above.

import jijmodeling as jm

# define variables
V = jm.Placeholder('V')
E = jm.Placeholder('E', ndim=2)
N = jm.Placeholder('N')
x = jm.BinaryVar('x', shape=(V, N))
n = jm.Element('n', belong_to=(0, N))
v = jm.Element('v', belong_to=(0, V))
e = jm.Element('e', belong_to=E)

Constraint#

We implement the constraint, Equation (1).

# set problem
problem = jm.Problem('Clique Cover')
# set one-hot constraint: each vertex has only one color
problem += jm.Constraint('color', x[v, :].sum()==1, forall=v)

x[v, :].sum() is equivalent to sum(n, x[v, n]).

Objective function#

Next, we implement an objective function Equation (2).

# set objective function: minimize the difference in the number of edges from complete graph
clique = x[:, n].sum() * (x[:, n].sum()-1) / 2
num_e = jm.sum(e, x[e[0], n]*x[e[1], n])
problem += jm.sum(n, clique-num_e)

Let’s display the implemented mathematical model in Jupyter Notebook.

problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Clique Cover} & & \\& & \min \quad \displaystyle \sum_{n = 0}^{N - 1} \left(\sum_{\ast_{0} = 0}^{V - 1} x_{\ast_{0}, n} \cdot \left(\sum_{\ast_{0} = 0}^{V - 1} x_{\ast_{0}, n} - 1\right) \cdot 2^{(-1)} - \sum_{e \in E} x_{e_{0}, n} \cdot x_{e_{1}, n}\right) & \\\text{{s.t.}} & & & \\ & \text{color} & \displaystyle \sum_{\ast_{1} = 0}^{N - 1} x_{v, \ast_{1}} = 1 & \forall v \in \left\{0,\ldots,V - 1\right\} \\\text{{where}} & & & \\& x & 2\text{-dim binary variable}\\\end{array}\end{split}\]

Prepare an instance#

We prepare a graph using Networkx.

import networkx as nx

# set the number of colors
inst_N = 3
# set empty graph
inst_G = nx.Graph()
# add edges
inst_E = [[0, 1], [1, 2], [0, 2], 
            [3, 4], [4, 5], [5, 6], [3, 6], [3, 5], [4, 6], 
            [7, 8], [8, 9], [7, 9], 
            [1, 3], [2, 6], [5, 7], [5, 9]]
inst_G.add_edges_from(inst_E)
# get the number of nodes
inst_V = list(inst_G.nodes)
num_V = len(inst_V)
instance_data = {'N': inst_N, 'V': num_V, 'E': inst_E}

This graph for the clique cover problem is shown below.

import matplotlib.pyplot as plt

nx.draw_networkx(inst_G, with_labels=True)
plt.show()
../_images/cfd1eaeff3f79b9d6c21c88fe991f9a48249ddaaa34a4f4b91e803cbd7926b9f.png

This graph has 3 cliques (0, 1, 2), (3, 4, 5, 6), and (7, 8, 9). In the next section, let’s try to detect these 3 cliques with JijSolver.

Solve by JijSolver#

We solve this problem using jijsolver.

import jijsolver

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

Visualize the solution#

In the end, we visualize the solution obtained.

df = solution.decision_variables
x_indices = df[df["value"]==1.0]["subscripts"]
# initialize vertex color list
node_colors = [-1] * len(x_indices)
# set color list for visualization
cmap = plt.get_cmap("tab10")
colorlist = [cmap(i) for i in range(inst_N)]
# set vertex color list
for i, j in x_indices:
    node_colors[i] = colorlist[j]
# make figure
nx.draw_networkx(inst_G, node_color=node_colors, with_labels=True)
plt.show()
../_images/839413f8b7b76ca11683b0498423752b876f9932a7bca57fa3b27a6a47efd41f.png

As we expected, JijSolver successfully split this graph into 3 cliques.

Contents