# Find a subgraph whose edge weights sum to at least the number of nodes

Given a graph G = (V,E) every edge is assigned a real number Xe $\in$ [0,1]

The sum of x variables for all edges is equal to the number of edges -1 : $\sum x_V = |V|-1$

For a subset S $\subset$ V let us denote by $E_{(S)}$ the set of all edges with both endpoints in the subset S.

Give a polynomial time algorithm that takes as an input graph G and numbers $X_e$ for e $\in$ E, and either finds a subset S such that

$\sum_{e \in E(s)} X_e > |S|-1$

or says that no such set S exists.

Analysis of its correctness and its running time.

Any suggestion please ?

---------------------------- IDEAS

3. ### dynamic programming

I was trying to build a list of dictionaries, storing for each node, the sum of the edges of every subgraph in which it is.

work in progress..

## 1 Answer

Your problem is very similar to the classical densest subgraph problem, in which you want to maximize the ratio $|E(S)|/|S|$. Goldberg gave a polynomial time algorithm for this problem based on network flow. Perhaps you can use his ideas to solve your specific problem as well.

• This doesn't seems to be helpful for the way I'm reasoning (see Edit), may be it can be helpful to give a starting point to a dynamic programming approach Dec 3 '14 at 12:05
• Nobody said your way of reasoning can succeed (though for all I know, it might). Dec 3 '14 at 16:00
• that sounds pretty obvious man. Despite that project-selection and baseball elimination seems to resolve it Dec 4 '14 at 12:25