The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
57 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
44 views

max_sat vs min_cut: theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
1
vote
0answers
77 views

Characterization of the Set of all s-t-Min-Cut 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 an edge labeling ...
8
votes
1answer
151 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
52 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
178 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 ...
4
votes
0answers
78 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
164 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?
5
votes
0answers
228 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 ...
5
votes
2answers
2k 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
94 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?
6
votes
0answers
160 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 ...
4
votes
1answer
393 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
103 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
214 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
235 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
143 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 ...
14
votes
3answers
782 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 ...
8
votes
1answer
791 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 ...
5
votes
2answers
1k 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
421 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 ...