1
$\begingroup$

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

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ @JɛffE: I cannot see why you asked it of me. According to the definition of “disconnected” by the asker, the empty graph is not disconnected. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 22, 2011 at 0:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – Yoshio Okamoto
    Commented Feb 22, 2011 at 2:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marc Bury
    Commented Feb 25, 2011 at 12:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Feb 25, 2011 at 12:57
  • 5
    $\begingroup$ 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). $\endgroup$
    – Per Austrin
    Commented Feb 25, 2011 at 15:22

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.