Tweeted twitter.com/StackCompSci/status/694927101510684674
3 edited tags
| link
2 added 5 characters in body
source | link

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.

Is it known if the problem of finding the maximum number of 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.

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.

    Post Migrated Here from stackoverflow.com
1
source | link

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of 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.