# Min-cut with maximal number of edges

I’ve searched for a solution for this problem for some time now, it is out of an algorithm question sheet.

We know that in order to find the minimal amount of edges in a flow graph’s min-cut we need to find the maximal flow, $$c_o$$,set the capacity of the edges of the min-cut to $$1$$ and for for the rest $$e\in E$$ set $$c(e)=c(e)\cdot (|E|+1)+1$$ and find the max flow $$c_n$$ in the new graph such that $$c_n=c_o\cdot (|E|+1)+k$$, in which $$k$$ is the minimal number of edges in the graph’s min-cut.

Our problem is about finding the maximal number of edges in a graph’s min-cut.

Deducting one instead of adding would have the same effect, hence I’ve thought that perhaps if we add some number $$\epsilon \in \mathbb{R}$$ until the max flow increases, that could tell us something.

However I got stuck in that thought, unable to find ways on how to progress.

Here is a simple algorithm that is based on your idea to reduce the capacity function.

Suppose the given flow network is directed graph $$G=(V,E)$$ with source $$s$$, sink $$t$$ and capacity function $$c$$.

Let $$\epsilon>0$$ be a constant that is small enough. Consider a new capacity function $$c^-$$ that is $$\epsilon$$ less than $$c$$, i.e., $$c^-(e)=c(e)-\epsilon$$ for each edge $$e$$.

Let $$\mathcal C_1$$ and $$\mathcal C_2$$ be two $$s$$-$$t$$ cuts of $$G$$. Abusing the notations $$c$$ and $$c^-$$, let

• $$c(\mathcal C_1)$$ and $$c^-(\mathcal C_1)$$ be the capacity of $$\mathcal C_1$$ wrt to $$c$$ and $$c^-$$ respectively.
• $$c(\mathcal C_2)$$ and $$c^-(\mathcal C_2)$$ be the capacity of $$\mathcal C_2$$ wrt to $$c$$ and $$c^-$$ respectively.

Let $$\|\mathcal C_1\|$$ be the number of edges in $$\mathcal C_1$$ i.e. in the cut-set of the $$s$$-$$t$$ cut $$\mathcal C_1$$ (which are the edges that start with nodes in the part of $$\|\mathcal C_1$$ that contains $$s$$ and end with nodes in the other part of $$\|\mathcal C_2\|$$ that contains $$t$$). We have $$\|\mathcal C_2\|$$ similarly.

Claim: $$c^-(\mathcal C_1) $$\iff$$ either $$c(\mathcal C_1) or $$c(\mathcal C_1)=c(\mathcal C_2)$$ and $$\|\mathcal C_1\|=\|\mathcal C_2\|$$.
Proof: $$c^-(\mathcal C_1)=c(\mathcal C_1)-\|\mathcal C_1\|\epsilon$$.
$$c^-(\mathcal C_2)=c(\mathcal C_2)-\|\mathcal C_2\|\epsilon$$.
$$c^-(\mathcal C_1)-c^-(\mathcal C_2)= c(\mathcal C_1)-c(\mathcal C_2)-(\|\mathcal C_1\|-\|\mathcal C_2\|)\epsilon.$$ Since $$\epsilon>0$$ is small enough and $$-|E|<\|\mathcal C_1\|-\|\mathcal C_2\|<|E|$$, the claim is true.

The claim means any min-$$s$$-$$t$$-cut wrt to $$c^-$$ must be a min-$$s$$-$$t$$-cut wrt to $$c$$ with the maximum number of edges. In other words, the maximum number of edges in any min-$$s$$-$$t$$-cut of the flow network $$(G,c)$$ is the number of edges in a min-$$s$$-$$t$$-cut of the flow network $$(G, c^-)$$.

So we have the following algorithm.

1. Construct $$c^-$$ such that $$c^-(e)=c(e)-\epsilon$$ for a small-enough constant $$\epsilon>0$$.
2. Compute a min-$$s$$-$$t$$-cut of $$G$$ wrt to $$c^-$$. Return the number of edges in it.

There are two ways to implement step 1.

• If $$c$$ is integer valued, we can choose $$\epsilon=\frac1{|E|}$$.
• In all cases, we can represent the scalar capacity $$c(e)$$ as vector $$(c(e),0)$$. Let $$\epsilon=(0,1)$$. $$c^-(e)=(c(e),-1)$$. Use the natural arithmetic and comparison order for the vectors. In this way, $$\epsilon$$ is realized as an "infinitesimal positive" capacity.

The time-complexity of the algorithm is about the same as the time-complexity to compute a max-flow of a flow network, such as $$O(VE^2)$$ for Dinic's algorithm.

• I completely trust that this algorithm is correct, however I cannot wrap my head around that just because the new capacity of the min cut is $x-\epsilon k$ then we have $k$ edges as the maximal amount of edges in a min-cut of $G$, care to share further intuition? I’m asking this because I’m uncertain about the characteristics of a graph’s min cut, it’s reasonable to think that there are several (exponential amount) of min cuts who all have the same flow (the maxflow) and only some/single has the max amount of edges crossing it. Jan 31 at 14:27
• However I cannot understand the idea of how from choosing a random min cut (which we got after finding the max flow) we’re able to find the maximal amount of edges in a min cut, out of all possible min cuts Jan 31 at 14:30
• @Aishgadol Is my updated answer clear for you? Jan 31 at 18:53
• You have made it alot clearer, thank you for your time and effort, this is truley mind-opening information. Jan 31 at 19:01