0
$\begingroup$

Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value of $f(u)$, among all vertices $u$ that are reachable from $v$, and save it a an attribute of v. The time complexity of the algorithm needs to be $O(V+E)$ (assuming that time complexity of $f(v)$ is $\Theta (1)$).

I thought about using DFS (or a variation of it) and/or topological sort, but I don't know how to use it in order to solve this problem.

In addition, I need to think about an algorithm that gets an undirected graph and the function $f(v)$, and calculate the same thing for every vertex, and I don't know how to do it either.

$\endgroup$
1
  • $\begingroup$ For a connected undirected graph, all vertices are reachable from every other vertex. So every vertex would have the same minimum reachable value right? $\endgroup$ Dec 13 '20 at 12:07
0
$\begingroup$

Yes, you can use the topological sort. Suppose topological sorting of the vertices gives you the sequence: $v_{1}, \dotsc, v_{n}$ such that there is no edge of the form $(v_{j},v_{i})$ for any $i < j$.

Following would be the pseudocode to compute the minimum reachable $f(u)$ value for each vertex $v_{i} \in V$:

fun()
----- int min_val_reachable[n];    // array that stores minimum reachable f(u) value for each vertex

----- for(i = n to 1; i--)
-------- min_val_reachable[i] = f(v_i) // since a vertex v_i is reachable to itself
-------- for each vertex 'u' in adj_list[v_i]
-------------- if (min_val_reachable[i] > min_val_reachable[u])
-------------------min_val_reachable[i] = min_val_reachable[u]
-------------- end
--------- end
----- end
----- return min_val_reachable[];

The time complexity of the topological sort is $O(|V| + |E|)$, and the time complexity of the above procedure is also $O(|V| + |E|)$. Thus, the overall complexity is $O(|V| + |E|)$.


You can prove the correctness of the above procedure using the induction technique as follows:

Hypothesis: After $t$ iterations of the outer "for loop", we get the correct min_value_reachable[] for every vertex from $v_{n}$ to $v_{n-t+1}$

Base Case: For $t = 1$, it is easy to see that min_value_reachable[$v_n$] = $f(v_n)$ since $v_{n}$ does not has any child, and $v_{n}$ is reachable to itself.

The induction case is also simple. Hope you can figure out the details yourself.

$\endgroup$
0
$\begingroup$

Given a vertex $v$, let $F(v)$ be the minimum value $f(u)$ among all nodes $u$ reachable from $u$ in the input DAG $G=(V,E)$.

Notice that a vertex $u$ is reachable from $v$ if and only if $u=v$ or $u$ is reachable from some out-neighbor $w$ of $v$. Then, we can write:

$$ F(v) = \min\{ f(v), \min_{(v,w) \in E} F(w) \}, $$ where the minimum of over an empty range is $+\infty$.

Let $v_1, \dots, v_n$ be the vertices of $G$ in reverse topological order, and notice that the previous equation for $F(v_i)$ only depends on $f(v_i)$ and on the values $F(v_j)$ with $j<i$.

If we compute $F(v_1), F(v_2), \dots, F(v_n)$ in this order, then we will only need time proportional to the out-degree $\delta_i$ of each $v_i$. More precisely, we will spend time $O( 1 + \delta_i)$ to compute $F(v_i)$. Since $\sum_{i=1}^n ( 1 + \delta_i) = |V| + |E|$, the overall time complexity is also $O(|V| + |E|)$.

If the graph $G$ is not a DAG then, the same approach works once you preprocess $G$ by identifying all the connected components $C$ into a single vertex $v_C$ having $f(v_C) = \min_{u \in C} f(u)$. This preprocessing requires time $O(|V|+|E|)$, since this is the time required to compute the connected components of $G$ (which are a partition of $G$). In particular this captures the case where $G$ is an undirected graph since it is equivalent to solving the problem using the directed version of $G$: just replace each undirected edge $\{u, v\}$ with the pair of directed edges $(u,v)$ and $(v,u)$.

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