# Length bounded minimum cardinality cut in DAGs

Suppose I have a DAG with non-negative edge lengths. The problem is to compute the minimum number of edges which disconnects all paths of length L or less. We call this L-length bounded minimum cardinality cut problem on DAGs. It can naturally be extended to all directed graphs.

There can be a further generalization where removing an edge has some associated cost. The L-length bounded min cut problem is finding the set of edges with minimum total weight that gives a L-length bounded min-cut.

The L-length bounded min-cut problem is known to be NP hard. In fact for a given budget it is NP hard to decide if there exists a length bounded cut which does not exceed the budget for series parallel graphs . So it holds for DAGs.

In this paper  it is showed that for directed graphs L-length bounded minimum cardinality cut itself is NP hard to have an 1.1377 approximation.

1) Does there exist NP hardness result for L-length bounded minimum cardinality cut on DAGs?

Or,

2) Is there any polynomial time, w.r.t. the number of edges and vertices, algorithm to construct the L-length bounded minimum cardinality cut on DAGs?

References:

1: Baier, Georg, et al. "Length-bounded cuts and flows." Automata, languages and programming. Springer Berlin Heidelberg, 2006. 679-690.

• I decided to go through the construction they use for proving the NP harness for directed graphs. As it turns out it is nothing but a DAG and therefore the hardness results are valid for DAG. Jun 12, 2015 at 22:05
• I have written the answer with some level of details. But for the exact construction is complicated. It is better understood by reading the reference given in the question. Jun 17, 2015 at 9:12