# ILP relaxation for Cluster deletion on C5

I'm looking for additional constraints that get rid of fractional solutions for the LP relaxation of the Cluster Deletion problem:

Given an undirected graph $$G = (V, E)$$, find a min. sized $$E' \subset E$$ s.t. the induced graph with edge set $$E-E'$$ is a cluster graph, i.e. one in which all connected components are cliques.

An ILP formulation is:

$$max \sum_{(u,v) \in E)} x_{uv}$$

subject to:

$$x_{uv} + x_{vw} - x_{uw} \leq 1$$ $$\forall (u,v) \in E: x_{uv} \in\{0,1\}$$ $$\forall (u,v) \notin E: x_{uv} = 0$$

Looking at the 5-cycle graph I showed that the optimal solution is never integral and now I have to provide additional constraints (for the 5 cycle graph) which forbid non-integral solutions, but I'm unable to come up with any. Can someone help here please?

• I'm not sure what you're expecting. Is this problem NP-hard? (I presume it is.) If so, there is not likely to be any polynomial set of constraints that prevent non-integral solutions; if there was, it would lead to a polynomial-time algorithm (since linear programming can be solved in polynomial time) and thus a proof that P = NP, which seems a bit much to expect. – D.W. Jun 10 at 20:16
• I haven't seen a proof, but I also presume that the problem is NP-hard. The number of constraints doesn't have to be polynomial. – eager2learn Jun 10 at 20:55
• Note that the additional constraints are only needed for the 5-cycle graph. – eager2learn Jun 10 at 21:00
• If you only want it to work for a single graph, then it's trivial: find the solution somehow, then add constraints that force each $x_{uv}$ to be either 0 or 1 according to whether it is in that solution. Is this a homework exercise? What's the context in which you encountered this problem? – D.W. Jun 10 at 22:11