2
$\begingroup$

Let's suppose we have a supplier, sorting facilities, shipping companies and a target warehouse.

We produce n packages of the product, and each goes to a different sorting facility (so every facility receives exactly one package).

A sorting facility then passes the processed product to a shipping company, each sorting facility is only connected to a limited number of shipping companies, meaning that It can only use a limited subset of all shippers to deliver the product to the warehouse.

Now, the company owner's brother runs shipping company A and the owner really want's to help his brother start up his bussiness.
We need to ensure that all packages are delivered, but company must A deliver most of them - so It's a max flow problem with a requirement, that vertex corresponding to company A has the highest flow of all the shipping companies vertices.

Here Is a sample graph representation I have came up with. Vertex 0 is the supplier, vertices 1-6 are the sorting facilities, vertices 7-10 are the shipping companies, and 11 is the warehouse.

Now, assuming vertex 7 is the owner's brother's company, we want to get a maximum flow in this graph such that flow through 7 is greater than flow through 8, 9 or 10

How can this graph (or any of the max-flows algorithms) be modified to ensure, that the requirement holds for vertex 7? sample graph

$\endgroup$
3
  • $\begingroup$ What's the context where you encountered this task? Can you credit the original source? $\endgroup$
    – D.W.
    Nov 24, 2020 at 17:38
  • $\begingroup$ There Is no context really. I have been studying max-flow in graphs and I found this type of modification interesting. $\endgroup$
    – Slam11
    Nov 24, 2020 at 17:44
  • 1
    $\begingroup$ You can use minimum cost flow to solve this by setting a cost of -1 on the $(7, 11)$ edge (or positive costs on the other 3 edges to 11). $\endgroup$ Apr 24, 2021 at 10:36

1 Answer 1

0
$\begingroup$

Add auxiliary nodes 8a, 9a, 10a between nodes 8, 9, 10 and node 11, so that for example we have 8 -> 8a -> 11. Set all the capacities on the (8 -> 8a, 9 -> 9a, and 10 -> 10a) edges to $c = 0$, and run max flow. If there is a solution (if the maximum flow through the graph is equal to the number $n$ of packages to be shipped) then congratulations - we are done. Otherwise, set the capacities to $c = 1$, and go again. And so on until you find the smallest capacity $c^*$ such that the maximum flow is $n$. If the flow through vertex 7 is larger than this capacity $c^*$ then we have a solution, but if not there is no solution. If you continue to increase up to $c = n$ and there is no solution, then the original problem has no solution.


As requested by D.W. I will elaborate on the correctness and efficiency of this solution. The simple method of increasing $c$ by $1$ each time to find $c^*$ can be improved by binary searching instead: as $c$ increases the maximum flow will also increase up to $n$, and therefore we can binary search on the possible values of $c$ in order to find the smallest $c^*$ such that the maximum flow is $n$. This improves the number of calls to a max-flow subroutine from $n$ to $\log n$.

In order to show correctness I will set up some more notation. In any allocation of flow to the graph, let $f_0$ be the flow through the special warehouse, and $f_1, \ldots, f_k$ the flow through the other warehouses. We will call an allocation of flow "feasible" if $f_0 + f_1 + \cdots + f_k = n$ and $f_0 > f_i$ for all $i = 1, \ldots, k$ and "infeasible" otherwise.

Suppose there is no feasible flow. Then no matter how we set $c$ in our algorithm, it will never find a feasible flow either (introducing capacities to vertices only limits the set of solutions). Therefore the algorithm gets the correct answer in this case.

Suppose there is a feasible flow. Out of all possible feasible flows, choose one which minimises $c' = \max_{i = 1, \ldots, k} f_i$. Then there is no feasible flow where $f_i < c'$ for all $i$, and there is a feasible flow where $f_i \leq c'$ for all $i$, and hence our algorithm will arrive at $c^* = c'$. However, the algorithm may not arrive at the same flows: in particular if $g_0, g_1, \ldots, g_k$ are the flows found by the algorithm, we are guaranteed that $g_i \leq c'$ for all $i = 1, \ldots, k$, but we may not have $g_0 > g_i$ for all $i$.

I think this is a problem with the algorithm actually: it finds $c^* = c'$ correctly, but needs some help in order to figure out whether flow through the special node can be made strictly larger. There are some things you could do with the residual graph here, or you could use a reduction to a circulation problem with lower bounds on capacities: use the algorithm above, but as a final step introduce the constraint that the flow through the special node must be at least $c^* + 1$, and check for a solution.

$\endgroup$
4
  • $\begingroup$ Alas, this doesn't run in polynomial time if the original capacities are large. Also, if the capacities on 8->8a->11 are $c$, you'll need to make sure that you send at least $c$ flow through 7->11, and I don't see anything in your answer that guarantees this. $\endgroup$
    – D.W.
    Nov 25, 2020 at 5:57
  • $\begingroup$ @D.W. I interpreted the capacities in the graph as all being 1 originally, so it would run in polynomial time under that assumption. Otherwise, since the "feasibility" (if the max flow is $n$) of the problem is monotonic in $c$, so doing a binary search can find the optimal value $c$ in polynomial time. Once the optimal $c$ is found, I did specify that the flow through vertex 7 must be checked to see if it is strictly larger than $c$. We have exhausted all possible smaller values of $c$, so either the solution works for this optimal $c$ or not at all. $\endgroup$
    – Joppy
    Nov 25, 2020 at 6:19
  • $\begingroup$ Binary search: clever! Care to edit your answer to add that? Checking to see if the flow is larger through $c$ does not seem sufficient, since what are you going to do if it is less than $c$? Maybe there exists a different solution where it is larger than $c$ but you just didn't find it. $\endgroup$
    – D.W.
    Nov 25, 2020 at 7:54
  • $\begingroup$ @D.W. Thanks for the comments - I've tried to elaborate and I did find that the algorithm is not correct, but is fairly close. It can be completed with some tricks I think, or just using lower bounds in the circulation problem. $\endgroup$
    – Joppy
    Nov 25, 2020 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.