Width Helps and Hinders Splitting Flows
Width Helps and Hinders Splitting Flows
复制标题
DOI：
10.1145/3641820
复制
发表时间：
2024-04-01
影响因子：
1.3
通讯作者：
Williams，Lucia
中科院分区：
文献类型：
--
作者：
Caceres，Manuel;Cairo，Massimo;Williams，Lucia
最小流分解（Minimum flow decomposition，MFD）是一个NP难问题，即在一个有向图G上找到一个网络流/循环X的最小分解，分解为加权和等于X的加权源到汇路径。我们表明，对于非循环图，考虑图的宽度（覆盖其所有边所需的最小路径数）会使我们对其可逼近性的理解有所提高。对于只使用非负权重的问题，我们识别并构造了一类新的宽度稳定图，对于这类图，一个流行的启发式算法是O（log瓦尔（X））-近似（瓦尔（X）是X的总流），并且对于稀疏图，我们将其最坏情况近似比从Ω（m/logm）提高到Ω（m/logm），其中是图中的边数。我们还研究了一个新的问题，图的循环，最小成本循环分解（MCCD），并表明它通过一个简单的减少MFD的推广。对于也允许负权重的版本，我们使用2的幂方法，结合奇偶固定参数和酉循环的分解（≤ 1），使用这个问题的广义宽度概念，给出了（+1）-近似（是X在任何边上的最大绝对值）。最后，我们反驳了一个猜想的线性独立性的最小（非负）流分解克劳斯特等人。，但表明其有用的含义（多项式时间分配的权重给一组给定的路径分解流）举行的负版本。
Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulationXon a directed graphGinto weighted source-to-sink paths whose weighted sum equalsX. We show that, for acyclic graphs, considering thewidthof the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stablegraphs, for which a popular heuristic is aO(logVal(X))-approximation (Val(X) being the total flow ofX), and strengthen its worst-case approximation ratio fromto Ω (m/logm) for sparse graphs, wheremis the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X‖ being the maximum absolute value ofXon any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. , but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.