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

Question

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

1. min-cut project selection

2. min-cut baseball elimination

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

Answer 1

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.