Questions tagged [max-flow-min-cut]
The max-flow-min-cut tag has no usage guidance.
34
questions
1
vote
0answers
54 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}$...
1
vote
1answer
137 views
Minimum graph cut with constraints
Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,......
2
votes
0answers
125 views
Maximum weight non-overlapping paths in a DAG
Suppose we have a weighted DAG $G$. A $m$-path-tuple is defined as $(P_1, ..., P_m)$ in which $P_i$ is a path on the graph, and no $P_i$ and $P_j$ share any edges. In other words each edge of the ...
0
votes
0answers
147 views
Minimum cut on a directed graph with negative term
Suppose we are given a directed Graph $G=(V,E)$ and there is a nonnegative weight $w(u,v)$ is defined for the edge from $u$ to $v$. The task is to partition vertices to $A$ and $B$ (partition means $V ...
1
vote
0answers
59 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, ...
2
votes
0answers
305 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$ ...
2
votes
1answer
234 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 ...
6
votes
0answers
761 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 ...
2
votes
2answers
83 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"-...
1
vote
0answers
84 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$ ...
0
votes
1answer
154 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 ...
1
vote
0answers
98 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 ...
13
votes
1answer
370 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$-...
2
votes
1answer
295 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 ...
3
votes
1answer
105 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 ...
2
votes
0answers
192 views
Characterization of the Set of all s-t-Min-Cut Edge Sets
I would like to know how to answer the following problem:
Input: A family of sets $S$ over a universe $U$.
Question: Is there a directed flow network $N$ with edges $U$ such that the set of ...
8
votes
0answers
430 views
Efficient Reduction from Min Cut to st-Min Cut
I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut.
But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
0
votes
1answer
121 views
Flow networks: Push flow on either edges but not both!
I have a flow network with random capacities on edges, is there some way to add a constraint of the type (push flow on either one of these two edges but not on both)?
I'm not sure if this is correct ...
1
vote
1answer
523 views
Rings and the set of all minimum s-t-cuts
Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let $\...
5
votes
0answers
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 ...
0
votes
1answer
384 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?
6
votes
0answers
450 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$....
8
votes
2answers
11k 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 ...
1
vote
0answers
117 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?
9
votes
1answer
305 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 ...
5
votes
1answer
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 ...
1
vote
0answers
134 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 ...
8
votes
1answer
253 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 ...
3
votes
0answers
278 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 ...
3
votes
1answer
149 views
Primal Dual model in the continuous domain
The continuous max flow problem is posed as follows :
sup $\int_\Omega p_s(x)dx$
subject to :
$|p(x)| \le C(x); \forall x \in \Omega $
$p_s(x) \le C_s(x); \forall x \in \Omega $
$p_t(x) \le ...
15
votes
3answers
852 views
Super Mario Flows in NP?
One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two ...
12
votes
2answers
2k views
Number of mincuts of a graph without using Karger's algorithm
We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.
I was wondering if we could ...
6
votes
3answers
6k views
Minimum cut through vertices/nodes - not edges
we all know and love s-t minimum cut algorithms, but they all cut through the edges in the graph. Are there any variants that cuts through nodes?
6
votes
3answers
607 views
In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial ...
