2
$\begingroup$

In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all vertices of S. There are two versions of the problem: in the optimization problem associated with Steiner trees, the task is to find a minimum-weight Steiner tree.

This is an online compendium on approximability of the Steiner Tree and related optimization problems: http://theory.cs.uni-bonn.de/info5/steinerkompendium/

I am currently studying different Steiner tree variants on Graphs and i had already read Compendium but i haven't found the following cases.

  1. INSTANCE: Graph $G=(V,E)$ , unweighted edges ,given a set of terminals $S\subset V$. SOLUTION: A tree T=(${V_t},E_t$) in G such that $V_t$ number is minimum, $S\subset V_t\subset V, E_t\subset E$.

This problem looks like set cover problem or Vertex Cover for a specified subset of V. Also asked here: Minimal Steiner Tree in unweighted directed graph https://cstheory.stackexchange.com/questions/19477/steiner-tree-problem-for-unweighted-graphs for complexity only. also here: https://stackoverflow.com/questions/3975763/minimum-connected-subgraph-containing-a-given-set-of-nodes/ and here: https://stackoverflow.com/questions/10056212/minimum-spanning-tree-between-a-start-location-and-a-set-of-required-nodes

  1. INSTANCE: Graph $G=(V,E)$ , edge weight->$\mathbb{R^+}$ , given a set of terminals $S\subset V$, node weight->R+. SOLUTION: A tree T=(${V_t},E_t$) in G such that T Prize(node and edge weights) is maximum and number of edges is minimum (Ratio:NodesWeights/NumberEdges) , $S\subset V_t\subset V, E_t\subset E$. (maximum path with minimum hopes-jumbs-edges).

This problem looks like Prize-Collecting Steiner Tree Problem.

  1. INSTANCE: Graph $G=(V,E)$ , edge weight->$\mathbb{R^+}$ , given a number for terminals $S\subset V$, where each S is adjacent to at least one other S, node weight->R+. SOLUTION: A tree T=(${V_t},E_t$) in G such that T Prize(node and edge weights) is maximum ,$S\subset V_t\subset V, E_t\subset E$.

I want to know if any of these cases can be transformed into already known cases or if they are already exists. Are all of them Np ?

$\endgroup$
  • $\begingroup$ 1. What do you mean by "can be transformed into already known cases or if they are already exists"? Is your real question: Are all of these problems in NP? If so, you should probably be asking as 3 separate questions -- one question per question, please. 2. What is the definition of "$V_t$ number"? 3. What is the definition of "T Prize"? What is meant by "Ratio:NodesWeights/NumberEdges"? "hopes-jumbs-edges"? 4. Your problem #2 is not well-defined; we might not be able to simultaneously maximize one objective function and minimize another. $\endgroup$ – D.W. Apr 2 '16 at 0:46
  • $\begingroup$ 1. For example if we split edge weight to start and end nodes than we have node weights only. etc . Maybe it can be with those problems. Furthermore i want to know if all of them variants of Stainer tree are in NP. 2. When i am writting $V_t$ number means the number of nodes of the steiner tree. $\endgroup$ – a.s.p. Apr 2 '16 at 12:43
  • $\begingroup$ 3. The Prize-Collecting Steiner Tree Problem (PCST) on a graph : siam.org/meetings/alenex05/papers/06iljubic.pdf . - When i am writting Ratio:NodesWeights/NumberEdges . For example. points-nodes: a.weight=5 b.weight=4 c.weight=2 d.weight=2 . So if you have to paths that connects two terminals t1 and t2: path1: t1 -> a - > d-> t2 . path2: t1-> b-> c-> t2 . then the algorithm has to selects path1. $\endgroup$ – a.s.p. Apr 2 '16 at 12:43
  • $\begingroup$ Please restrict yourself to one question per post. $\endgroup$ – Raphael Jun 8 '16 at 11:19
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 8 '16 at 11:19

Your Answer

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

Browse other questions tagged or ask your own question.