Q4 - can you explain?
Assuming we can run tasks in parallel as much as we want (depending on the constraints) it seems like we can use dynamic programming after sorting the graph topologically. Something like c(u) = u+max(c(v)) (while (u,v) is an edge in the graph), and then the solution is max(c(u)) while u has no entering edges. The base would be that for every leaf c(v) = t(v), But i'm getting mixed over here and can't find a solution.
Can you shed some light?
Q5 - is this a KMP question (meaning is it not for the test)? How can we recognize KMP questions?