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 [1]. So it holds for DAGs.
In this paper [1] 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.