3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you think? Have you tried any ideas? Can you solve it using a slower algorithm? $\endgroup$ – Yuval Filmus Feb 23 '18 at 11:59
  • $\begingroup$ Dear Yuval Filmus, I have not found an algorithm to solve it optimally even with nonlinear computation time. $\endgroup$ – John Bai Feb 23 '18 at 15:31
  • $\begingroup$ Have you tried showing that it's NP-hard? $\endgroup$ – Yuval Filmus Feb 23 '18 at 17:05
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 23 '18 at 17:11
  • $\begingroup$ @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. $\endgroup$ – John Bai Feb 23 '18 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.