8
$\begingroup$

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.

$\endgroup$
9
  • $\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, 2017 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, 2017 at 21:28
  • $\begingroup$ Search also for Weighted Clique. $\endgroup$
    – Pål GD
    Nov 27, 2017 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, 2017 at 11:23
  • 1
    $\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, 2017 at 15:24

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.