1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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? $\endgroup$
    – Yixin Cao
    Jul 22, 2017 at 13:17

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.