I have exercise:

Show reduction Denset-k-subgraph to ILP (Integer Linear Porgramming).

(Denset-k-subgraph is problem where there is graph G = (V, E) and two natural numbers k and t. We are asking if we can chose k vertices between whom there are at least t edges, for example $t =\binom{k}{2}$ we would asked about the clique of size k).

Below there is my solution:


$x_i = \begin{Bmatrix} 1 & \ when \ \ i \ \ vertex \ \ was \ \ chosen \\ 0 & o/w \end{Bmatrix}$


$1) \ \forall_{x_i}: 0 \leq x_i \leq 1 \\ $

$2) \ \sum_{i = 1}^{n} x_i = k, \ \ \ \ //where \ n =\left | V \right | \\$

$3) \ \sum_{i \in \left \{1,2,..,n \right \}\ :\ (v_i, v_j) \in E} x_ix_j = t \\$

Condition 2) just counts all chose vertices to be equal k

Condition 3) for every vertex and all his neighbours (there is edge connecting them) we are summing +1 if and only if both were chosen

Could somebody tell me is this correct reduction to ILP? If not what is wrong here?

Thank you


closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, Juho, Discrete lizard Feb 11 at 9:20

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ We can help you if you have any particular doubt, but we’re not going to mark your answer. That’s your grader’s job. $\endgroup$ – Yuval Filmus Feb 10 at 14:56
  • $\begingroup$ I doubt if my solution is okay. I dont know which part exactly could be wrong, I am asking you. I dont ask for full solution, just for tips. $\endgroup$ – JohnyBe Feb 10 at 15:06
  • $\begingroup$ @JohnyBe If you have no specific questions about your solution, you're just asking us to grade it for you. That's not what this site is for, sorry. $\endgroup$ – David Richerby Feb 10 at 16:48
  • $\begingroup$ Okay, so its very helpful community to study computer science. This rules is absolutely stupid, if I had known what is wrong in my solution I would have never ask you. I will never help anyone here in the future. $\endgroup$ – JohnyBe Feb 10 at 17:02