Open AccessArticle

Stable Multicommodity Flows

Tamás Király

^* and

Júlia Pap

MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University,Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary

Author to whom correspondence should be addressed.

Algorithms 2013, 6(1), 161-168; https://doi.org/10.3390/a6010161

Submission received: 31 December 2012 / Revised: 25 January 2013 / Accepted: 8 March 2013 / Published: 18 March 2013

(This article belongs to the Special Issue Special Issue on Matching under Preferences)

Download Versions Notes

Abstract

We extend the stable flow model of Fleiner to multicommodity flows. In addition to the preference lists of agents on trading partners for each commodity, every trading pair has a preference list on the commodities that the seller can sell to the buyer. A blocking walk (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded along the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.

Keywords:

stable matching problem; stable flows; multicommodity flows; PPAD-completeness; Sperner’s Lemma

1. Introduction

Just as network flows generalize bipartite matchings, the stable marriage problem can be generalized to stable flows. An acyclic network model was presented by Ostrovsky [1], while Fleiner [2] introduced a stable flow model where the network is not necessarily acyclic. The aim of this paper is to extend the model of Fleiner to multicommodity flows, but first we briefly describe his model and results.

An instance of the stable flow problem consists of a network on digraph

D = (V, A)

with

s, t \in V

and capacities

c \in R_{+}^{A}

, and additionally for each node

v \in V

a linear order

<_{v}

on the arc set incident to v. We assume that s has no incoming arcs and t has no outgoing arcs. The network along with the set of these preference orders is called a network with preferences. We note that outgoing arcs are never compared with incoming arcs, so the information that we really need is a linear order on the set of outgoing arcs

δ^{o u t} (v)

and one on the set of incoming arcs

δ^{i n} (v)

We refer to directed walks simply as walks in this paper. Let f be a flow of network

(D, s, t, c)

. A walk

P = (v_{1}, a_{1}, v_{2}, a_{2}, \dots, a_{k - 1}, v_{k})

is said to block f if the following hold:

(i): each arc $a_{i}$ is unsaturated in f,
(ii): $v_{1} = s$ or there is an arc $a^{'} = v_{1} u$ for which $f (a^{'}) > 0$ and $a^{'} <_{v_{1}} a_{1}$ ,
(iii): $v_{k} = t$ or there is an arc $a^{″} = w v_{k}$ for which $f (a^{″}) > 0$ and $a^{″} <_{v_{k}} a_{k - 1}$ .

A flow is called stable if there is no walk blocking it. Note that this definition is slightly different from the one in [2], but it is equivalent.

The problem can be motivated by a network trading model: the nodes are traders that can buy and sell amounts of a certain product along the arcs of the digraph, and have preferences with whom they would like to trade (

a <_{v} a^{'}

means that trader v prefers trading along

a^{'}

to trading along a). A blocking walk represents a possible chain of transactions that offers a better selling option for the first trader of the walk than the current f, and also offers a better buying option for the last trader. In this interpretation, nodes s and t represent the producers and the consumers.

Since it will be convenient in the proofs to consider only finitely many walks, we introduce a finite subclass of walks that already determines stability. A walk

P = (v_{1}, a_{1}, v_{2}, a_{2}, \dots, a_{k - 1}, v_{k})

is called a quasi-path if

v_{2}, a_{2}, \dots, a_{k - 2}, v_{k - 1}

is a path. It is easy to see that every blocking walk contains a blocking quasi-path, so we may restrict the condition of stability to quasi-paths.

Fleiner [2] proved the following result, by reducing the stable flow problem to the stable allocation problem of Baïou and Balinski [3]. A different proof based on the Gale–Shapley algorithm, as well as an extension to flows over time, was given by Cseh, Matuschke, and Skutella [4].

Theorem 1.1

(Fleiner [2]). Every network with preferences has a stable flow. If the capacities are integral, then there is an integral stable flow.

1.1. Stable Multicommodity Flows

In this paper we present a way to include multiple commodities in the above network trading model. In the multicommodity setting, every arc has individual capacities for specific commodities as well as a cumulative capacity, and each trader has a preference order for each commodity on the possible buyers and sellers, so the preferred trading partners may be different for different commodities. In addition, for each trading pair (i.e., arc in D) there is a preference order on the commodities, which expresses that the pair is more inclined to trade certain goods than others.

A blocking walk in our model represents a chain of transactions for a specific commodity, with which the first and the last trader of the walk would be more pleased than before (the chain may also start at the producers, or end at the consumers), and each intermediate transaction either corresponds to an arc with free capacity or it can replace the trade of a less preferred commodity.

The formal definitions are as follows. The network consists of a digraph

D = (V, A)

with capacities

c \in R_{+}^{A}

(these will be called cumulative capacities, in order to distinguish from capacities of individual commodities). There are ℓ commodities, and each has its own capacity bound

c^{j} \in R_{+}^{A}

(

j \in [ℓ]

). Each commodity has a source

s^{j} \in V

and a sink

t^{j} \in V

. Sources and sinks of different commodities may coincide, but we assume that

c^{j}

is 0 on every arc entering

s^{j}

and on every arc leaving

t^{j}

For each commodity

j \in [ℓ]

, there are linear orders

<_{v}^{j}

for each node

v \in V \ {s^{j}, t^{j}}

on the arc set incident to v. In addition, for each arc

a \in A

there is a linear order

<_{a}

on the set of commodities. The network, together with these preference orders, is called a multicommodity network with preferences.

We say that

f = (f^{1}, \dots, f^{ℓ})

is a feasible multicommodity flow of the network if

f^{j} : A \to R_{+}

satisfies Kirchhoff’s law at every node except at

s^{j}

and

t^{j}

f^{j} (a) \leq c_{a}^{j}

for every

a \in A

and

j \in [ℓ]

, and

\sum_{j = 1}^{ℓ} f^{j} (a) \leq c_{a}

for every

a \in A

A walk

P = (v_{1}, a_{1}, v_{2}, a_{2}, \dots, a_{k - 1}, v_{k})

is said to be blocking with respect to commodity j if the following hold:

(i): each arc $a_{i}$ is unsaturated by $f^{j}$ , that is, $f^{j} (a_{i}) < c_{a_{i}}^{j}$ ,
(ii): $v_{1} = s^{j}$ or there is an arc $a^{'} = v_{1} u$ for which $f^{j} (a^{'}) > 0$ and $a^{'} <_{v_{1}}^{j} a_{1}$ ,
(iii): $v_{k} = t^{j}$ or there is an arc $a^{″} = w v_{k}$ for which $f^{j} (a^{″}) > 0$ and $a^{''} <_{v_{k}}^{j} a_{k - 1}$ ,
(iv): if an arc $a_{i}$ of P is saturated by f, i.e., $\sum_{j = 1}^{ℓ} f^{j} (a_{i}) = c_{a_{i}}$ , then there is a commodity $j^{'}$ such that $f^{j^{'}} (a_{i}) > 0$ and $j^{'} <_{a_{i}} j$ .

The last condition expresses that a chain of transactions can be blocking even if some of them have to replace transactions of other commodities, provided that the latter are less preferred commodities for the trading pairs.

A feasible multicommodity flow is called stable if there is no walk blocking it. As in the single flow case, it is enough to prohibit blocking quasi-paths, since each blocking walk contains a blocking quasi-path.

Remark.

It can be decided in polynomial time if a feasible multicommodity flow is stable. To see this, we show that for a given commodity j and nodes

u, v

, checking whether there is a blocking walk from u to v with respect to commodity j can be done in polynomial time. Conditions (i) and (iv) restrict the possible arcs that can appear in the walk. Among these, condition (ii) determines which arcs can be the starting arcs of the walk, and condition (iii) determines the possible ending arcs. Any

u v

-walk using only these arcs is automatically blocking, and we can use BFS to decide if such a walk exists.

Before proving the main result on the existence of stable multicommodity flows, we describe a version of Sperner’s Lemma that serves as the main tool in our proof.

1.2. A Polyhedral Version of Sperner’s Lemma

The following polyhedral version of Sperner’s Lemma was introduced in [5], and it was used in [6] to give an alternative proof of Theorem 1.1. An extreme direction of a polyhedron is an extreme ray of its characteristic cone. For a colouring of the facets of a pointed polyhedron P, a vertex of P is multicoloured if it lies on facets of every colour.

Theorem 1.2

([5]). Let

P \subseteq R^{n}

be an n-dimensional pointed polyhedron whose characteristic cone is generated by n linearly independent vectors. If the facets of the polyhedron are coloured with n colours such that facets containing the i-th extreme direction do not get colour i, then there is a multicoloured vertex.

We note that there is no known polynomial algorithm to find a multicoloured vertex; in fact, it is shown in [7] that this problem is PPAD-complete.

2. Existence of a Stable Multicommodity Flow

Theorem 2.1.

In every multicommodity network with preferences there exists a stable multicommodity flow.

Proof.

Let us consider a multicommodity network with preferences, as defined in Section 1.1. Let

P

denote the set of all quasi-paths, and for an arc

a \in A

let

P_{a}

be the set of quasi-paths that contain a. Furthermore, for a node

v \in V

, let

P_{v}^{out}

and

P_{v}^{in}

denote the set of quasi-paths that start and end at v, respectively.

Let us introduce the variables

x_{P}^{j}

(

j \in [ℓ], P \in P

) and

y_{a}^{j}

(

j \in [ℓ], a \in A

). Given a set of quasi-paths

P^{'} \subseteq P

, we use the notation

x^{j} (P^{'})

for

\sum_{P \in P^{'}} x_{P}^{j}

These variables do not have a clear meaning in terms of the problem that we want to solve; in order to help understanding their role, we describe the overall structure of the proof. We will define a full-dimensional polyhedron Π in the space of these variables that satisfies the conditions of Theorem 1.2, and has the property that we remain in Π if we decrease a coordinate

x_{P}^{j}

or if we increase it to 0, and we remain in Π if we increase a coordinate

y_{a}^{j}

or if we decrease it to

c_{a}^{j}

. In place of Kirchhoff’s law, we use the inequalities that at every node in

V \ {s^{j}, t^{j}}

the incoming

x^{j}

is at most the outgoing

y^{j}

, and the outgoing

x^{j}

is at most the incoming

y^{j}

. The face

F = {(x, y) \in Π : x_{P}^{j} = 0 if P is not a single arc, x_{a}^{j} = y_{a}^{j} for every a \in A and j \in [ℓ]}

corresponds to the set of multicommodity flows. We will prove the following:

We can define a suitable colouring of the facets of Π such that any multicoloured vertex of Π is on the face F,
We show that a multicoloured vertex corresponds to a stable multicommodity flow. This is where the variables $x_{P}^{j}$ (where P has length at least 2) play a role: in some sense, they correspond to possibilities of changing a feasible solution along a blocking quasi-path.

Let us turn to the details of the proof. We consider the polyhedron Π described by the following inequalities:

\begin{matrix} y_{a}^{j} & \geq 0 & \forall a \in A \forall j \in [ℓ] \end{matrix}

(1)

\begin{matrix} x^{j} (P^{'}) - y_{a}^{j} & \leq 0 & \forall P^{'} \subseteq P_{a} \forall a \in A \forall j \in [ℓ] \end{matrix}

(2)

\begin{matrix} x^{j} (P^{'}) & \leq c_{a}^{j} & \forall P^{'} \subseteq P_{a} \forall a \in A \forall j \in [ℓ] \end{matrix}

(3)

\begin{matrix} x^{j} (P^{'}) - y^{j} (δ^{'}) & \leq c^{j} (δ^{i n} (v) \ δ^{'}) & \forall \emptyset \neq P^{'} \subseteq P_{v}^{out}, δ^{'} \subseteq δ^{i n} (v), v \in V \ {s^{j}, t^{j}}, j \in [ℓ] \end{matrix}

(4)

\begin{matrix} x^{j} (P^{'}) - y^{j} (δ^{'}) & \leq c^{j} (δ^{o u t} (v) \ δ^{'}) & \forall \emptyset \neq P^{'} \subseteq P_{v}^{in}, δ^{'} \subseteq δ^{o u t} (v), v \in V \ {s^{j}, t^{j}}, j \in [ℓ] \end{matrix}

(5)

\begin{matrix} \sum_{j = 1}^{ℓ} x^{j} (P_{j}^{'}) & \leq c_{a} & \forall P_{j}^{'} \subseteq P_{a} (j \in [ℓ]) \forall a \in A \end{matrix}

(6)

First let us determine the set of extreme directions of Π. Clearly

- x_{P}^{j}

for

P \in P, j \in [ℓ]

and

y_{a}^{j}

for

a \in A, j \in [ℓ]

give infinite directions. Since

x_{P}^{j}

is bounded from above and

y_{a}^{j}

from below, there is no infinite direction that is not in the cone of the above. So the number of extreme directions equals the dimension.

Now let us assign colours (that is, variables, since each variable corresponds to an extreme direction of Π) to each inequality:

to an inequality of type (1) or type (2) we assign $y_{a}^{j}$ ,
to an inequality of type (3) we assign $x_{P}^{j}$ for a longest possible quasi-paths $P \in P^{'}$ ,
to an inequality of type (4) we assign $x_{P}^{j}$ for a quasi-path $P \in P^{'}$ in which the outgoing arc from v is smallest possible in the order $<_{v}^{j}$ from $P^{'}$ , and among these, we choose P to be one of the longest quasi-paths,
to an inequality of type (5) we assign $x_{P}^{j}$ for a quasi-path $P \in P^{'}$ in which the incoming arc to v is smallest possible in the order $<_{v}^{j}$ from $P^{'}$ , and among these, we choose P to be one of the longest quasi-paths,
to an inequality of type (6) we assign $x_{P}^{j}$ where j is the commodity that is smallest in the order $<_{a}$ among those with nonempty $P_{j}^{'}$ , and from $P_{j}^{'}$ we choose P to be one of the longest quasi-paths.

Since the assigned colour of each inequality is a coordinate with nonzero coefficient, the colouring fulfils the criteria of Theorem 1.2. Thus there exists a multicoloured vertex

(\bar{x}, \bar{y})

of Π.

Claim 2.2.

\bar{x} \geq 0

, and

{\bar{y}}^{j} \leq c^{j}

for every

j \in [ℓ]

Proof.

Suppose that

{\bar{x}}_{P}^{j}

is negative for some

P \in P

. Then by increasing

{\bar{x}}_{P}^{j}

to zero we get a vector that is still in Π, because every inequality where

x_{P}^{j}

has positive coefficient is also present with the coefficient changed to zero (except for the inequalities where

P^{'} = {P}

, but changing the coefficient of

x_{p}^{j}

in those to zero is satisfied too since

y_{a}^{j}

and

c_{a}^{j}

are nonnegative). On the other hand we know that

- x_{P}^{j}

is an infinite direction, so

(\bar{x}, \bar{y})

could not have been a vertex. Thus

{\bar{x}}_{P}^{j}

is nonnegative for every

P \in P

and

j \in [ℓ]

. Similarly we get that

{\bar{y}}_{a}^{j} \leq c_{a}^{j}

for every

a \in A

and

j \in [ℓ]

. ◊

Claim 2.3.

{\bar{x}}^{j} (P_{a}) = {\bar{y}}_{a}^{j}

for every arc

a \in A

and

j \in [ℓ]

Proof.

Since

(\bar{x}, \bar{y})

is multicoloured, there is a tight inequality that has colour

y_{a}^{j}

. If this inequality is of type (1), then using Claim 2.2 we have

0 \leq {\bar{x}}^{j} (P_{a}) \leq {\bar{y}}_{a}^{j} = 0

, thus equality holds. If the tight inequality is of type (2) for some

P^{'} \subseteq P_{a}

, then by Claim 2.2,

{\bar{x}}^{j} (P_{a}) \geq {\bar{x}}^{j} (P^{'}) = {\bar{y}}_{a}^{j} \geq {\bar{x}}^{j} (P_{a})

, so equality holds again. ◊

Claim 2.4.

For every

j \in [ℓ]

{\bar{x}}_{P}^{j} = 0

for every quasi-path P that has at least 2 arcs.

Proof.

Suppose that

{\bar{x}}_{P}^{j} > 0

for a quasi-path

P = (v_{1}, a_{1}, \dots, v_{k})

, where

k \geq 3

. Let Q be the one-arc path

(v_{1}, a_{1}, v_{2})

and let R be the quasi-path

(v_{2}, a_{2}, \dots, v_{k})

Consider the inequality that

(\bar{x}, \bar{y})

satisfies with equality and has colour

x_{Q}^{j}

. It cannot be of type (3), since because of P, we would not have chosen

x_{Q}^{j}

as colour. It also cannot be of type (4) or type (6) for the same reason. Thus it is of type (5). This means that there exists some

P^{'} \subseteq P_{v_{2}}^{in}

and

δ^{'} \subseteq δ^{o u t} (v_{2})

for which

{\bar{x}}^{j} (P^{'}) - {\bar{y}}^{j} (δ^{'}) = c^{j} (δ^{o u t} (v_{2}) \ δ^{'})

. Using Claim 2.2, this holds also for the whole sets

P_{v_{2}}^{in}

and

δ^{o u t} (v_{2})

, that is,

{\bar{x}}^{j} (P_{v_{2}}^{in}) = {\bar{y}}^{j} (δ^{o u t} (v_{2}))

Using

{\bar{x}}_{P}^{j} > 0

, and considering the sum of inequalities of type (2) for the arcs in

δ^{i n} (v_{2})

, we get

{\bar{y}}^{j} (δ^{o u t} (v_{2})) = {\bar{x}}^{j} (P_{v_{2}}^{in}) < {\bar{x}}^{j} (⋃_{a \in δ^{i n} (v_{2})} P_{a}) \leq {\bar{y}}^{j} (δ^{i n} (v_{2})) .

By the same argument for the subwalk R, we get

{\bar{y}}^{j} (δ^{i n} (v_{2})) = {\bar{x}}^{j} (P_{v_{2}}^{out}) < {\bar{y}}^{j} (δ^{o u t} (v_{2}))

which is a contradiction. ◊

We obtained that

\bar{x}

is positive only on the arcs (that is, on quasi-paths of length 1), and by Claim 2.3,

{\bar{x}}_{a}^{j} = {\bar{y}}_{a}^{j}

for every arc a and every

j \in [ℓ]

. By inequalities (4) and (5), we have

{\bar{x}}^{j} (δ^{o u t} (v)) \leq {\bar{y}}^{j} (δ^{i n} (v)) = {\bar{x}}^{j} (δ^{i n} (v)) \leq {\bar{y}}^{j} (δ^{o u t} (v)) = {\bar{x}}^{j} (δ^{o u t} (v))

for every

v \in V \ {s^{j}, t^{j}}

, so

{\bar{y}}^{j}

is a flow. By inequality (3), it satisfies the capacity constraints for commodity j, and by inequality (6),

\bar{y}

satisfies the cumulative capacity constraints, so it is a feasible multicommodity flow. We are done by proving our last claim.

Claim 2.5.

No quasi-path blocks

\bar{y}

with respect to any commodity.

Proof.

Let

P = (v_{1}, a_{1}, \dots, v_{k})

be an arbitrary quasi-path and j an arbitrary commodity. Since

(\bar{x}, \bar{y})

is a multicoloured vertex, there is a tight inequality of colour

x_{P}^{j}

. If it is of the form (3), then the arc a is saturated for commodity j, so P does not block

\bar{y}

with respect to commodity j.

If it is of the form (4) for node

v_{1}

P^{'} \subseteq P_{v_{1}}^{out}

and

δ^{'} \subseteq δ^{i n} (v_{1})

, then

a^{'} \notin P^{'}

whenever

a^{'} \in δ^{o u t} (v_{1})

and

a^{'} <_{v_{1}}^{j} a_{1}

. Thus

{\bar{x}}_{a^{'}}^{j} = 0

, because if

{\bar{x}}_{a^{'}}^{j}

was positive, then adding

x_{a^{'}}^{j}

to this tight inequality would not hold for

(\bar{x}, \bar{y})

, although it is also an inequality of the system. This implies that P does not block the flow

\bar{y}

with respect to commodity j.

The case when the tight inequality of colour

x_{P}^{j}

is of type (5) is analogous. Finally, if the inequality of colour

x_{P}^{j}

is of type (6), then the arc a is saturated, and furthermore

a \notin P_{j^{'}}^{'}

whenever

j^{'} <_{a} j

since

x_{P}^{j}

is selected as colour. This implies that

{\bar{x}}_{a}^{j^{'}} = 0

whenever

j^{'} <_{a} j

: if

{\bar{x}}_{a}^{j^{'}} > 0

would hold, then by adding a to

P_{j^{'}}^{'}

we would obtain an inequality that is violated by

(\bar{x}, \bar{y})

. Again, this means that P is not blocking for commodity j. ◊

We obtained that there is no blocking quasi-path, so

\bar{y}

is a stable multicommodity flow. □

We remark that even if the capacities are integer, there might be no integer stable multicommodity flow. In fact, for any integer N there is an instance where there is no stable solution with denominators at most N. As an example, consider the network consisting of nodes

v_{1}, \dots, v_{n}

and arcs

v_{i} v_{i + 1}

(

i \in [n]

), where we use the notation

v_{n + 1} = v_{1}

. There are n commodities; the sources and sinks are defined by

s^{j} = v_{j + 1}

t^{j} = v_{j}

, and the capacity

c^{j}

is 1 on all arcs except for

v_{j} v_{j + 1}

where it is 0. This means that commodity j has a unique quasi-path from

s^{j}

t^{j}

, namely

(v_{j + 1}, v_{j + 2}, \dots, v_{1}, \dots, v_{j})

, so the preference orders at the nodes do not play any role. The cumulative capacity c is 1 everywhere. The preference order at arc

a = v_{i} v_{i + 1}

is defined by

i - 1 >_{a} \dots >_{a} 1 >_{a} n >_{a} \dots >_{a} i + 1

(commodity i does not appear in the ordering because it has capacity 0 on this arc). We claim that the only stable multicommodity flow is obtained by setting

f^{j} (a) = \frac{1}{n - 1}

on every arc a except for

v_{j} v_{j + 1}

. Indeed, the all-zero flow is not stable, and if f is a nonzero feasible multicommodity flow different from the above, then there must be an index j such that commodity j has positive flow and the arc

v_{j} v_{j + 1}

is unsaturated. It can be checked that the path

(v_{j + 2}, v_{j + 3}, \dots, v_{1}, \dots, v_{j + 1})

is blocking with respect to commodity

j + 1

3. PPAD-Hardness

In this section, we prove that it is PPAD-hard to find a stable multicommodity flow. This is true even if the digraph is acyclic, a special case relevant for example in economic applications like supply chains (see [1]). The problem that we reduce to it is the following stable fractional hypergraph matching problem. We are given a hypergraph

H = (V, E)

, and for every node

v \in V

a linear order

≺_{v}

on the hyperedges containing v. A fractional matching of H is a vector

x \in R_{+}^{E}

such that

\sum_{e ∋ v} x_{e} \leq 1 for every v \in V .

A fractional matching is stable if for every

e \in E

there exists

v \in e

for which

\sum_{e^{'} ⪰_{v} e} x_{e^{'}} = 1 .

Kintali et al. [8] showed that finding a stable fractional hypergraph matching is PPAD-complete. We reduce this problem to the stable multicommodity flow problem in order to prove the following theorem.

Theorem 3.1.

It is PPAD-hard to find a stable multicommodity flow in a multicommodity network with preferences, even if the network is acyclic.

Proof.

Let

(H = (V, E), ≺)

be an instance of the stable fractional hypergraph matching problem. We use the notation

V = {v_{1}, v_{2}, \dots, v_{n}}

and

| E | = m

. We construct a network whose node set consists of nodes

s_{e}, t_{e}

(

e \in E

) and

v_{i}^{'}, v_{i}^{″}

(

i \in [n]

). There are m commodities, one corresponding to each hyperedge

e \in E

, with source

s_{e}

and sink

t_{e}

. The arc set of the network contains the arcs

v_{i}^{'} v_{i}^{″}

(

i \in [n]

) with cumulative and individual capacities all 1. Furthermore for each hyperedge e, whose elements are

v_{i_{1}}, v_{i_{2}}, \dots, v_{i_{k}}

with increasing indices, we add the arcs

s_{e} v_{i_{1}}^{'}

v_{i_{1}}^{″} v_{i_{2}}^{'}, \dots,

v_{i_{k - 1}}^{″} v_{i_{k}}^{'}

v_{i_{k}}^{″} t_{e}

. On these edges we set the cumulative capacity and the capacity of the commodity e to 1, and the other individual capacities to 0.

By the construction, each commodity has only one possible path, so we do not have to define precedence orderings for the nodes. In addition, only the arcs

v_{i}^{'} v_{i}^{″}

can be used by more than one commodity, so it is enough to define precedence orderings for these arcs: let the ordering

<_{v_{i}^{'} v_{i}^{″}}

be the same as

≺_{v_{i}}

It is easy to see that the feasible multicommodity flows of this network correspond to the fractional matchings of the hypergraph H. Furthermore, the stability of a multicommodity flow is equivalent to the stability of the corresponding fractional matching. Since the constructed network is acyclic, this proves the theorem. □

4. Open problems

It was shown in the previous section that finding a stable multicommodity flow is hard. The proof relies on the use of individual capacities, which enables the restriction of a commodity to a subset of the arcs. It is open whether the problem remains PPAD-hard if there are no individual capacities. Another interesting question is the complexity of the problem if there are only a constant number of commodities.

Acknowledgements

The authors received a grant (no. CK 80124) from the National Development Agency of Hungary, based on a source from the Research and Technology Innovation Fund. We thank the anonymous referees for their helpful comments.

References

Ostrovsky, M. Stability in supply chain networks. Am. Econ. Rev. 2008, 98, 897–923. [Google Scholar] [CrossRef]
Fleiner, T. On stable matchings and flows. Gr. Theor. Concepts Comput. Sci. Lecture Notes Comput. Sci. 2010, 6410, 51–62. [Google Scholar]
Baïou, M.; Balinski, M. The stable allocation (or ordinal transportation) problem. Math. Oper. Res. 2002, 27, 485–503. [Google Scholar] [CrossRef]
Cseh, Á.; Matuschke, J.; Skutella, M. Stable Flows over Time, TU Berlin Reports 023-2012; TU Berlin, Institut fr Mathematik: Berlin, Germany, 2012. [Google Scholar]
Király, T.; Pap, J. A note on kernels and Sperner’s Lemma. Discrete Appl. Math. 2009, 157, 3327–3331. [Google Scholar] [CrossRef]
Pap, J. Integrality, complexity and colourings in polyhedral combinatorics. Ph.D. Thesis, Eötvös Loránd University, Budapest, Hungary, 2012. [Google Scholar]
Király, T.; Pap, J. PPAD-completeness of polyhedral versions of Sperner’s Lemma. EGRES Tech. Rep. 2012, 2012-04. [Google Scholar] [CrossRef]
Kintali, S.; Poplawski, L.J.; Rajaraman, R.; Sundaram, R.; Teng, S.-H. Reducibility among Fractional Stability Problems. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, USA, October 2009; pp. 283–292.

© 2013 by the authors licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license ( http://creativecommons.org/licenses/by/3.0/).

Share and Cite

MDPI and ACS Style

Király, T.; Pap, J. Stable Multicommodity Flows. Algorithms 2013, 6, 161-168. https://doi.org/10.3390/a6010161

AMA Style

Király T, Pap J. Stable Multicommodity Flows. Algorithms. 2013; 6(1):161-168. https://doi.org/10.3390/a6010161

Chicago/Turabian Style

Király, Tamás, and Júlia Pap. 2013. "Stable Multicommodity Flows" Algorithms 6, no. 1: 161-168. https://doi.org/10.3390/a6010161

APA Style

Király, T., & Pap, J. (2013). Stable Multicommodity Flows. Algorithms, 6(1), 161-168. https://doi.org/10.3390/a6010161

Article Menu

Stable Multicommodity Flows

Abstract

1. Introduction

1.1. Stable Multicommodity Flows

1.2. A Polyhedral Version of Sperner’s Lemma

2. Existence of a Stable Multicommodity Flow

3. PPAD-Hardness

4. Open problems

Acknowledgements

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI