Let $G=(V,E)$ be a DAG. For each $v\in V$ you have a color $c(v): V \rightarrow \left\{c_1 \ldots c_k \right\}$ where $k$ is a fixed number, and a weight $p(v)$. For every $v \in V$ you have to find its descendant that has the same color and the lowest weight.

The problem requires an algorithm that runs in linear time.

A naive approach would use a search in topological order but that has $O(n^2)$ running time because you should perform it for every node.

Another idea could be reverse edges and do a visit starting from the sink. Then you may mantain a map that keeps updated the lowest encountered $p(v)$ corresponding to each color $c_k$, and assign the correct value to every discovered $v$. But what if there are more sinks?

Any suggestion to do this in linear time?


I'm wondering if the following may work (to simplify it keeps the lowest p(v) and not the node itself):

merge(src, dest)
  for i = 1 to k
    if src[c_i] < dest[c_i] then dest[c_i] = src[c_i]

  map = [] array of k infinities
  for (v,u) in E do
    if visited(u) = false then
      map_u = visit(u, E, G)
      merge(map_u, map)
      map_u = maps(u)
      merge(map_u, map)
    end if
  end for
  maps[v] = copy of map
  cost[v] = map[c(v)]
  if p(v) < map[c(v)] then map[c(v)] = p[v]
  return map

  visited = new array of |V| elements
  for each v in V do: visited(v) = false
  for each v in V do:
    if visited[v] = false then visit(v, V, E)
  end for
  • $\begingroup$ If $n$ is the number of vertices, then it's somewhat doubtful that linear time suffices, since you might have to go over all edges, and there could be many of them. $\endgroup$ Jan 23, 2016 at 22:47
  • 1
    $\begingroup$ @YuvalFilmus text is vague about this, it says that has to be linear respect to the size of the graph, so $O(|V|+|E|)$. I think one could keep a map in any node $v$ to summarize, at that point, min. discovered descendant weights for each color. For example, using DFS. If the search encounters already visited node, just use its associated map and return to source. However if think i'm missing something. $\endgroup$
    – kentilla
    Jan 23, 2016 at 23:55
  • $\begingroup$ @RickyDemer yes, i'm interested in a solution assuming k is costant (used the term "fixed" probably incorrect). Can this simplify and bring to a linear time solution? In which way? $\endgroup$
    – kentilla
    Jan 24, 2016 at 7:35
  • $\begingroup$ ... Oh ... I read your question too quickly and somehow missed that. ​ (Your use of "fixed" is fine.) ​ ​ ​ ​ $\endgroup$
    – user12859
    Jan 24, 2016 at 8:18
  • $\begingroup$ Either DFS or a topological sorting framework works. Actually, Tarjan's algorithm for topological sorting is based on DFS. You can follow the DFS framework to solve your problem. $\endgroup$
    – hengxin
    Jan 24, 2016 at 11:38


Your Answer

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

Browse other questions tagged or ask your own question.