Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path connecting a maximal number of target vertices is the longest path problem in a DAG, which can be optimally solved within linear computation time. At the moment, the un-weighted DAG has m source (root) vertices. The objective is to find m directed paths where each path originates from one unique source vertex such that the total number of the target vertices connected by the m paths is maximal. Each target vertex and each edge can be passed multiply by the m paths. However, when counting the number of the connected vertices, the multiply visited target vertex just be treated as one single target vertex.
I want to know whether and how the above mentioned problem can be optimally solved within linear computation time. Thanks for your answer.