# Tag Info

6

Yes. If the flow is not maximum, then there is an augmenting path. If there's an augmenting path, Ford-Fulkerson will find it (and continue to find them until the flow is maximum). Starting from a different initial flow does not change this.

6

You've left out part of the statement. It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow." If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$. The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated. The $s$ to $c$ ...

6

Yes, Ford-Fulkerson always finds the cut that is "closest" to the source. See this question for a formalization of what is meant by "closest". A graph can contain exponentially many min-cuts, so beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case. Based on what I've read, there are output-sensitive ...

6

You can do it in $\small \mathcal{O}(m + n)$ time where $\small m$ and $\small n$ are the # of edges and vertices respectively. Let the edge to be updated be $\small e = (u, v)$. If you increment the capacity of $\small e$ by $\small 1$, the maximum flow increments by at most $\small 1$. Hence, starting with the current max flow $\small f$, you only need ...

3

A flow is maximum if there is no $s$-$t$ path in the residual network. You can check this in time $O(|E|)$.

3

You can reduce SAT to this version. Connect the source to nodes $x_1,\ldots,x_n$, one per variable, with infinite capacity. Connect each $x_i$ to two exclusive nodes $x_i^T,x_i^F$, with infinite capacity. Create one node per clause, and connect a literal to a clause (with infinite capacity) if the clause contains the literal. Finally, connect each clause to ...

3

This is pseudocode, not the end-all be-all of the algorithm implementation. It is a very high level overview and by nature is left up to interpretation for the implementation. That being said... "When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity." This is not necessarily the ...

3

No, it is not true that "the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges". If you look at the wiki article of Ford and Fulkerson method you will see the following pseudocode: Algorithm Ford–Fulkerson Inputs: Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink ...

3

if there was no path from s to t, then the flow would be a max flow. The correct statement is, if there is no path from $s$ to $t$ in the residual network, then the flow is a max flow. If you build the residual network, you'll see that there is no edge from $a$ to $b$ and none from $c$ to $b$ or $d$, so $s$ and $t$ are disconnected.

2

The short answer is $f(u,v)=-f(v,u)$. Note that the first sum includes both vertices $w$ such that $(u,w) \in E$, as well as vertices $w$ such that $(u,w) \notin E$ but $(w,u) \in E$. Now unpack the implications of the first sum, separating by these two cases, and I think you'll see what happens. For a more lengthy explanation, this is covered in standard ...

2

A helpful way to build intuition: Try working through an example! Can you find an example of a graph and a flow where property (a) is true? Then, ask yourself: is property (b) true in that one? What made the difference? Spoiler (but it's best to try the above first; it will help you learn more from this exercise):

2

Will not find A-E, B-C min-cut. Will find A-B, A-E and C-D. Graph does not show flow direction, but assume left to right (i.e. A->B, B->C, A->E, E->C and C->D) B / \ 1 / \ 1 / \ 2 A C --- D \ / 1 \ / 4 \ / E

2

Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are equal, then it is equivalent to the vertex-connectivity problem. The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough. ...

2

No, your gut feeling is not correct. Consider the following flow network with source $s$ and sink $t$, where the capacity of every edge is 1. The max-flow from source to sink is 0. The s-t cut $(\{s,A\}, \{B,t\})$ is a minimum cut since the only connecting edge $(B, A)$ goes from sink side to source side. $$s \longrightarrow A \longleftarrow B \... 2 Consider a graph of two node s and t and one edge (s,t) with a flow f, f(s,t)=1. Let S=\{s\} and T=\{t\}. Then the flow across the cut (S, T) is, apparently 1. Or,$$f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)= f(u,v)=1. $\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the flow from $S$ to $T$. $\sum_{u\in S}... 1 This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem. Given an instance of Not-All-Equal 3SAT with$n$variables and$m$clauses, for each variable$x_i$, we create two vertices$v_i$and$v_i'$with an edge between them for each variable. In addition, for each clause, for example,$x_1\...

1

That would actually work as well, but it is more cumbersome than just adding a new source and sink.

1

I suggest you start with a simpler problem: there are only two (possibly overlapping) subsets, A and B; and every group must have two objects: one from subset A, and one from B. Once I figured out how to solve that, it was clear to me how to solve your original question. Hint on how to solve that:

1

Hint: Hint #2:

1

First, you can divide all capacities by $\sqrt{2}$ so that all capacities are now $1$ except for a single edge $e'$ which has capacity $\sqrt{2}$. Call this instance $G$. Create $G_1$ which is a copy of $G$ where the capacity of $e'$ has been replaced with $1$, and find the max flow of this graph, with a value $F_1$. Now, consider $G_2$ which is also a ...

1

Since all steps of the algorithm merely involve addition, you can compute the least common multiple $m$ of the denominators of all weights involved, and creating $G'$ from $G$ by multiplying all weights by $m$. Then all weights are integers and you can run Ford-Fulkerson. You can divide the results from it by $m$ again to get back your rationals.

1

Your approach works. The situation you're worried about can't happen. It appears you haven't quite fully grasped how the Ford-Fulkerson algorithms yet, so focus on getting more familiar with it. It always finds the max-flow, and the max-flow always solves your problem. The key misunderstanding is where you wrote: Running the Ford-Fulkerson algorithm ...

1

You need to draw the residual network for this.The augmented path finding procedure should be done in the residual network. There are no augmented path from S to t here. So this is a max flow.

1

The flow is maximum if there is no augmenting(i.e. improving) path between s and t. A path would contribute to the maximum flow if all its edges have strictly positive capacity left. In your case although you have some paths between s and t, all of them will have at least one edge that has used its whole capacity. Thus you can't improve the current flow and ...

Only top voted, non community-wiki answers of a minimum length are eligible