I wonder what is known about the two following maximisation problems.

Maximum weight connected subgraph :

Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$

Output : A connected subgraph $H$ in $G$

Objective : Maximise the weight of $H$

and Maximum weight connected $k$-subgraph :

Input : A graph $G$, with positive weights $w_v\ge 0$ for each vertex

Output : A connected subgraph $H$ in $G$ of size $k$

Objective : Maximise the weight of $H$

I would very much appreciate any relevant related references.

I am particulary interested in the case when $G$ is a planar graph : Are there any constant aproximation algorithms known ? Any PTAS ?

  • 2
    $\begingroup$ For the first problem : can you define what a subgraph of $G$ is ? If it is just a subset of $E$, with corresponding vertices, then just take the connected component with maximum weight ? I don't think the planarity changes anything here. For the second problem : If $k$ is fixed (i.e. not part of the input), then the problem is polynomial : check the ${n \choose k}$ possible subsets of $V$ with size $k$. $\endgroup$ – GBat Jun 24 '19 at 7:48
  • 1
    $\begingroup$ Wait, I got it for the first problem, I didn't realize that the weights could be negative numbers. $\endgroup$ – GBat Jun 24 '19 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.