# Vertex Disjoint Directed Max Steiner Tree Packing

I am not getting enough literature on Vertex Disjoint/Vertex Capacited Min Steiner Tree Packing Most of the few papers that I have found refers to one reference which is not accessible over internet.

Korte, B., H. J. Pr6mel and A. Steger, "Steiner Trees in VLSI-layout", in Paths, Flows, and VLSI-Layout, Korte, B., L. Lovisz, H. J. Prtimel and A. Schrijver (Eds.), Springer-Verlag (1990).

One early works[1] claim the following is known to be NP-Complete

Given an undirected graph $G=(V,E)$ and a Family Terminal sets $\psi = {N_{i}\subseteq V: i=1...K}$ where $N_{i}\cap N_{j} = \phi$ edge cost $c(e) \geq 0 \;\forall e\in E$, vertex cost $n(v) \geq 0 \;\forall v\in V$ find a minimum-cost Family $\Gamma = \{T_{N_{i}}\}$ where each $T_{N_{i}}$ corresponds to Steiner tree for terminal vertices $N_{i} = (V_{N_{i}},E_{N_{i}})$ and $V_{N_{i}} \cap V_{N_{j}} = \phi \;\forall i \neq j$, where cost of the Tree is determined by $C(T_{N_{i}}) = \sum_{e\in E_{N_{i}}} c(e) + \sum_{v\in V_{N_{i}}} n(v)$

But this does not imply any constraint on $\vert N_{i} \vert$ which makes me believe that it is NP-complete for $\vert N_{i} \vert = 2$ as well. Am I correct ? or the authors just missed to put the limits ?

Also does not consider negative edge weights and directed graphs.

In that paper authors show for series parallel graph it can be solved in polynomial time $O(n^{5})$ worst case complexity. But series parallel graph is $k$ connected for a fixed $m$ and often $m=2$. Probabbly that's why it can be solved in P time.

Another early work [2]

we prove that PVCD with unit capacitiesis NP-hard even in the simplest non-trivial case where there are only three terminals (one root r and two other terminals) and we are asked to find only 2 vertex-disjoint Steiner trees. The problem becomes trivially easy if any of these two conditions is tighter, i.e., if the number of terminals is reduced to 2 or the number of Steiner trees that we have to find is reduced to 1.

• Packing Vertex Capacitated Directed Steiner Trees (PVCD)

Which actually implies $\vert N_{i} \vert = 2$ it is trivially easy to solve (i.e. Not NP-Complete).

Here does these two papers conflict ? or in undirected case $\vert N_{i} \vert$ can be arbitrary ?

[1] Chopra, Sunil, and Kalyan T. Talluri. "Minimum-Cost Node-Disjoint Steiner Trees in Series-Parallel Networks." VLSI Design 4.1 (1996): 53-57.

[2] Cheriyan, Joseph, and Mohammad R. Salavatipour. "Hardness and approximation results for packing Steiner trees." Algorithmica 45.1 (2006): 21-43.

• What does the vertex capacity $c(v)$ mean? If it is the maximum number of edges that may be incident on the vertex, then Hamiltonian Path can be easily reduced to this problem by setting $c(v) = 2$ for every vertex $v$. – j_random_hacker Jan 17 '18 at 14:23
• $c(v)$ is How many Trees can have vertex $v$ in common. If two trees have two consecutive vertices $v_{1}, v_{2}$ and edge $e_{1,2}$ in common then and then none of these two vertices will have out degree = in degree. – Neel Basu Jan 17 '18 at 14:36
• Trees plural? The problem statement in your first paragraph says "find a Steiner Tree". – j_random_hacker Jan 17 '18 at 14:40
• Hm that's wrong I think, I have to reconsider the question. I was talking in terms of those two references. I was thinking K steiner trees will actually merge into a single Steiner tree. That's why I said a tree. – Neel Basu Jan 17 '18 at 15:04
• I don't understand the problem, so I have no idea. I haven't (and won't) dig up and read the references you give to try to better understand a problem statement that you can't be bothered trying to state clearly yourself. – j_random_hacker Jan 17 '18 at 15:18

## 1 Answer

But this does not imply any constraint on $|N_i|$ which makes me believe that it is NP-complete for $|N_i|=2$ as well. Am I correct?

No, not necessarily. Just because a problem is NP-complete, doesn't mean it will remain NP-complete when you add some restriction to the set of instances (inputs).

Example: Graph coloring is NP-complete. 2-colorability is not. In other words, the following problem is NP-complete:

• Given an undirected graph $G$ and an integer $N$, determine whether the graph $G$ can be colored using $N$ colors.

However, it is not NP-complete for the special case $N=2$.