-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – j_random_hacker Jan 17 '18 at 14:23
  • $\begingroup$ $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. $\endgroup$ – Neel Basu Jan 17 '18 at 14:36
  • $\begingroup$ Trees plural? The problem statement in your first paragraph says "find a Steiner Tree". $\endgroup$ – j_random_hacker Jan 17 '18 at 14:40
  • $\begingroup$ 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. $\endgroup$ – Neel Basu Jan 17 '18 at 15:04
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Jan 17 '18 at 15:18
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.