Блог пользователя Tokyo_Drift

Network Flow with constraint of equal flows on given list of edges.
Автор Tokyo_Drift, история, 23 месяца назад, По-английски

I have some network $$$G$$$, and for $$$k$$$ edges $$$e_1$$$, $$$e_2$$$... $$$e_k$$$, there is constraint that flow on these edges should be always equal to each other: $$$f_{e_1}=f_{e_2} = ...f_{e_k}$$$. Given this constraint I want to find max flow on $$$G$$$. $$$G$$$ is network with around 10k edges and I have around 1-5 minutes time limit. Any ideas, papers, problems?

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
23 месяца назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

This is an interesting problem and it has been studied before. The paper by Srinivasan and Thompson (1972) solves it : https://onlinelibrary.wiley.com/doi/epdf/10.1002/nav.3800190202

This is how to reduce the problem to the paper above. Start by removing the edges $$$e_1, \ldots, e_k$$$ from the graph, but remember both $$$c$$$ the minimum capacity of those edges, and $$$b(u)$$$ the difference between the number of edges with $$$u$$$ as head and those with $$$u$$$ as tail.

Also add an edge between tap and source of infinite capacity and cost -1 (all other edges are of cost -1). Then you can notice that we want to solve the following problem for all $$$x$$$ between 0 and $$$c$$$:

$$$\mathrm{minimize } \sum_{e} f_e\times w_e$$$

$$$\mathrm{subject}\quad \mathrm{to } \sum_{e\in\mathrm{out}(u)} f_e - \sum_{e\in\mathrm{in}(u)} f_e = x\times b(u)$$$

If you can solve that LP for all $$$x$$$ between 0 and $$$c$$$ then you win, the flow is simply the flow on edge from tap to source.

The book Network Flows : theory, algorithms and applications contains this problem as an exercice (11.51), I suggest reading both the exercice and either the corresponding chapter, or https://mirror.codeforces.com/blog/entry/94190 to better understand how to solve this.

→ Ответить