8
$\begingroup$

The maximum-weight connected subgraph problem is as follows:

Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$.

Output: a maximum-weight subset $S$ of vertices such that $G[S]$ is connected.

This problem is NP-hard. David S. Johnson mentions on pg. 149 of this column that the problem remains hard in planar graphs of maximum degree three with all weights either $+1$ or $-1$.

I cannot find the cited paper -- A. Vergis, manuscript (1983)

Any ideas as to where to find the paper? Or what the reduction was?

$\endgroup$

1 Answer 1

3
$\begingroup$

In the "The NP-Completeness Column: An Ongoing Guide" number 14, Johnson writes "... Vergis [49]. Transformation from STEINER TREE IN GRAPHS [ND12]...". I don't have access to the Vergis' paper, however a possible reduction can be the following.

Steiner Tree (ST) in graphs problem

Instance: an undirected graph $G = (V,E)$, a subset of the vertices $R \subseteq V$, called terminal nodes; a non-negative integer $k$

Question: is there a subtree of $G$ that includes all the vertices of $R$ (a spanning tree for $R$) and that contains at most $k$ edges?

The problem remains NPC even for planar graphs (M. Garey and D. Johnson. The rectilinear Steiner tree problem is NP-complete).

Given an instance of planar ST, for now suppose that you can assign arbitrary weights to nodes. If $|R|=p$ and $|E|=q$ , you can assign weight $q+1$ to the nodes of $R$ and you can add a middle node to every edge of $E$ and assign weight $-1$ to it. Assign weight $0$ to the remaining nodes in $V \setminus R$. The original graph $G$ has a spanning tree for $R$ with at most $k$ edges if and only if in the transformed graph you can find a subgraph of target weight greater or equal to $W = p(q+1) - k$.

Informally to reach the $p(q+1)$ quantity you must include all the nodes of $R$ in the subgraph, and you must include at most $k$ middle nodes (corresponding to the edges of $G$) that have negative weight -1 to keep them connected.

You can reduce the the max degree of the whole graph to three in this way: if $D = \max\{deg(u_i) \mid u_i \in V\}$ just transform each node $u_i$ to a circular chain of $D$ nodes (and adjust the value of $p$ accordingly). Connect the inbound edges to distinct nodes of the chain (that will have degree 3).

And if you want to use only weights $+1,-1$ then you must:
(A) assign $+1$ to all the nodes of the circular chains corresponding to nodes in $V\setminus R$,
(B) transform every middle node to a linear chain of nodes of weight $-1$ and length $l_E = |V\setminus R|+1$, and
(C) further expand the circular chains (with weight +1) corresponding to the nodes of $R$ to at least length $l_R = l_E( |E| + 1)$; and set target weight $W =pl_R - kl_E$.
Informally, the expanded chains and the new target make the $+1$ weights of the nodes corresponding to $V \setminus R$ (point A) irrelevant.

$\endgroup$
4
  • 1
    $\begingroup$ you are very quick at designing NP-hardness gadgets ! $\endgroup$ Mar 21, 2014 at 21:14
  • 1
    $\begingroup$ @SureshVenkat: but I'm still not sure it is correct :-S. However I'm also specialized in "Reinventing The Wheel" (RTW) reductions :-). Furthermore with yEd you can draw a graph in a few minutes ... using tikzit it would take hours :). $\endgroup$ Mar 21, 2014 at 21:20
  • $\begingroup$ When there is a satisfying assignment, how do you make sure it is connected? $\endgroup$ Mar 22, 2014 at 0:25
  • $\begingroup$ @AustinBuchanan: I changed the whole proof ... see if it can work (the previous one patched with the $(y_i,y_{i+1})$ edges was correct but didn't ensure a planar graph :-) $\endgroup$ Mar 22, 2014 at 3:21

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.