# Questions tagged [max-flow-min-cut]

The tag has no usage guidance.

41 questions
Filter by
Sorted by
Tagged with
152 views

### Minimum cut with size bounds $k\leq |S| \leq |V|-k$

It is known by the max flow min cut theorem that the minimum cut problem is in $P$. I am interested in knowing what is known on the complexity of the minimum cut with size $k\leq |S| \leq , |V|- k$. ...
133 views

### Finding vertex separator such that the induced subgraph has minimal number of edges

My problem is related to edge and vertex cuts with a little twist. Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
169 views

### How to find the second smallest cut in a graph?

For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, ...
84 views

### Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
54 views

### polytime approximability of directed multicut

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
147 views

### Interval partitioning with restrictions: NP-complete or efficiently solvable?

The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ...
226 views

### Max flow with restriction of individual flows

What is known about the complexity of solving max flow with restrictions on individual flows for some nodes? More precisely, in addition to wanting the max flow, you have a constraint for some ...
69 views

### Space complexity of global minimum cut

Are there any non-trivial bounds on the space complexity of global minimum cut? The problem is known to be in $\mathsf{RNC}$. Is anything known about containment in either $\mathsf{L}$ or $\mathsf{NL}$...
364 views

71 views

### Sparse-cut approximation for well connected graphs

Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$. If I understand UGC correctly, ...
317 views

### expected number of edges for fixed min cut

It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges. Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
270 views

### generate a graph with fixed min cut

Is there a constructive way to generate a graph with a fixed min cut equal to $k$? One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to ...
941 views

### Minimum vertex k-cut

Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at ...
91 views

### Name of graph partition that balances edges between sets with edges remaining within sets

Is there a common name for this problem: Let G=(V, E) be an undirected graph. Partition V into sets $S_1$, $S_2$, ..., $S_k$, such that (the number of edges between sets) + (the number of "non"-...
93 views

### Minimum cost flow with Demand and Edge Capacity scaling

Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ ...
188 views

### Length bounded minimum cardinality cut in DAGs

Suppose I have a DAG with non-negative edge lengths. The problem is to compute the minimum number of edges which disconnects all paths of length L or less. We call this L-length bounded minimum ...
102 views

### Multicuts composed of Min-Cuts

Multicuts or multiway cuts are (edge) cuts of minimum capacity that separate each pair of a set of terminals (a subset of the entire node set). For two terminals, this is the classical $s$-$t$ mincut ...
654 views

### Second Smallest $s$-$t$-Cut in a Network

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem: Input: A network $N$ and a number $k$, all in binary. Output: A $k$th smallest $s$-...
333 views

### Maximum flow for all edges in an undirected graph

I was wondering if the following problem has been studied in the past, and what are some of the best ways people can come up with to solve it: Let $G=(V,E)$ be an undirected graph, which we use as a ...
118 views

### Characterizing the set of problems solvable via network flow

What are some ways to prove that a certain problem cannot be solved using Network Flow (NF)? One way is to prove the problem is NP-hard. But NF has substantial structure -- is there some symmetry or ...
203 views

154 views

### Indexing structure for all-pairs min-cuts in a huge DAG

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution. Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive ...
430 views

### karger's algorithm contracting nodes not edges [closed]

Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge). Is there a reason why this is so?
557 views

### Weighted vertex-connectivity; global min vertex-cut

I am interested in the following problem: Input: a connected undirected graph $G=(V,E)$; a positive weight for each vertex. Output: a minimum weight subset of $V$ whose removal disconnects $G$. When ...
12k views

### Fastest way to find an s-t min-cut from an s-t max-flow?

Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity. How could I use a sparse s-t flow to find an s-t min-cut in time ...
126 views

### Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

If we want a specific example, then how about the Erdos-Renyi random graph?
424 views

### Increasing the capacity to maximize the min cut

Consider a graph with all edges having unit capacity. One can find the min cut in polynomial time. Suppose I am allowed to increase the capacity of any $k$ edges to infinity (equivalent to merging ...
3k views

### Can I get all min-cuts after executing Push-Relabel?

The push-relabel algorithm (here is push-relabel as pseudo-code) assigns a distance-label to each node. After executing push relabel, you have those distance labels and a max flow in a given network ...
190 views

### Edge Cut of interval graphs

On interval graphs, minimal vertex separators are well understood: they are cliques, there are no more than $n$ ones. However, when we turn to the minimal edge cut, my search found no even one single ...
267 views

### Request for references on multicommodity flow-cut results

This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...
290 views

### Graph connectivity related game [closed]

I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
163 views