# Max-weight connected & co-connected subgraph problem

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?

• 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? Jul 22, 2017 at 13:17

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