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?

  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 10 at 20:16
  • $\begingroup$ 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. $\endgroup$ – eager2learn Jun 10 at 20:55
  • $\begingroup$ Note that the additional constraints are only needed for the 5-cycle graph. $\endgroup$ – eager2learn Jun 10 at 21:00
  • $\begingroup$ 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? $\endgroup$ – D.W. Jun 10 at 22:11

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.