# How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

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.

• What do you think? Have you tried any ideas? Can you solve it using a slower algorithm? – Yuval Filmus Feb 23 '18 at 11:59
• Dear Yuval Filmus, I have not found an algorithm to solve it optimally even with nonlinear computation time. – John Bai Feb 23 '18 at 15:31
• Have you tried showing that it's NP-hard? – Yuval Filmus Feb 23 '18 at 17:05
• What's a "leaf vertex"? Is that a sink, i.e., a vertex with no outgoing edges? What does "total number of the leaf vertices connected by the m paths" mean? Can you edit the question to explain all of these more clearly? – D.W. Feb 23 '18 at 17:11
• @Yuval Filmus For DAG with a single source (root) vertex, the longest path problem can be optimally solved within linear computation time. At the moment, I think the DAG with multiple source vertices can also be solved within linear computation time. On the other hand, to verify whether the problem is NP-hard, I need to find the most complex scenario of the problem and check whether it could be solved within linear computation time. – John Bai Feb 23 '18 at 17:39