Tag Info

Hot answers tagged network-flow

4

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s \to v_2 \to v_3 \to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.

4

Those answers assume that all edge capacities are integers. Assuming they are, this works. Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger ...

3

Let us consider $K_{2,2}$, the complete bipartite graph with two vertices on either side. A valid max flow sends $1/2$ units of flow across each edge of the bipartite graph. This gives a negative answer to your first question. On the other hand, the integral flow theorem guarantees that there exists an integral max flow, and such a max flow can be found ...

3

Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former. In other words, EK is $O(|E|\min(f_{max}, |V||E|))$ time (and writing it this way does add information, since $f_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other ...

3

It is explained in part (b) of the caption of Figure 26.4. The residual network $G_f$ with augmenting path $p$ shaded; its residual capacity is $c_f(p)=c_f(v_2,v_3)=4$. Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G_f$ that is defined by $f'(s,v_2)=f'(v_2,v_3)=f'(v_3,t)=4$. So for the network flow $f\uparrow f'... 3 Your problem is NP-hard. There is a reduction from Independent Set to its decision version. Consider an instance$G=(V,E)$of Independent Set, you construct a network with vertices$\{s,t\}\cup V\cup V'$where each vertex in$V'$corresponds to a pair of vertices in$V$. For example, if$V=\{1,2,3\}$, then$V'=\{v_{12},v_{23},v_{13}\}$. Then we construct ... 2 The given algorithm is correct. The flow network constructed need to be directed, and the value of a$S$-$T$cut only considers edges going out of the vertex set$S$. 2 To test correctness: the set of edges belonging to a min-cut is not unique in general, so a dataset like you ask would not really be helpful, apart from checking that the value of the cut is the right one. However, it is easy to check correctness yourself by using the output of your algorithm if you compute both the max-flow and the min-cut; just check that ... 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}...

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 A full edge, e.g. a \rightarrow c, has a residual capacity of 0 in the residual network. So you can't make an augmenting path over that directed edge. However the reversed edge, c \rightarrow a has a residual capacity of 5 (since c_{c \rightarrow a} = 0 and f_{c \rightarrow a} = -5). Therefore you can create an augmenting path using the reversed ... 2 This is sometimes called the minimum edge-cost flow problem or fixed-cost flow problem. As you suspected, it is indeed NP-hard, even when the network is bipartite. It is listed as problem ND32 in the list of NP-hard problems by Garey and Johnson: M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New ... 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 Yes, you can. If it has, say, no outcoming edge, there can be no flow routed over this node. Otherwise the flow conservation constraint for this node (v)$$\sum_{(u,v) \in E} f_{uv} - \underbrace{\sum_{(v,w) \in E} f_{vw}}_{= 0} = 0 is violated if you have incoming flow.

1

I would do it kind of the other way around as you suggested. First compute a flow that saturates $(u,v)$. This can be done with the Ford--Fulkerson algorithm. Look only for augmenting paths which contain $(u,v)$ and augment the flow until the edge is saturated. In the second step you augment further, but avoid the edge $(u,v)$ when searching for augmenting ...

1

Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic. I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and ...

1

Apply the transformation $w \mapsto (m+1)w + 1$ to all weights (where $m$ is the number of edges in the graph), and find the minimum weight cut in the new graph. This will give you the minimum weight cut with the minimum number of edges. By computing the value modulo $m+1$, you can determine the number of edges.

1

Remove $u$ and $v$ (as well as all edges connected to them), and for any removed edge $(u,x)$, add an edge from $s$ to $x$ with the same capacity; for any removed edge $(y,v)$, add an edge from $y$ to $t$ with the same capacity. Now find a min cut in this new graph. The partition of nodes in this cut suggests a min cut among those including $e$ in the ...

1

By the max flow min cut theorem, the maximum value of a flow equals the minimum capacity of a cut. The capacity of a cut is of the form 12x+18y, which can’t equal 56 because 56 is not a multiple of 6.

1

Just to respond to the above comment by the OP "why does linear programming for $K_{2,2}$ fail". Perhaps your confusion is because we need to distinguish between "solving an LP" and "solving an LP using a particular algorithm". The LP formulation of maxflow (with real variables) has optimal solution (1,0,1,0) (for the edges of the bipartite graph $K_{2,2}... 1 Flow is an abstraction of how much "stuff" you want to move through the network. Exactly what the stuff is depends on what you're modelling with the network - water pipes, transport networks, computer networks, etc. The problem (or something close to it) can also be used to model other problems, in which case flow could be all kinds of things. 1 There is a significant typo on that slide. "$c_f (u, v) = f (v, u)$if$f (v, u)$not in$E$" should have been "$c_f (u, v) = f (v, u)$if$(u, v)$not in$E$" or, what is equivalent, "$c_f (u, v) = f (v, u)$if$(v, u)$is in$E$". Why do we care about edge that is not in$E$? In fact, we care only edge$(u,v)$if either$(u,v)$is in$E$or$(v,u)$... 1 First a quick note, the flow entering a vertex is equal to the flow leaving. I'll just refer to it as the amount of flow through a vertex. Second, note that we can say$a \leq b \wedge b \leq a$, thus we can add the constraint$a = b$for two vertices. Then we can re-use the NP-hard result from the paper that you quoted: "A negative disjunctive ... 1 I would say that 3. is a special case of 2. instead but it is a point of view. On 3., you can create a new node "source" which has edges to every supply nodes (b(v) > 0). These edges have cost 0 and capacity b(v). Then you create a new node "sink" which has edges from every demand node. These edges have cost 0 and capacity -b(v). All this replaces the b(v)... 1 Here is your definition of reversed edges in the case of flow network given in your comment. Between 2 vertices there is the normal forward edge (u,v) , and another edge (v,u) that goes backward(this is the reversed edge). regardless their capacities. If your definition is used, flow networks may have reversed edges indeed. For example, the flow network (... 1 The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem. If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you ... 1 Let$G=(V,E)$be your input graph. Now consider a maximum flow$f$on$G$. Let$f$be a flow in$G$such that the residual network$G_R$has no s-t path, then$f$is a maximum flow. Let's define$G'=(V,E')$to be your graph with$E'=E \cup \{(u_i,s)\}$for$i=1,...,N$. Since$f$is a maximum flow on$G$, then$G_R\$ has no s-t paths. Now you can ...

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