Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it?

I'd be interested if there are FPT algorithms as well, or even run time in O(n^k).

I'm aware that if there are no length restrictions and we're given two target nodes this is in P, using network flow.

It has some connections to Digraph Ordering (see Kenkre's recent paper) in terms of establishing upper bounds.

One way to begin to approach the problem is to define an LP which maximizes the sum of 0-1 path variables, and ensures no two paths given value 1 overlap. (If we're a little careful we can do this with polynomially many constraints) However, we have to round our solution to get anywhere.

  • $\begingroup$ Have you researched this? What have you found so far? We're not librarians, we're here to assist if you can't get your algorithm to work. $\endgroup$ – Adam B Feb 2 '16 at 4:37
  • $\begingroup$ @adam-b I haven't been able to find anything on this problem -- I was hoping someone else knew about it (maybe it has a name I'm not aware of, for example). I added a few notes in the main post in case they're helpful. $\endgroup$ – Nathan Feb 2 '16 at 4:45
  • $\begingroup$ I'd actually take this one straight to cstheory -- more expertise of the sort needed there than on cs. If this is a practical problem, though, you might do well by trying to solve the integer program with standardish techniques. $\endgroup$ – David Eisenstat Feb 2 '16 at 13:53
  • $\begingroup$ @Zach-Langley Thanks for the response! I'm not sure I quite see. Couldn't we take the same edge more than once in different copies of the graph? For example, for k=3 and a line graph A->B->C->D, we could take the paths A->B->C, as well as B->C->D, since these involve disjoint edges in the copied graphs (however, clearly these paths aren't edge disjoint). Let me know if I misunderstood. $\endgroup$ – Nathan Feb 2 '16 at 19:52
  • $\begingroup$ The case $k=1$ can be solved in polynomial time, using a non-trivial algorithm. (It's just maximum matching.) $\endgroup$ – Yuval Filmus Feb 2 '16 at 19:56

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.