How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming? 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.
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.