<blockquote>
  <p>Problem: 
  Given a graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, find 
  a partition of $V$ into two parts $V_1$ and $V_2$, so that $G[V_1]$ and $G[V_2]$ are connected and so that $w(V_1)$ is maximized.</p>
</blockquote>

<p>This problem is NP-hard, as follows easily from the following paper:</p>

<blockquote>
  <p>Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger:
  Partitioning graphs into connected parts. Theor. Comput. Sci. 410(47-49): 4834-4843 (2009)</p>
</blockquote>

<p>The paper shows that the following problem is NP-hard: Given a graph $G=(V,E)$ and two vertices $s,t\in V$, is there a "good" partition of $V$ into two sets $V_1$ and $V_2$, so that $G[V_1]$ and $G[V_2]$ are connected and so that $s,t\in V_1$. </p>

<p>Take such an instance, and make $w(s)=w(t)=1$ and $w(x)=0$ for $x\in V-\{s,t\}$. If there exists a good partition, you can reach $w(V_1)=2$.
If there is no good parition, the best you can get is $w(V_1)=1$.
(This argument shows NP-hardness, and also in-approximability within a
factor of $2-\epsilon$.)</p>

CC BY-SA 3.0
2017-07-21T12:23:18.363Z
2017-07-21T12:23:18.363Z
Gamow
<p>The max-weight connected subgraph problem (MWCS) may be described as follows:
given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one
seeks for a subset $L\subseteq V$ for which the spanned subgraph $G[L]$ is
connected and $\sum_{v\in L}w(v)$ is maximal.</p>

<p>The MWCS problem is known to be NP-hard (see <a href="https://arxiv.org/abs/1409.5308" rel="nofollow noreferrer">https://arxiv.org/abs/1409.5308</a>).</p>

<p>Consider the following variation: in the same settings, one seeks for a vertex
set $L$ for which the spanned subgraphs $G[L]$ and $G[V\smallsetminus L]$ are
both connected, and $\sum_{v\in L}w(v)$ is maximal.</p>

<p>My question is the following: is it possible that this variation takes the
problem out from the NP class?  If not - is it easy to see that it is still
hard, given that the original problem is hard?</p>

<p>And does it make a difference if one asks
$\sum_{v\in L}w(v)-\sum_{u\in V\smallsetminus L}w(u)$ to be maximal?</p>

CC BY-SA 3.0
2017-07-22T13:17:51.537Z
it's essentially the same problem because you can add a universal vertex (adjacent to every old vertex in the graph) with weight $-\infty$. You last question is not clear enough: Do you still need the connectivity condition? on both sides?
Yixin Cao
<ds.algorithms><graph-algorithms><np-hardness>
Max-weight connected & co-connected subgraph problem
Bach
# Max-weight connected & co-connected subgraph problem

(Asked by: username_0 on 2017-07-21)

The max-weight connected subgraph problem (MWCS) may be described as follows:
given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one
seeks for a subset $L\subseteq V$ for which the spanned subgraph $G[L]$ is
connected and $\sum\_{v\in L}w(v)$ is maximal.

The MWCS problem is known to be NP-hard (see <https://arxiv.org/abs/1409.5308>).

Consider the following variation: in the same settings, one seeks for a vertex
set $L$ for which the spanned subgraphs $G[L]$ and $G[V\smallsetminus L]$ are
both connected, and $\sum\_{v\in L}w(v)$ is maximal.

My question is the following: is it possible that this variation takes the
problem out from the NP class? If not - is it easy to see that it is still
hard, given that the original problem is hard?

And does it make a difference if one asks
$\sum\_{v\in L}w(v)-\sum\_{u\in V\smallsetminus L}w(u)$ to be maximal?

**Tags:** ds.algorithms, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: it's essentially the same problem because you can add a universal vertex (adjacent to every old vertex in the graph) with weight $-\infty$. You last question is not clear enough: Do you still need the connectivity condition? on both sides?  

---

## 1 answers

### Answer by username_2 on 2017-07-21. Score: 2

> Problem:
> Given a graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, find
> a partition of $V$ into two parts $V\_1$ and $V\_2$, so that $G[V\_1]$ and $G[V\_2]$ are connected and so that $w(V\_1)$ is maximized.

This problem is NP-hard, as follows easily from the following paper:

> Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger:
> Partitioning graphs into connected parts. Theor. Comput. Sci. 410(47-49): 4834-4843 (2009)

The paper shows that the following problem is NP-hard: Given a graph $G=(V,E)$ and two vertices $s,t\in V$, is there a "good" partition of $V$ into two sets $V\_1$ and $V\_2$, so that $G[V\_1]$ and $G[V\_2]$ are connected and so that $s,t\in V\_1$.

Take such an instance, and make $w(s)=w(t)=1$ and $w(x)=0$ for $x\in V-\{s,t\}$. If there exists a good partition, you can reach $w(V\_1)=2$.
If there is no good parition, the best you can get is $w(V\_1)=1$.
(This argument shows NP-hardness, and also in-approximability within a
factor of $2-\epsilon$.)


---

