# 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. – Soumya Basu Jun 12 '15 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. – Soumya Basu Jun 17 '15 at 9:12

## 1 Answer

The paper mentioned in the question uses a reduction from Vertex Cover problem to show that the length bounded cut problem is NP Hard. The instance they construct given an instance of vertex cover, is nothing but a DAG. In this case all the edge has unit weight which corresponds to the minimum cardinality case. Therefore, the problem of L-length bounded minimum cardinality cut on DAGs is NP hard.