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


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.

  • $\begingroup$ 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 $\endgroup$
    – tuxErrante
    Dec 3 '14 at 12:05
  • $\begingroup$ Nobody said your way of reasoning can succeed (though for all I know, it might). $\endgroup$ Dec 3 '14 at 16:00
  • $\begingroup$ that sounds pretty obvious man. Despite that project-selection and baseball elimination seems to resolve it $\endgroup$
    – tuxErrante
    Dec 4 '14 at 12:25

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.