2026-07-23T06:32:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16969 2024-03-06T10:58:51Z ddc:004 open_access

Width Helps and Hinders Splitting Flows Cáceres, Manuel Cairo, Massimo Grigorjew, Andreas Khan, Shahbaz Mumey, Brendan Rizzi, Romeo Tomescu, Alexandru I. Williams, Lucia Flow decomposition approximation algorithms graph width Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow X on directed graph G into weighted source-to-sink paths whose superposition equals X. We focus on a common formulation of the problem where the path weights must be non-negative integers and also on a new variant where these weights can be negative. We show that, for acyclic graphs, considering the width of the graph (the minimum number of s-t paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the non-negative version, we show that a popular heuristic is a O(log |X|)-approximation (|X| being the total flow of X) on graphs satisfying two properties related to the width (satisfied by e.g., series-parallel graphs), and strengthen its worst-case approximation ratio from Ω(√m) to Ω(m / log m) for sparse graphs, where m is the number of edges in the graph. For the negative version, we give a (⌈log ║X║⌉+1)-approximation (║X║ being the maximum absolute value of X on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary flows (║X║ ≤ 1) into at most width paths. We also disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ALENEX 2018], 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Cáceres and Massimo Cairo and Andreas Grigorjew and Shahbaz Khan and Brendan Mumey and Romeo Rizzi and Alexandru I. Tomescu and Lucia Williams 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.31 urn:nbn:de:0030-drops-169695 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.31 eng https://creativecommons.org/licenses/by/4.0/legalcode