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. 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 graphhttps://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-nodesINSTANCE: 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.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 ?
General Steiner Tree Variants
graph theory;linear programming