1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yonatan N May 20 at 21:53
  • $\begingroup$ Sorry, that's right. My bad, I missed in typing. Thanks for pointing it out. $\endgroup$ – am_rf24 May 20 at 22:54
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri May 21 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.