# The heaviest induced subgraph problem

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.

• @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. – Łukasz Kuszner Nov 27 '17 at 20:42
• Yes, it's been studied in great details. en.wikipedia.org/wiki/Clique_problem#Hardness_of_approximation – Pål GD Nov 27 '17 at 21:28
• Search also for Weighted Clique. – Pål GD Nov 27 '17 at 21:29
• In the literature, the heaviest $k$-subgraph problem is your problem where all vertices have weight 1. – Juho Dec 3 '17 at 11:23
• @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. – Łukasz Kuszner 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.