# 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.

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

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.