# Algorithms for Maximum weight connected subgraph in planar graphs

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 ?

• 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$. – GBat Jun 24 at 7:48
• Wait, I got it for the first problem, I didn't realize that the weights could be negative numbers. – GBat Jun 24 at 7:54