Talk:Maximum flow problem

Fairness in car sharing (carpool) subsection mentions some equations and images, but those are missing. Iomartin (talk) 11:34, 20 July 2015 (UTC)

== Solution ==

The picture MFP2.jpg is wrong and it is an erroneous plagiarism of a copyrighted picture: See [http://en.wikipedia.org/wiki/File_talk:MFP2.jpg] — Preceding unsigned comment added by 131.188.224.200 (talk) 09:53, 21 November 2011 (UTC)

i think this diagram is wrong it is doing the opposite to what is being described in the text

Vin and vout should be swapped — Preceding unsigned comment added by Spartan3123 (talk • contribs) 00:50, 7 November 2011 (UTC)

I'd like to see some examples of problems that can be solved by turning them into Maximum flow problems. Joepnl (talk) 16:53, 8 October 2010 (UTC)

And what does it mean that there exists an integral maximum flow?

Velle (talk) 23:57, 27 January 2011 (UTC)

: It means that edge capacities and flow values are integers. -- X7q (talk) 01:05, 28 January 2011 (UTC)

The history section is severely flawed. The referenced papers do not support the claim that Dantzig created the max flow problem or that it was used in the Berlin airlift. The cited papers refers to the transportation problem. The referenced textbook (CLRS) does not acknowledge Dantzig as the creator of the max flow problem. The only reference to the Berlin airlift is an MIT press release (and its echos). I would view Schrijver's peer-reviewed article as authoritative.

Schrijver, Alexander, "On the history of the transportation and maximum flow problems", Mathematical Programming 91 (2002) 437-445

Moreover, the 2010 electric flow result is a significant result, but it is misleading to single it out in the history section (e.g., instead of Edmonds-Karp or other classic results). —Preceding unsigned comment added by 128.112.139.195 (talk) 10:36, 18 April 2011 (UTC)

First of all, the minimum path cover in DAG problem is not an application of max flow. It is an application of maximum bipartite matching and should be moved to that page.

Also I believe it's better to express this application using Dilworth's theorem. — Preceding unsigned comment added by Mizgly (talk • contribs) 19:30, 5 December 2012 (UTC)

: It is noteworthy to differentiate between a "path cover" and a "vertex-disjoint path cover". The current section only applies to the vertex-disjoint case. A counter-example being 1->2->4, 3->2->5. 141.3.49.88 (talk) 16:15, 27 April 2015 (UTC)

I removed the following example, as it is half-baked and makes reference to a non-existent figure. Perhaps someone could flesh it out and add it back in?

The problem exactly is that $N$ people are pooling a car for $k$ days. Each participant can choose if he participates on each day. We aim to fairly decide who will be driving on a given day.

The solution is the following:

We can decide this on the basis of the number of people using the car i.e.; if $m$ people use the car on a day, each person has a responsibility of $1/m$. Thus, for every person $i$, his driving obligation $D\_i$ as shown. Then person $i$ is required to drive only $[D\_i]$ times in $k$ days.

Our aim is to find if such a setting is possible. For this we try to model the problem as a network.

Now, it can be proved that if a flow $k$ exists then such a fair setting exists and such a flow of value $k$ always exists.

Doctormatt (talk) 00:03, 28 August 2015 (UTC)

One should update the table that lists the best known algorithms for computing the maximum flow. To the best of my knowledge the best current algorithm is Madry's algorithm running in time O(m^(10/7) polylog(m)). The paper of the algorithm is called "Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back" and can be found here: https://people.csail.mit.edu/madry/docs/matching_flow.pdf --131.130.117.228 (talk) 17:04, 18 January 2016 (UTC)

Note however that Madry's algorithm only applies for networks with unit capacities. The table however is definitely missing the algorithm with running time O(m n^(1/2) polylog(n) log^2 U) by Lee and Sidford: https://arxiv.org/abs/1312.6713 (FOCS 2014). I'm not adding it myself right now because I do not know which method for writing polylog(n) in the running time is preferred by WP. In research papers we often use tilde-O notation, but it does not seem appropriate here. — Preceding unsigned comment added by 2001:628:2120:630:F1B4:3809:85FE:5DE (talk) 12:42, 11 January 2018 (UTC)

Hello fellow Wikipedians,

I have just modified one external link on Maximum flow problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20160303170302/http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf to http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

{{sourcecheck|checked=false|needhelp=}}

Cheers.—InternetArchiveBot (Report bug) 00:08, 23 January 2018 (UTC)

There are numerous issues with the subsection "Minimum path cover in directed acyclic graph" (besides no cited sources):

1. The terms "in-degree" and "out-degree" are not defined in this article, but if we assume they take the usual meaning – "positive out-degree" of $v$ means that there is one or more edges leaving $v$ – then $V\_\{in\}$ and $V\_\{out\}$ can be non-disjoint, which contradicts the statement that $G\text{'}$ is a bipartite graph. Although it can be understood that $V\_\{in\}$ and $V\_\{out\}$ contain "symbolic" vertices constituting the original vertices of $V$, such that the symbolic vertices for a certain $v\; \backslash in\; V$ are distinct in $V\_\{in\}$ and $V\_\{out\}$, it is necessary to make this distinctness explicit, for example using a notation such as $\backslash \{\; v\_\backslash textrm\{in\}\; \backslash vert\; v\; \backslash in\; V\; \backslash land\; v\; \backslash text\{\; has\; positive\; in-degree\}\; \backslash \}$.
2. Similarly, taking the current definition of $V\_\{in\}$ and $V\_\{out\}$, $E\text{'}$ simply equals $E$, since for each $(u,\; v)\; \backslash in\; E$ it certainly holds that out-degree of $u$ and in-degree of $v$ are both positive. This again contradicts the statement that $G\text{'}$ is a bipartite graph, since $V\_\{out\}$ and $V\_\{in\}$ are in general not independent.
3. Kőnig's theorem relates vertex covers to matchings in bipartite graphs. It is not clear how one would use Kőnig's theorem to relate matchings in $G\text{'}$ to verex-disjoint path covers in $G$.
4. Overall, it is not clear whether and why are the observations in this section correct. As currently stated, it leaves too much room for interpretation and gives no intuitive explanation of the principle, althought the intuition is quite simple.

I would suggest either incorporating these remarks or removing the subsection.

--84.245.120.59 (talk) 19:44, 21 November 2020 (UTC)

The last entry in the table is written in terms of O(n), but n appears to be undefined, and all of the other entries talk in terms of |E| and |V|.

Rdviii (talk) 03:42, 25 March 2025 (UTC)