Proving Graphical Steiner Tree is NP-Complete

Preface

We prove the graphical steiner tree problem is NP-complete by reducing vertex cover to it. The version of it is taken from our favorite Kleinberg and Tardos’ Algorithm Design book’s exercises. We assume the reader is familiar with vertex cover, what NP-completeness is and the general approach for proving it by reduction.

Graphical Steiner Tree Definition

Here is a clear definition of the problem we prove its NP-completeness, Taken from klienberg and tardos’ exercise 38 of chapter 8, NP and computational intractability.

Example and High-Level Overview

Before showing a rigour proof, We present a simple example which demonstrates our approach. We begin with a vertix cover example, then accordingly encode it into an instance of the graphical steiner tree problem. We give some insights why finding a solution to the latter accounts for a solution to the former, and Hence argue our claimed proof is correct.

Vertex Cover

Let’s consider a simple example of vertex cover problem. A graph $G$ has vertices $G(V) = \set {1, 2, 3, 4}$ colored in red and purple, and edges $G(E) = \set {1, 2, 3, 4 }$ colored in green. Finally, Let $k=2$

Clearly, A subset $G(V)_{red} = \set {1, 2}$ has the minimum possible number of elements which enables covering all edges $G(E)$. Now let’s see how it is going to be encoded into an instance of a graphical steiner tree.

Graphical Steiner Tree

Construct a graph $G’$ whose vertices $G’(V)$ are the unions of,

$\set {S}$ a special vertex, $\set {1, 2, 3, 4} = G’(V)_e$ colored in green corresponding to edges of the vertex cover $G(E)$, $\set {1’, 2’, 3’, 4’} = G’(V)_v$ colored in red and purple corresponding to vertices of the vertex cover $G(V)$, and $\set {1_0, 2_0, 3_0, 4_0} = G’(V)_o$ contains an additional vertex colored in white for each element of $G’(V)_v$. Note vertices in $G’(V)_o$ and vertex $S$ are not corresponded to anything in the vertex cover instance.

$G’$’s edges $G’(E)$ are the unions of,

$G’(E)_c$ corresponding to edges which connect $G’(V)_v$ with $G’(V)_e$ in case an edge is covered by a vertex in the vertex cover instance, and $G’(E)_S$ contains two edges for each element of $G’(V)_v$ connecting it to the special vertex $S$ via $G’(V)_o$. Note edges in $G’(E)_S$ are not corresponded to anything in the vertex cover instance.

Define $X’ = \set{S} \cup G’(V)_v \cup G’(V)_e$

Define $k’ = ||G’(V)_e|| + 2(k) + (||G’(V)_v||-(k))$ $=$ $||G’(V)_e|| + 2(2) + (||G’(V)_v||-(2))$ where $k$ is taken from vertex cover instance.

Accounting a Solution for Vertex Cover

Let’s remark how a solution of encoded Graphical Steiner Tree yields a solution to Vertex Cover.

By definition of Graphical Steiner Tree, and definition of X, $G’(V)_v$ vertices must be connected to $S$. For each, There are two pathways, Either connecting backward via $G’(V)_o$ with cost of two edges, or connecting forward via $G’(V)_e$. So there is a penalty on connecting backward, and the algorithm is obliged to connect forward as much as possible to reduce the number of edges. In other words, We could reform the algorithm’s goal as, In order to connect $X$ in a single component with least possible edges, What is the minimum number of vertices of $G’(V)_v$ needs to be connected backward;y?

The trick here as shown from the example is that we reduced vertices covering edges in vertex cover to vertices connected to other vertices in graphical steiner tree.

More Rigour Remarks

Now let’s present some more rigour remarks of our reduction. For the sake of readability, We intentionally omit the definition of constructed encoded instance of graphical steiner tree. We believe the above discussion suffices to convince the reader. In addition, We assume on behalf of the reader to see why both theorem 1 and theorem 2 suffices to prove intended NP-completeness.

Theorem 1

If a vertex cover instance is decided to be covered by at most $k$ vertices, Then the encoded graphical steiner tree is decided to be solved by at most $k’$ edges.

Note the definition of $k’$ is stated above.

Proof

Let $X \subseteq G(V)$ be the chosen vertices in vertex cover instance which cover all its edges. Let $G’(V)_X \subseteq G’(V)_v$ containing elements corresponding to $X$.

Construct $F \subseteq G’(E)$ containing,

One edge from each element of $G’(V)_e$ to some element in $G’(V)_X$, Two edges from each element of $G’(V)_X$ along the path to $S$, and one edge from each element of to $G’(V)_v - G’(V)_X$ to any remaining $G’(V)_e$.

Clearly, Mentioned edges exist. Also, $X’$ (see its definition above) is a single component in the graph, As all needed vertices are connected to $S$.

By definition, The number of elements in $X$ is at most $k$. Clearly, All mentioned edges of $X’$ are distinct from each other. Hence, The number of them is at most $k’$ following $F$’s construction.

Theorem 2

If the encoded graphical steiner tree is decided to be solved by at most $k’$ edges, Then vertex cover instance is decided to be covered by at most $k$ vertices.

Proof

Let $X’$ be the solution of encoded graphical steiner tree. Since $X’$ is a single-component in the graph, All vertices must be connected to $S$ including $G’(V)_v$. Those are connected either backward through $G’(V)_o$ or forward through $G’(V)_e$. Let $G’(V)_b$ be those which are connected backwardly. Let $k’_b$ be equal to its number of elements.

Construct $X \subseteq G(V)$ containing vertices in vertex cover instance corresponding to $G’(V)_b$ in $X’$. It is not hard to see those vertices cover all edges in vertex cover. Clearly, In $X’$ each element of $G(V)_e$ is connected to some element in $G(V)_b$, Otherwise they won’t be connected to $S$ violating $X’$ definition. Hence, every edge in vertex cover must be covered by $X$.

What is remaining is to prove $X$’s cardinality is at most $k$. In other words, We need to show $k’_b$ is at most $k$. Assume for the sake of contradiction that $k’_b > k$. Then $||X’|| \geq ||G’(V)_e|| + 2(k’_b) + (||G’(V)_v||-(k’_b))$ $>$ $||G’(V)_e|| + 2(k) + (||G’(V)_v||-(k))$ $=$ $k’$ violating $X’$ to be at most $k’$ as defined.

Conclusion

I acknowledge that might not be a complete proof, However we believe it suffices for anyone with minimum familiarity of computational complexity theory or NP-completeness. We did really enjoy figuring the trick of reducing covering edges by vertices to connecting vertices to other vertices. After all, The literature is crammed with proved NP-complete problems. I guess a first-look in Computers and Intractability: A Guide to the Theory of NP-completeness by Garey and Johnson delineates this blog post trivial. However, I am happy that I was able to think from a different perspective to figure this problem out by only the aid of Kleinberg and Tardos’ book.

References

• Kleinberg and Tardos. Algorithm Design. Pearson