论文标题
确切的流量稀疏需要无限的尺寸
Exact Flow Sparsification Requires Unbounded Size
论文作者
论文摘要
给定一个较大的边缘负量的网络$ g $和一个称为终端的$ k $顶点的子集，一个（精确的）流量弹药器是一个小型网络$ g'$，可保留（确切）可以在终端之间路由的所有多物品流。 Leighton和Moitra [Stoc 2010]引入了流量稀疏器，并在许多算法环境中进行了研究和使用。 一个基本的问题是十多年来一直开放的，询问每个$ k $终端网络是否承认一个精确的流动稀疏器，其大小由某些功能$ f（k）$界定（无论$ g $还是其容量）。我们通过证明存在$ 6 $ - 末端网络$ g $的流量稀疏器$ g'$必须具有任意尺寸的$ 6 $ - 末端网络$ g $来解决这个问题。这种无限性也许令人惊讶，因为类似的稀疏量可以保留所有末端切割（称为精确切割的稀疏器或模仿网络）承认尺寸$ f_0（k）\ leq 2^{2^k} $的稀疏器， 我们通过分析网络中所有可行需求的集合（称为需求多层）来证明我们的结果。我们确定了该多层的不变性，本质上是某些方面的斜率，即使对于$ k = 6 $，也可以任意使其大大，并暗示在网络大小上明确的下限。我们进一步使用这种技术来再次回答有关Flow-Sparsification的否定性问题，即仅使用收缩并保留一个需求向量的不可行性。
Given a large edge-capacitated network $G$ and a subset of $k$ vertices called terminals, an (exact) flow sparsifier is a small network $G'$ that preserves (exactly) all multicommodity flows that can be routed between the terminals. Flow sparsifiers were introduced by Leighton and Moitra [STOC 2010], and have been studied and used in many algorithmic contexts. A fundamental question that remained open for over a decade, asks whether every $k$-terminal network admits an exact flow sparsifier whose size is bounded by some function $f(k)$ (regardless of the size of $G$ or its capacities). We resolve this question in the negative by proving that there exist $6$-terminal networks $G$ whose flow sparsifiers $G'$ must have arbitrarily large size. This unboundedness is perhaps surprising, since the analogous sparsification that preserves all terminal cuts (called exact cut sparsifier or mimicking network) admits sparsifiers of size $f_0(k)\leq 2^{2^k}$ [Hagerup, Katajainen, Nishimura, and Ragde, JCSS 1998]. We prove our results by analyzing the set of all feasible demands in the network, known as the demand polytope. We identify an invariant of this polytope, essentially the slope of certain facets, that can be made arbitrarily large even for $k=6$, and implies an explicit lower bound on the size of the network. We further use this technique to answer, again in the negative, an open question of Seymour [JCTB 2015] regarding flow-sparsification that uses only contractions and preserves the infeasibility of one demand vector.
