0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Soumya Basu
    Jun 12, 2015 at 22:05
  • $\begingroup$ 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. $\endgroup$
    – Soumya Basu
    Jun 17, 2015 at 9:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.