# Max-weight connected subgraph problem in planar graphs

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?

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.

• you are very quick at designing NP-hardness gadgets ! – Suresh Venkat Mar 21 '14 at 21:14
• @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 :). – Marzio De Biasi Mar 21 '14 at 21:20
• When there is a satisfying assignment, how do you make sure it is connected? – Austin Buchanan Mar 22 '14 at 0:25
• @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 :-) – Marzio De Biasi Mar 22 '14 at 3:21