<p>I wonder what is known about the two following maximisation problems. </p>

<p><strong>Maximum weight connected subgraph</strong> :</p>

<p><strong>Input</strong> : A graph <span class="math-container">$G$</span>, with weights <span class="math-container">$w_v\in \mathbb{R}$</span> for each vertex <span class="math-container">$v \in V(G)$</span></p>

<p><strong>Output</strong> : A connected subgraph <span class="math-container">$H$</span> in <span class="math-container">$G$</span></p>

<p><strong>Objective</strong> : Maximise the weight of <span class="math-container">$H$</span></p>

<p>and <strong>Maximum weight connected <span class="math-container">$k$</span>-subgraph</strong> :</p>

<p><strong>Input</strong> : A graph <span class="math-container">$G$</span>, with positive weights <span class="math-container">$w_v\ge 0$</span> for each vertex</p>

<p><strong>Output</strong> : A connected subgraph <span class="math-container">$H$</span> in <span class="math-container">$G$</span> of size <span class="math-container">$k$</span></p>

<p><strong>Objective</strong> : Maximise the weight of <span class="math-container">$H$</span></p>

<p>I would very much appreciate any relevant related references.</p>

<p>I am particulary interested in the case when <span class="math-container">$G$</span> is a planar graph : Are there any constant aproximation algorithms known ? Any PTAS ?</p>

CC BY-SA 4.0
2019-06-24T07:48:42.037Z
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$.
GBathie
CC BY-SA 4.0
2019-06-24T07:54:47.590Z
Wait, I got it for the first problem, I didn't realize that the weights could be negative numbers.
GBathie
<reference-request><graph-algorithms><approximation-algorithms><planar-graphs>
Algorithms for Maximum weight connected subgraph in planar graphs
Mathieu Mari
# Algorithms for Maximum weight connected subgraph in planar graphs

(Asked by: username_0 on 2019-06-22)

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 ?

**Tags:** reference-request, graph-algorithms, approximation-algorithms, planar-graphs

> **Comments:**
> **username_1**: 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$.  
> **username_1**: Wait, I got it for the first problem, I didn't realize that the weights could be negative numbers.  

---

## 0 answers

