<p>Given a graph $G = (V,E)$ and a vertex weight $z_v$ for each $v \in V$, find an (EDIT) <strong>induced</strong> subgraph $G&#39; = (V&#39;, E&#39;)$ with minimum weight $z_{G&#39;}=\sum_{v&#39; \in V&#39;} z_{v&#39;}$ where $G&#39;$ is <i>disconnected</i> (i.e., has 2 or more maximal connected components).</p>

<p>The maximum weight <i>connected</i> subgraph problem is known to be NP-hard by reduction from MINIMUM-COVER [1].  Is this "opposite" disconnected problem easier?</p>

<p>Also, maybe this deserves its own question, but are there interesting (non-contrived) cases where the "opposite" of a well-known hard problem is easy?  Here's an attempt at defining opposite for vertex-weighted graph optimization problems:</p>

<p>The problem P is defined as follows. Given a vertex-weighted graph $G$, and a set $\mathcal{S}$ of induced subgraphs of $G$, find an induced subgraph in $\mathcal{S}$ with maximum weight. Then, the opposite of $P$ is defined as follows. Given a vertex-weighted graph $G$, and the set $\mathcal{\bar S}$ of induced subgraphs of $G$ that are not in $\mathcal{S}$, find an induced subgraph in $\mathcal{\bar S}$ with minimum weight.</p>

<p>(Note: since $z_v$ is not constrained to be positive, minimizing or maximizing is arbitrary.  I switch only for aesthetics related to the term "opposite".)</p>

<p>[1] <a href="http://prosecco.ucsd.edu/ISMB2002/nph.pdf" rel="nofollow">http://prosecco.ucsd.edu/ISMB2002/nph.pdf</a></p>

