I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ of $G$ that maximizes the sum: $ \sum_{e \in E'} w_e(e) + \sum_{v \in V'} w_v(v) $.

The problem is NP-Hard (by the reduction from maximum clique problem) so any suggestions for approximation solutions (even greedy) and links to the literature would be appreciated.

  • $\begingroup$ @Juho First of all, I would like to know if such a problem has been considered. Any study, including a paper with experimental results is welcome. $\endgroup$ Nov 27 '17 at 20:42
  • $\begingroup$ Yes, it's been studied in great details. en.wikipedia.org/wiki/Clique_problem#Hardness_of_approximation $\endgroup$
    – Pål GD
    Nov 27 '17 at 21:28
  • $\begingroup$ Search also for Weighted Clique. $\endgroup$
    – Pål GD
    Nov 27 '17 at 21:29
  • $\begingroup$ In the literature, the heaviest $k$-subgraph problem is your problem where all vertices have weight 1. $\endgroup$
    – Juho
    Dec 3 '17 at 11:23
  • $\begingroup$ @Juho For example here heaviest $k$-subgraph problem is discussed, however it is not the same (but quite similar) as you are allowed to take but specified $k$ different vertices. In the case I am asking about you can take any amount of nodes. So, if you have found anything closer than the paper by Alain Billionnet mentioned above please point it out - it would be meaningful for me. $\endgroup$ Dec 4 '17 at 15:24

$\newcommand{\R}{\mathbb{R}}$ Let's consider a special case of the problem where vertex has negative weight and edges have positive weight. So $w_v: V\to \R^-$ and $w_e: E\to \R^+$.

Finding the heaviest induced subgraph is equivalent to a min-$st$-cut computation on a suitable graph. We will refer to the slides about densest subgraph in this presentation.

Indeed, minimizing $w_e(E(V'))+w_v(V')$ is equivalent to minimizing $(-w_v(V')) + \frac{1}{2} w_e(E(V',\bar{V'})) + \frac{1}{2} \sum_{v\in \bar{V'}} \deg(v)$. (Note the degree here are weighted degree, that is $\deg(v) =\sum_{e:v\in e} w_e(e)$) The derivation of the above fact is similar to slide 21. Then, this can be solved easily by modeling it as a min-$st$-cut in some other graph (see slide 22). It is crucial to have negative vertex weights and positive edge weights for the reduction to work.


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.