<p>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 <strong>L-length bounded minimum cardinality cut on DAGs is NP hard</strong>. </p>

CC BY-SA 3.0
2015-06-17T09:11:04.763Z
2015-06-17T09:11:04.763Z
Soumya Basu
<p>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 <strong>L-length bounded minimum cardinality cut</strong> problem on DAGs. It can naturally be extended to all directed graphs. </p>

<p>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 <strong>L-length bounded min-cut</strong>.  </p>

<p>The <strong>L-length bounded min-cut</strong> 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 <a href="http://kam.mff.cuni.cz/~kolman/papers/acmlcuts.pdf" rel="nofollow">[1]</a>. So it holds for DAGs.</p>

<p>In this paper <a href="http://kam.mff.cuni.cz/~kolman/papers/acmlcuts.pdf" rel="nofollow">[1]</a> it is showed that for directed graphs <strong>L-length bounded minimum cardinality cut</strong> itself is NP hard to have an 1.1377 approximation.</p>

<p>1) Does there exist NP hardness result for <strong>L-length bounded minimum cardinality cut</strong> on DAGs?</p>

<p>Or, </p>

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

<p>References: </p>

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

CC BY-SA 3.0
2015-06-12T22:05:17.577Z
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
CC BY-SA 3.0
2015-06-17T09:12:53.723Z
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
<cc.complexity-theory><graph-algorithms><max-flow-min-cut>
Length bounded minimum cardinality cut in DAGs
Soumya Basu
# Length bounded minimum cardinality cut in DAGs

(Asked by: username_0 on 2015-06-12)

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]](http://kam.mff.cuni.cz/~kolman/papers/acmlcuts.pdf). So it holds for DAGs.

In this paper [[1]](http://kam.mff.cuni.cz/~kolman/papers/acmlcuts.pdf) 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.

**Tags:** cc.complexity-theory, graph-algorithms, max-flow-min-cut

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_0 on 2015-06-17. Score: 1 | Accepted 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**.


---

