Max-weight connected & co-connected subgraph problem

Question

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?

Answer 1

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