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.
<PERSON>, B., <PERSON> and <PERSON>, "Steiner Trees in VLSI-layout", in Paths, Flows, and VLSI-Layout, Korte, B., <PERSON>, <PERSON> and <PERSON> (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 <PERSON> 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. 835
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] <PERSON>, <PERSON>, and <PERSON>. "Minimum-Cost Node-Disjoint Steiner Trees in Series-Parallel Networks." VLSI Design 4.1 (1996): 53-57.
[2] <PERSON>, <PERSON>, and <PERSON>. "Hardness and approximation results for packing Steiner trees." Algorithmica 45.1 (2006): 21-43. 433