7

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 ...


4

Find a maximum flow. Then create m new flow networks: one for each edge in the maximum flow. In each new configuration, reduce the capacity of one of the edges to an amount just below its flow. Find the maximum flow on each of the new flow networks. If any of the new configurations generate the same maximum flow value as the original graph, then that new ...


4

Note $S_{\max}=V-\bigcap_{S\in\mathcal{F}}(V-S)$. And $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph. The reason why $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph is the same as the reason why $S_{\min}$ is the set of all vertices ...


3

If $f_G$ is a valid flow for $G$, then there exists a valid flow $f_H$ for $H$ such that $|f_G| = |f_H|$. This is true since there is always a flow $f'_G$ for $G$ such that $|f'_G| = |f_G|$ and no edge is traversed in both directions in a flow decomposition of $f'_G$. If some edge $(u,v)$ is traversed by $x$ units of flow from $u$ to $v$ and $y \le x$ units ...


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

For edge "consumptions" I believe the following approach should work: [I misread your question at first, but am leaving this part for the benefit of future people reading this] Suppose you have some edge $u\rightarrow v$ with "consumption" $c$. Then you can model this by inserting a vertex $w$ in the middle to get $u\rightarrow w \rightarrow v$ and then add ...


2

Given a weighted directed graph and two nodes $s,t$, an $s$-$t$ cut is a set of edges, upon whose removal $t$ is not reachable from $s$. The weight of the cut is the total weight of edges removed. A minimum $s$-$t$ cut is one of minimum weight. A similar definition works for undirected graphs and in the special case in which the graph is unweighted, in ...


2

This is known as the closure problem. I quote the Wikipedia paragraph describing the reduction to the max flow problem here. As Picard (1976) [1] showed, a maximum-weight closure may be obtained from $G$ by solving a maximum flow problem on a graph $H$ constructed from $G$ by adding to it two additional vertices $s$ and $t$. For each vertex $v$ with ...


2

First, compute the minimum cut value $c$ of the network. Second, remove edge $e_1$ and increase the capacity of $e_2$ to infinity, then compute the minimum cut value $c_1$ of the new network. Third, remove edge $e_2$ and increase the capacity of $e_1$ to infinity, then compute the minimum cut value $c_2$ of the new network. Now you can check if $c-c_1\ge ...


1

Add a new source $s'$ and the edge $(s', s)$ with maximum and minimum capacity $R$. For each vertex $v$ with demand $d$ do the following: Replace $v$ with two vertices $v_1$ and $v_2$. Replace all the former edges $(u,v)$ with $(u, v_1)$ Replace all the former edges $(v, u)$ with $(v_2, u)$. Add the edge $(v_1, v_2)$ with minimum capacity $d$. The problem ...


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

Your problem is NP-hard. With the extra constraint, it is at least as hard as max independent set. In particular, suppose we have an undirected graph $G$. Let there be one object per vertex in $G$. For each edge in $G$, we'll have a constraint saying that at most one of the two endpoints of that edge can be assigned (using your new constraint type). We'...


1

Replace each undirected edge $(u,v)$ by two directed edges, one in each direction: $u\to v$ and $v\to u$. That gives you a graph with only directed edges. Then the max-flow on that graph is the same as the max-flow on your original graph.


1

I believe that the answer is yes: any min-cut constructed in this way from a max-flow will also have minimum possible cardinality, among all possible min-cuts. There can be multiple min-cuts, all with the same cost. They form a lattice structure: the intersection of two min-cuts is another min-cut, and the union of two min-cuts is another min-cut. You can ...


1

Yes, it is possible to solve such problems efficiently. The minimum-cost circulation problem is a generalization of the standard network flow problem, which allows you to set both lower bounds and upper bounds on the flow through each edge. (You can set all costs equal to 1.) There are polynomial-time algorithms to solve instances of the minimum-cost ...


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

Answer to Question 1: Because of how we chose 𝑣, we know that the distance of vertex 𝑒 from the source 𝑠 did not decrease, i.e., 𝛿𝑓′(𝑠,𝑒)β‰₯𝛿𝑓(𝑠,𝑒) Why the shortest-path from 𝑠 to 𝑒 after the augmentation of flow 𝑓 must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? ...


1

Your problem is a generalization of the Longest Path problem, which is NP-hard. If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once. At that point, you are just looking for the longest path. Your generalization, allowing partial conversions, non-constant functions,...


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