CC BY-SA 2.5
2011-02-21T20:00:14.757Z
If vertex weights are restricted to nonnegative numbers, the minimum weight disconnected subgraph can be found in polynomial time because it is equivalent to finding a pair of nonadjacent vertices such that the sum of the weights of the two vertices is minimized.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-21T21:16:13.097Z
Yes, if vertex weights are nonnegative, then the maximum weight connected subgraph problem also has a trivial solution (of G'=G).
dan_x
CC BY-SA 2.5
2011-02-21T22:40:27.407Z
@Tsuyoshi: Is the empty set connected?  (It has zero connected components.)
Jeffε
CC BY-SA 2.5
2011-02-22T00:09:04.133Z
@JɛﬀE: I cannot see why you asked it of me.  According to the definition of “disconnected” by the asker, the empty graph is not disconnected.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-22T01:38:21.110Z
I'm afraid that the "opposite" problem in the general setting, as suggested in the question, does not capture the case of connected and disconnected subgraphs.  I just guess it's implicitly assumed that if G' = (V', E') is connected, then G'' = (V', E-E') is disconnected, but this is not true: The complement of a connected graph can be connected as the path on four vertices shows.  Probably, the right way is to look at a graph property and its complement.
Yoshio Okamoto
CC BY-SA 2.5
2011-02-22T02:05:11.783Z
@Yoshio: The only assumption I'm making is that the set of subgraphs of G can be split into two disjoint sets: those that are connected, and those that aren't (and the union of the two covers all subgraphs).  I agree that a connected graph can have a connected graph as its complement, so it might be that both G' and your G'' are in the "connected" set, but I don't see how that's relevant...
dan_x
CC BY-SA 2.5
2011-02-22T02:27:06.070Z
@dan x: Thanks a lot. Then, we don't look at a graph and its complement, but we look at the set of subgraphs of $G$, and its partition into two classes. The formulation should be like "The problem $P$ is defined as follows. Given a vertex-weighted graph $G$, and a set $\cal{S}$ of subgraphs of $G$, find a subgraph in $\cal{S}$ with max weight. Then, the opposite of $P$ is defined as follows. Given a vertex-weighted graph $G$, and the set $\overline{\cal{S}}$ of subgraphs of $G$ that are not in $\cal{S}$, find a subgraph in $\overline{\cal{S}}$ with min weight.  I understand in this way.
Yoshio Okamoto
CC BY-SA 2.5
2011-02-22T02:32:06.593Z
@Yoshio: Thanks for the constructive help with writing clarity.  I'll edit the question to put it in those terms.
dan_x
CC BY-SA 2.5
2011-02-25T12:06:08.677Z
I think the connected subgraph problem is "reducable" to the disconnected subgraph problem. If you put in some extra isolated vertex with positive weight (in case of max) then every optimal solution of the disconnected subgraph problem contains this vertex and satisfies the disconnection property. So in the remaining graph the solution contains the maximum weight connected subgraph of the original graph.
Marc Bury
CC BY-SA 2.5
2011-02-25T12:57:38.107Z
dan, do you mean induced subgraphs? If not, then of course the problem is trivial; take no edges and negative weights (in case of no negative weights, the two smallest weights). If you mean induced, then I guess the first step of the reduction should be something like in Marc's comment.
domotorp
CC BY-SA 2.5
2011-02-25T15:22:09.067Z
If induced subgraph is meant the problem seems to be as hard as the vertex separator problem: simply set all weights to be -1 (then you're maximizing the number of vertices kept, i.e., minimizing the number of vertices removed to separate the graph into two components).
Per Austrin
CC BY-SA 2.5
2011-02-25T15:40:57.007Z
Yes, I mean induced subgraph.
dan_x
<ds.algorithms><graph-algorithms>
Minimum Weight Disconnected Subgraph and "Opposite" problems
dan_x
# Minimum Weight Disconnected Subgraph and "Opposite" problems

(Asked by: username_0 on 2011-02-21)

Given a graph $G = (V,E)$ and a vertex weight $z\_v$ for each $v \in V$, find an (EDIT) **induced** subgraph $G' = (V', E')$ with minimum weight $z\_{G'}=\sum\_{v' \in V'} z\_{v'}$ where $G'$ is *disconnected* (i.e., has 2 or more maximal connected components).

The maximum weight *connected* subgraph problem is known to be NP-hard by reduction from MINIMUM-COVER [1]. Is this "opposite" disconnected problem easier?

Also, maybe this deserves its own question, but are there interesting (non-contrived) cases where the "opposite" of a well-known hard problem is easy? Here's an attempt at defining opposite for vertex-weighted graph optimization problems:

The problem P is defined as follows. Given a vertex-weighted graph $G$, and a set $\mathcal{S}$ of induced subgraphs of $G$, find an induced subgraph in $\mathcal{S}$ with maximum weight. Then, the opposite of $P$ is defined as follows. Given a vertex-weighted graph $G$, and the set $\mathcal{\bar S}$ of induced subgraphs of $G$ that are not in $\mathcal{S}$, find an induced subgraph in $\mathcal{\bar S}$ with minimum weight.

(Note: since $z\_v$ is not constrained to be positive, minimizing or maximizing is arbitrary. I switch only for aesthetics related to the term "opposite".)

[1] <http://prosecco.ucsd.edu/ISMB2002/nph.pdf>

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: If vertex weights are restricted to nonnegative numbers, the minimum weight disconnected subgraph can be found in polynomial time because it is equivalent to finding a pair of nonadjacent vertices such that the sum of the weights of the two vertices is minimized.  
> **username_0**: Yes, if vertex weights are nonnegative, then the maximum weight connected subgraph problem also has a trivial solution (of G'=G).  
> **username_2**: @Tsuyoshi: Is the empty set connected?  (It has zero connected components.)  
> **username_1**: @JɛﬀE: I cannot see why you asked it of me.  According to the definition of “disconnected” by the asker, the empty graph is not disconnected.  
> **username_3**: I'm afraid that the "opposite" problem in the general setting, as suggested in the question, does not capture the case of connected and disconnected subgraphs.  I just guess it's implicitly assumed that if G' = (V', E') is connected, then G'' = (V', E-E') is disconnected, but this is not true: The complement of a connected graph can be connected as the path on four vertices shows.  Probably, the right way is to look at a graph property and its complement.  
> **username_0**: @Yoshio: The only assumption I'm making is that the set of subgraphs of G can be split into two disjoint sets: those that are connected, and those that aren't (and the union of the two covers all subgraphs).  I agree that a connected graph can have a connected graph as its complement, so it might be that both G' and your G'' are in the "connected" set, but I don't see how that's relevant...  
> **username_3**: @dan x: Thanks a lot. Then, we don't look at a graph and its complement, but we look at the set of subgraphs of $G$, and its partition into two classes. The formulation should be like "The problem $P$ is defined as follows. Given a vertex-weighted graph $G$, and a set $\cal{S}$ of subgraphs of $G$, find a subgraph in $\cal{S}$ with max weight. Then, the opposite of $P$ is defined as follows. Given a vertex-weighted graph $G$, and the set $\overline{\cal{S}}$ of subgraphs of $G$ that are not in $\cal{S}$, find a subgraph in $\overline{\cal{S}}$ with min weight.  I understand in this way.  
> **username_0**: @Yoshio: Thanks for the constructive help with writing clarity.  I'll edit the question to put it in those terms.  
> **username_4**: I think the connected subgraph problem is "reducable" to the disconnected subgraph problem. If you put in some extra isolated vertex with positive weight (in case of max) then every optimal solution of the disconnected subgraph problem contains this vertex and satisfies the disconnection property. So in the remaining graph the solution contains the maximum weight connected subgraph of the original graph.  
> **username_5**: dan, do you mean induced subgraphs? If not, then of course the problem is trivial; take no edges and negative weights (in case of no negative weights, the two smallest weights). If you mean induced, then I guess the first step of the reduction should be something like in Marc's comment.  
> **username_6**: If induced subgraph is meant the problem seems to be as hard as the vertex separator problem: simply set all weights to be -1 (then you're maximizing the number of vertices kept, i.e., minimizing the number of vertices removed to separate the graph into two components).  
> **username_0**: Yes, I mean induced subgraph.  

---

## 0 answers

