2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

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)<c^-(\mathcal C_2)$ $\iff$ either $c(\mathcal C_1)<c(\mathcal C_2)$ 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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Aishgadol
    Commented Jan 31, 2023 at 14:27
  • $\begingroup$ 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 $\endgroup$
    – Aishgadol
    Commented Jan 31, 2023 at 14:30
  • 1
    $\begingroup$ @Aishgadol Is my updated answer clear for you? $\endgroup$
    – John L.
    Commented Jan 31, 2023 at 18:53
  • $\begingroup$ You have made it alot clearer, thank you for your time and effort, this is truley mind-opening information. $\endgroup$
    – Aishgadol
    Commented Jan 31, 2023 at 19:01

Your Answer

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

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