# Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is:

Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$.
Question: Is there an $s$-$t$ cut of capacity at most $k$?

Obviously, the problem is in P by standard methods. When trying to logspace reduce the P-complete LP-optimization problem, I encountered the following problems:

• If the LP problem has no feasible solution, then $t$ should not be reachable from $s$. In this case, checking whether an LP problem has a feasible solution would be quite simple (don't know whether this is true).
• If the LP problem is unbounded, then the min-cut should be unbounded as well. This could possibly be the case if $s$ and $t$ are identical. Again, checking whether an LP has an unbounded solution would be even easier.

For the lower bound, NL-hardness is quite easy: For a given directed graph $G$ with nodes $s$ and $t$, just take $G$ as a flow network and assign capacity 1 to each edge. Then ask if there is an $s$-$t$ cut of capacity at most 0. $t$ is reachable from $s$ if and only if the answer to this question is no. Since coNL=NL, we are done.

Moreover, the problem is NL-complete for outerplanar graphs. For this, $s$ and $t$ are joined by an edge of infinite capacity. This edge creates the two new faces $f_1$ and $f_2$. Now, answer the question whether there is a path of length at most $k$ from $f_1$ to $f_2$ in the dual graph.

I do not see how to generalize this to general graphs nor how to overcome the problems described when reducing LP optimization.

• Have you tried reducing a known P-complete problem to it, e.g. LP optimisation? What else have you tried (but searching)? – Raphael Jul 24 '14 at 17:55

The reduction gets an Alternating Monotone Fanin 2, Fanout 2 CVP instance (a circuit $C$) and creates a flow network $N$ that allows a max flow of value $D 4^{k-1}$ where D is the number of input gates in $C$, iff $C$ evaluates to 1.
The idea is to construct the network by creating two nodes $(i,x,0)$ and $(i,x,1)$ for each gate $(i,x)$ (gate $x$ on the $i$th layer in $C$, one for each possible value 0 and 1). The input layer is layer 0. The source of $N$ is connected to $(0,x,0)$ ($(0,x,1)$) with capacity $4^k$ iff $(0,x)$ is a constant 0 (1) in $C$. Each edge $((i,x),(i+1,y))$ of $C$ is then replaced by a small subnetwork which sends 3/4 of the flow directly to the sink. The remaining quarter is sent to $(i+1,y,0) ((i+1,y,1))$, if $x$ in $C$ values to 0 (1). (At least the max flow needs to take these routes. Hence these small subnetworks simulate the gates.)
Now, the output gate $(k,x)$ is copied as well, but only the $(k,x,1)$ copy is connected to the edge. That is: Iff $C$ evaluates to 0, then exactly 1 flow unit cannot be sent to the sink. Hence, the flow in $N$ is $D 4^{k-1}-1$. If $C$ evaluates to 1, then the full $D 4^{k-1}$ flow units can reach the sink. This completes the reduction.