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

<p>Steiner Tree (ST) in graphs problem</p>

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

<p><strong>Question</strong>: 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?</p>

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

<p>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 <em>middle node</em> 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 <em>target weight</em> greater or equal to $W = p(q+1) - k$.</p>

<p>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.</p>

<p>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).</p>

<p>And if you want to use only weights $+1,-1$ then you must:<br><strong>(A)</strong> assign $+1$ to all the nodes of the circular chains corresponding to nodes in $V\setminus R$,<br><strong>(B)</strong> transform every middle node to a linear chain of nodes of weight $-1$ and length $l_E = |V\setminus R|+1$, and<br><strong>(C)</strong> 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$.<br>
Informally, the expanded chains and the new target make the $+1$ weights of the nodes corresponding to $V \setminus R$ (point A) irrelevant.</p>

CC BY-SA 3.0
2014-03-21T21:14:36.197Z
you are very quick at designing NP-hardness gadgets !
Suresh Venkat
CC BY-SA 3.0
2014-03-21T21:20:15.417Z
@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](http://www.yworks.com/en/products_yed_about.html) you can draw a graph in a few minutes ... using tikzit it would take hours :).
Marzio De Biasi
CC BY-SA 3.0
2014-03-22T00:25:26.347Z
When there is a satisfying assignment, how do you make sure it is connected?
Austin Buchanan
CC BY-SA 3.0
2014-03-22T03:21:47.070Z
@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
CC BY-SA 3.0
2014-03-21T21:05:06.873Z
2014-03-22T21:03:55.793Z
2014-03-22T21:03:55.793Z
Marzio De Biasi
<p>The maximum-weight connected subgraph problem is as follows:</p>
<blockquote>
<p>Input: a graph <span class="math-container">$G=(V,E)$</span> and a weight <span class="math-container">$w_i$</span> (possibly negative) for each vertex <span class="math-container">$i \in V$</span>.</p>
<p>Output: a maximum-weight subset <span class="math-container">$S$</span> of vertices such that <span class="math-container">$G[S]$</span> is connected.</p>
</blockquote>
<p>This problem is NP-hard. David S. Johnson mentions on pg. 149 of <a href="http://www.sciencedirect.com/science/article/pii/0196677485900252" rel="noreferrer">this column</a> that the problem remains hard in planar graphs of maximum degree three with all weights either <span class="math-container">$+1$</span> or <span class="math-container">$-1$</span>.</p>
<p>I cannot find the cited paper --  <strong>A. Vergis, manuscript (1983)</strong></p>
<p>Any ideas as to where to find the paper? Or what the reduction was?</p>

<reference-request><np-hardness><reductions><planar-graphs>
Max-weight connected subgraph problem in planar graphs
Austin Buchanan
# Max-weight connected subgraph problem in planar graphs

(Asked by: username_0 on 2014-03-21)

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](http://www.sciencedirect.com/science/article/pii/0196677485900252) 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?

**Tags:** reference-request, np-hardness, reductions, planar-graphs

---

## 1 answers

### Answer by username_1 on 2014-03-21. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: you are very quick at designing NP-hardness gadgets !  
> **username_1**: @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](http://www.yworks.com/en/products_yed_about.html) you can draw a graph in a few minutes ... using tikzit it would take hours :).  
> **username_0**: When there is a satisfying assignment, how do you make sure it is connected?  
> **username_1**: @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 :-)  

---

