8
$\begingroup$

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?
Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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, 2017 at 2:27
  • $\begingroup$ And how about "rooted into $r$"? $\endgroup$
    – HardFork
    Dec 22, 2017 at 5:32
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 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, 2017 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, 2017 at 13:14
  • $\begingroup$ The problem is to find an optimal tree from a DAG $\endgroup$
    – Stephan
    Dec 22, 2017 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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