Fair Integral Network Flows

A strongly polynomial algorithm is developed for finding an integer-valued feasible st-flow of a given flow amount, which is decreasingly minimal on a specified subset F of edges in the sense that the largest flow value on F is as small as possible; within this, the second largest flow value on F is as small as possible; within this, the third largest flow value on F is as small as possible, and so on. A characterization of the set of these st-flows gives rise to an algorithm to compute a cheapest F-decreasingly minimal integer-valued feasible st-flow of given flow amount. Decreasing minimality is a possible formal way to capture the intuitive notion of fairness.

Funding: This work was supported by JSPS KAKENHI [Grants JP20K11697, JP26280004] and the National Research, Development, and Innovation Fund of Hungary [Grant NKFI-128673].