Questions tagged [max-flow-min-cut]
The max-flow-min-cut tag has no usage guidance.
42
questions
1
vote
0
answers
168
views
Easier famility of graphs for MAXCUT [closed]
I would like to know if there are particular family of graphs for which the Goemans-Williamson MAXCUT Approximation Algorithm renders higher than 0.878 approximation ratio. TIA
- 997
2
votes
1
answer
192
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$. ...
- 680
8
votes
1
answer
176
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 ...
- 183
5
votes
0
answers
219
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$, ...
4
votes
0
answers
86
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 ...
- 454
1
vote
0
answers
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 ...
- 21
3
votes
1
answer
198
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. ...
1
vote
2
answers
232
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 ...
- 680
1
vote
0
answers
75
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}$...
- 429
1
vote
1
answer
428
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,......
- 111
2
votes
0
answers
212
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 ...
- 639
1
vote
0
answers
165
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 ...
- 639
1
vote
0
answers
72
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, ...
- 771
2
votes
0
answers
318
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$ ...
- 41
2
votes
1
answer
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 ...
- 41
6
votes
0
answers
994
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 ...
- 61
2
votes
2
answers
100
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"-...
- 123
1
vote
0
answers
94
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$ ...
- 171
0
votes
1
answer
192
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 ...
- 171
1
vote
0
answers
104
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 ...
- 439
14
votes
1
answer
700
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$-...
- 439
2
votes
1
answer
348
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
1
answer
120
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 ...
- 133
2
votes
0
answers
203
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 all $s$-$...
- 439
8
votes
0
answers
668
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 ...
- 1,120
0
votes
1
answer
145
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
1
vote
1
answer
721
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 $\...
- 439
5
votes
0
answers
159
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 ...
- 8,641
0
votes
1
answer
451
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
0
answers
602
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 ...
- 1,156
8
votes
2
answers
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 ...
- 735
1
vote
0
answers
129
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?
- 735
9
votes
1
answer
444
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 ...
- 91
6
votes
1
answer
4k
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 ...
- 595
1
vote
0
answers
203
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 ...
- 2,530
8
votes
1
answer
269
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 ...
- 453
3
votes
0
answers
296
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 ...
- 629
4
votes
1
answer
163
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 ...
- 153
15
votes
3
answers
905
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 ...
- 1,100
15
votes
2
answers
4k
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 ...
- 1,933
8
votes
3
answers
9k
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?
- 191
6
votes
3
answers
821
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 ...
- 467