# DAG, search for cheapest descendants with same color

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?

Edited

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]

visit(v,E,G)
visited[v]=true
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)
else
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

search(V,E)
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

• 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. Jan 23, 2016 at 22:47
• @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. Jan 23, 2016 at 23:55
• @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? Jan 24, 2016 at 7:35
• ... Oh ... I read your question too quickly and somehow missed that. ​ (Your use of "fixed" is fine.) ​ ​ ​ ​
– user12859
Jan 24, 2016 at 8:18
• 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. Jan 24, 2016 at 11:38