2
$\begingroup$

I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut theorem (https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem). This makes some sense to me but I'm confused as to what happens in a DAG with unit edge weights. In this case, there's three claims I'm trying to make:

  1. The max flow of a DAG with unit edge weights has an upper bound equal to the sum of the number of edges entering all sinks. In other words, max flow is bounded by the sum of the indegree of all sink nodes.
  2. Because all edges have the same weight, there are $\binom{n}{\text{max flow}}$ possible min-cuts where $n$ is the number of edges. In essence, if the max flow for a DAG is 3, then choosing any 3 edges would give you a min-cut.
  3. If you apply the Ford-Fulkerson to identify a min-cut, it will effectively always include edges connected to the source node because those will immediately have their capacity maxed out and the algorithm returns the cut closest to the source(s).

These feel unintuitive to say the least but seem to hold true for the few small examples I tried to run through. In particular, the second statement seems very wrong to me. It seems to imply that any set of edges with capacity equal to max flow constitute a min-cut. While a min-cut definitely has capacity equal to max flow, I'd guess the reverse statement that any set of cuts with a capacity equal to max flow is a min-cut isn't necessarily true (though I can't quite come up with a counter-example).

My question is, are any of the 3 claims above true?

Edit:

After thinking about it some more, I think I found a counterexample to my 2nd claim. In the DAG below, the max flow is 2 but cutting any two of the dotted edges wouldn't yield a partition.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ What is your question? Could please edit your post and include your question? If you claim that something is incorrect please include the reason why it is incorrect. $\endgroup$ – fade2black Sep 7 '17 at 1:08
  • $\begingroup$ Sorry, I updated the question. What I'm really hoping for is some general information surrounding the idea of a min-cut in DAGs with unit edge weights. I thinking getting answers to whether or not the above statements are true (or not) would help me with this. $\endgroup$ – jaip Sep 7 '17 at 1:23
2
$\begingroup$

Your first claim is true.

As for the second consider the following counterexample. Consider the following DAG with edges $(s,v_1),(v_1,v_2), (v_1,v_3), (v_2,t), (v_3,t)$, where $s$ is the source and $t$ is the sink

                 (v2)
                 /  \
                /    \
        (s)-->(v1)   (t) 
                \    /
                 \  /
                 (v3)

There is only one mincut while according to your claim there are $\binom{5}{1} = 5$. So your second claim is false.

For the third claim consider the following DAG with edges $(s,v_1),(s,v_2), (v_2,v_3), (v_1,v_3), (v_3,t)$

                 (v2)
                 /  \
                /    \
              (s)   (v3)---->(t) 
                \    /
                 \  /
                 (v1)

The Ford-Fulkerson (or any other) algorithm should find min-cut as the only edge $(v_3,t)$ which is not connected to the source. The the third claim is false.

$\endgroup$
  • $\begingroup$ Ok thank you, that's pretty helpful to me. Couple follow up questions. Is the 3rd claim true if the source node has the same outdegree as the indegree of the sink? In that case, it seems like the edges leaving the source node would serve as bottleneck. Second, does the 1st claim generalize to multi-source multi-sink DAGs? $\endgroup$ – jaip Sep 7 '17 at 2:12
  • $\begingroup$ In fact, the Ford-Fulkerson "algorithm" is a method which has several implementations. Basically, this algorithm computes the maximum flow. The minimum-cut then can be computed using the final residual network. Here is an example. So it fully depends on your implementation. $\endgroup$ – fade2black Sep 7 '17 at 2:42
  • $\begingroup$ As for the second question, you could easily transform the multi-sink graph into a single-sink graph. $\endgroup$ – fade2black Sep 7 '17 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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