<p>Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com.</p>

<p>The intuition becomes more apparent if you first write down an alternate similar looking but not necessarily linear mathematical program</p>

<p><span class="math-container">$$\begin{eqnarray}
\textrm{maximize}\,\,&amp;\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}&amp; \\
\textrm{subject to}\,\,&amp; x_{ij} \leq y_i&amp; \forall {(i,j) \in E}\\
&amp; x_{ij} \leq y_j&amp; \forall {(i,j) \in E} \\
&amp; 0 \leq x_{ij} \leq 1 &amp;\forall {(i,j) \in E} \\
&amp; 0 \leq y_i \leq 1 &amp;\forall {i \in V} \\
\end{eqnarray}$$</span></p>

<p>Integer solutions to this program have a simple interpretation, with <span class="math-container">$y_i = 1$</span> iff vertex <span class="math-container">$i$</span> is in a chosen subgraph, <span class="math-container">$x_{ij} = 1$</span> only if <span class="math-container">$(i,j)$</span> 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. </p>

<p>The key observation is that the objective function is scale-free, in that dividing all <span class="math-container">$x_{ij}s$</span> and <span class="math-container">$y_i$</span>s of a feasible solution by the same constant value <span class="math-container">$k \geq 1$</span> 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 <span class="math-container">$\sum_{i \in V} y_i = 1$</span> (otherwise, we can divide all LP variables by exactly <span class="math-container">$k=\sum_{i \in V} y_i$</span> to ensure this). We make this restriction explicit by adding in the constraint <span class="math-container">$\sum_{i \in V} y_i = 1$</span>. But, with this constraint in hand, the denominator of the objective function for the above program is exactly <span class="math-container">$1$</span>. Hence, we can remove it from the objective, leaving us with something that <em>is</em> linear, and in particular with the LP in the original post.</p>

CC BY-SA 4.0
2020-05-21T21:28:40.297Z
Want to point  out that when one deals with "ratio"  problems such a densest subgraph or sparsest cut this is a standard trick to normalize the denominator to 1 so as to get an LP.
Chandra Chekuri
CC BY-SA 4.0
2020-05-20T22:36:09.353Z
2020-05-23T08:05:56.707Z
2020-05-23T08:05:56.707Z
Yonatan N
<p>I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1184&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">this</a> paper. 
Just mentioning the LP for maximum density of a subgraph of G(V,E)</p>

<p><span class="math-container">$$ \max{\sum_{(i,j) \in E} {x_{ij}}}$$</span>
<span class="math-container">$$\text{s.t.}$$</span>
<span class="math-container">$$\forall (i,j)\in E \quad x_{ij} \leq y_i$$</span>
<span class="math-container">$$\forall (i,j)\in E \quad x_{ij} \leq y_j$$</span>
<span class="math-container">$$\sum_{i \in V}y_i \leq 1$$</span>
<span class="math-container">$$\forall (i,j)\in E, i \in V \quad x_{ij}, y_i \geq 0$$</span></p>

CC BY-SA 4.0
2020-05-20T21:53:16.813Z
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.
Yonatan N
CC BY-SA 4.0
2020-05-20T22:54:13.817Z
Sorry, that's right. My bad, I missed in typing. Thanks for pointing it out.
am_rf24
<graph-theory><graph-algorithms><linear-programming><combinatorics>
Intuition behind the Charikar's LP formulation for densest subgraph problem
am_rf24
# Intuition behind the Charikar's LP formulation for densest subgraph problem

(Asked by: username_0 on 2020-05-20)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1184&rep=rep1&type=pdf) 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$$

**Tags:** graph-theory, graph-algorithms, linear-programming, combinatorics
> **Comments:**
> **username_1**: 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.  
> **username_0**: Sorry, that's right. My bad, I missed in typing. Thanks for pointing it out.  

---

## 1 answers

### Answer by username_1 on 2020-05-20. Score: 2 | Accepted answer

Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com.

The intuition becomes more apparent if you first write down an alternate similar looking but not necessarily linear mathematical program

$$\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.

> **Comments:**
> **username_2**: Want to point  out that when one deals with "ratio"  problems such a densest subgraph or sparsest cut this is a standard trick to normalize the denominator to 1 so as to get an LP.  

---

