I am trying to solve the exercise 3.3 in Approximation Algorithms by Vazirani, pg 34. It states

3.3 Give an approximation factor preserving reduction from the set cover problem to the following problem, thereby showing that it is unlikely to have a better approximation guarantee than $O(\log{n})$.

Problem 3.14 (Directed Steiner tree) $G = (V,E)$ is a directed graph with nonnegative edge costs. The vertex set $V$ is partitioned into two sets, required and Steiner. One of the required vertices, $r$, is special. The problem is to find a minimum cost tree in $G$ rooted into $r$ that contains all the required vertices and any subset of the Steiner vertices.

My (related) questions

  1. How do we define a tree in a directed graph? I searched on the Internet and found that a tree is defined for only undirected tree, in particular on Wikipedia.
  2. What does it mean "rooted into $r$"? Does it mean out-degree of $r$ is zero?

Sometime there isn't a completely agreed upon meaning of terms, it is more useful to look at the context to see which definition is appropriate.

In this case, instead of searching for definition of general directed tree, it is better to look for directed steiner tree.

A quick search pulled up this paper which has this diagram showing an example of directed steiner tree:

enter image description here

While not explicitly defined, it coincides with my intuition of what a default directed tree should look like --- A directed graph with exactly one directed path from a distinguished root vertex to any other vertex in the graph (tree).

  • 1
    $\begingroup$ It's not 'any' vertex. It's the tree representing the shortest path from the root to each terminal vertex. Notice that 2 vertices are not traversed. $\endgroup$ – Stephan Dec 22 '17 at 2:27
  • $\begingroup$ And how about "rooted into $r$"? $\endgroup$ – HardFork Dec 22 '17 at 5:32

A tree is defined as an acyclic graph. Meaning there exists only one path between any two vertices.

In a steiner graph tree problem, the required vertices are the root, and terminals. The optimal tree will be the lowest cost tree which contains exactly one path between the root vertex, and each terminal vertex.

Tree(graph theory)

Steiner Tree Problem

  • 1
    $\begingroup$ But there are acyclic graphs which have two different paths between the source vertex and sink vertex. For example imagine a rhombus-like graph with all $outdeg(source)=2, outdeg(sink)=0$ and $outdeg(v)=1$ for all other $v$s. Is it a graph in this case? I think your definition should be amended as "a DAG with exactly one path between any two vertices". Bu this time "DAG" is redundant. $\endgroup$ – HardFork Dec 22 '17 at 5:56
  • $\begingroup$ Acyclic graphs with more than one path between any two vertices are not trees. Trees are also technically undirected. $\endgroup$ – Stephan Dec 22 '17 at 13:14
  • $\begingroup$ The problem is to find an optimal tree from a DAG $\endgroup$ – Stephan Dec 22 '17 at 14:09

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.