# Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a subgraph of G(V,E)

$$\max{\sum_{(i,j) \in E} {x_{ij}}}$$ $$\text{s.t.}$$ $$\forall (i,j)\in E \quad x_{ij} \leq y_i$$ $$\forall (i,j)\in E \quad x_{ij} \leq y_j$$ $$\sum_{i \in V}y_i \leq 1$$ $$\forall (i,j)\in E, i \in V \quad x_{ij}, y_i \geq 0$$

• The $\sum$ in the objective function should come after the $\max$ (rather than as a subscript). There should also be a constraint of the form $\sum_i y_i = 1$ or similar. Otherwise, the LP is unbounded. May 20, 2020 at 21:53
• Sorry, that's right. My bad, I missed in typing. Thanks for pointing it out. May 20, 2020 at 22:54

$$\begin{eqnarray} \textrm{maximize}\,\,&\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}& \\ \textrm{subject to}\,\,& x_{ij} \leq y_i& \forall {(i,j) \in E}\\ & x_{ij} \leq y_j& \forall {(i,j) \in E} \\ & 0 \leq x_{ij} \leq 1 &\forall {(i,j) \in E} \\ & 0 \leq y_i \leq 1 &\forall {i \in V} \\ \end{eqnarray}$$
Integer solutions to this program have a simple interpretation, with $$y_i = 1$$ iff vertex $$i$$ is in a chosen subgraph, $$x_{ij} = 1$$ only if $$(i,j)$$ is an edge in the subgraph induced by the selected vertices, and the objective function coming directly from the definition of the densest subgraph. Unfortunately, the objective function as written is not valid for an LP.
The key observation is that the objective function is scale-free, in that dividing all $$x_{ij}s$$ and $$y_i$$s of a feasible solution by the same constant value $$k \geq 1$$ does not affect either feasibility of a solution or its corresponding objective function value. Hence, we can without loss of generality restrict our attention to the case that $$\sum_{i \in V} y_i = 1$$ (otherwise, we can divide all LP variables by exactly $$k=\sum_{i \in V} y_i$$ to ensure this). We make this restriction explicit by adding in the constraint $$\sum_{i \in V} y_i = 1$$. But, with this constraint in hand, the denominator of the objective function for the above program is exactly $$1$$. Hence, we can remove it from the objective, leaving us with something that is linear, and in particular with the LP in the original post.