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.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top