{"ID":3052311,"CreatedAt":"2026-06-04T04:41:36.695875263Z","UpdatedAt":"2026-06-06T04:55:27.670236374Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.04456","arxiv_id":"2606.04456","title":"Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs","abstract":"The multicommodity flow problem in an undirected capacitated graph $G$ is specified by a set of source-sink pairs with nonnegative demands. A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let $α$ be the smallest value such that the existence of a feasible flow implies the existence of an unsplittable flow that exceeds the edge capacities by at most $+\\,α\\,d_{\\max}$, where $d_{\\max}$ is the maximum demand value. Schrijver, Seymour, and Winkler showed that $α\\in\\left[1.01,\\,1.5\\right]$ if $G$ is a cycle. These bounds were ultimately improved to $α\\in\\left[1.1,\\,1.3\\right]$ by Skutella and Däubel. Recently, Alemán Espinosa and Kumar extended this constant upper bound to the broader class of outerplanar graphs, and showed that if $G$ is outerplanar then $α\\le 3.6$. We show that $α\\in\\left[\\tfrac{4}{3},2\\right]$ if $G$ is outerplanar. We introduce a novel technique that considers the global parameters of the instance, and that may be useful in other (more general) settings where the cut-condition is sufficient, or nearly sufficient, for the existence of a feasible flow.","short_abstract":"The multicommodity flow problem in an undirected capacitated graph $G$ is specified by a set of source-sink pairs with nonnegative demands. A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let $α$ be the smallest valu...","url_abs":"https://arxiv.org/abs/2606.04456","url_pdf":"https://arxiv.org/pdf/2606.04456v1","authors":"[\"David Alemán Espinosa\",\"Niklas Schlomberg\"]","published":"2026-06-03T04:59:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}