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 ?---------------------------- IDEASmin-cut project selectionmin-cut baseball eliminationdynamic programmingI 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..
Find a subgraph whose edge weights sum to at least the number of nodes
algorithms;graphs;decision problem;polynomial time