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
Minimum Weight Disconnected Subgraph and Opposite problems
ds.algorithms;graph algorithms