<p>If you think of $1 - X_{uv}$ as the "distance" between $u$ and $v$, then you can impose the triangle inequality: $1 - X_{uw} \le 1 - X_{uv} + 1 - X_{vw}$, which can be rewritten $X_{uv} + X_{vw} - X_{uw} \le 1$. This forces (in integral 0-1 solutions) the vertices to group into cliques. You can then check that the degree of every vertex is $k-1$ to ensure they form $k$-cliques.</p>

CC BY-SA 3.0
2017-04-28T23:01:00.863Z
2017-04-28T23:01:00.863Z
Andrew Morgan
<p>Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.</p>

CC BY-SA 3.0
2017-04-27T17:24:13.327Z
Do you mean *integer* linear programming, or just linear programming?  There is a significant difference.
D.W.
CC BY-SA 3.0
2017-04-28T18:41:55.987Z
Also, since you want the cliques to be disjoint, a more appropriate way to state the question is "how to check if a graph *is* $n/k$ disjoint $k$-cliques"
amakelov
CC BY-SA 3.0
2017-05-01T04:46:01.893Z
@amakelov: I assume the OP meant general subgraph, not induced subgraph, when asking about containment (otherwise the problem is completely trivial). If we allow general subgraphs, then a graph can certianly contain $n/k$ disjoint $k$-cliques but not be equal to $n/k$ disjoint $k$-cliques, just by adding some edges between the cliques...
Joshua Grochow
<graph-theory><graph-algorithms><linear-programming>
How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?
user45150
# How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?

(Asked by: username_0 on 2017-04-27)

Edges are given in form of $X\_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.

**Tags:** graph-theory, graph-algorithms, linear-programming

> **Comments:**
> **username_1**: Do you mean *integer* linear programming, or just linear programming?  There is a significant difference.  
> **username_2**: Also, since you want the cliques to be disjoint, a more appropriate way to state the question is "how to check if a graph *is* $n/k$ disjoint $k$-cliques"  
> **username_3**: @username_2: I assume the OP meant general subgraph, not induced subgraph, when asking about containment (otherwise the problem is completely trivial). If we allow general subgraphs, then a graph can certianly contain $n/k$ disjoint $k$-cliques but not be equal to $n/k$ disjoint $k$-cliques, just by adding some edges between the cliques...  

---

## 1 answers

### Answer by username_4 on 2017-04-28. Score: 1

If you think of $1 - X\_{uv}$ as the "distance" between $u$ and $v$, then you can impose the triangle inequality: $1 - X\_{uw} \le 1 - X\_{uv} + 1 - X\_{vw}$, which can be rewritten $X\_{uv} + X\_{vw} - X\_{uw} \le 1$. This forces (in integral 0-1 solutions) the vertices to group into cliques. You can then check that the degree of every vertex is $k-1$ to ensure they form $k$-cliques.


---

