{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:53:19Z","timestamp":1710377599586},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["851093, SAFEBIO"]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["322595, 328877, 352821, and 346968"],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["1661530, and 1759522"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"\n Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow\/circulation\n X<\/jats:italic>\n on a directed graph\n G<\/jats:italic>\n into weighted source-to-sink paths whose weighted sum equals\n X<\/jats:italic>\n . We show that, for acyclic graphs, considering the\n width<\/jats:italic>\n of 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 of\n width-stable<\/jats:italic>\n graphs, for which a popular heuristic is a\n O<\/jats:italic>\n (log\n Val<\/jats:monospace>\n (\n X<\/jats:italic>\n ))-approximation (\n Val<\/jats:monospace>\n (\n X<\/jats:italic>\n ) being the total flow of\n X<\/jats:italic>\n ), and strengthen its worst-case approximation ratio from\n \n \\(\\Omega (\\sqrt {m})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n to \u03a9 (\n m<\/jats:italic>\n \/log\n m<\/jats:italic>\n ) for sparse graphs, where\n m<\/jats:italic>\n is 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 (\u2308 log \u2016 X \u2016 \u2309 +1)-approximation (\u2016\n X<\/jats:italic>\n \u2016 being the maximum absolute value of\n X<\/jats:italic>\n on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (\u2016\n X<\/jats:italic>\n \u2016 \u2264 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\u00a0al. [\n 2018<\/jats:xref>\n ], 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.\n <\/jats:p>","DOI":"10.1145\/3641820","type":"journal-article","created":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T11:54:37Z","timestamp":1705924477000},"page":"1-20","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Width Helps and Hinders Splitting Flows"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-0235-6951","authenticated-orcid":false,"given":"Manuel","family":"C\u00e1ceres","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-7247-756X","authenticated-orcid":false,"given":"Massimo","family":"Cairo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-0989-2415","authenticated-orcid":false,"given":"Andreas","family":"Grigorjew","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-9352-0088","authenticated-orcid":false,"given":"Shahbaz","family":"Khan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, India"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-7151-2124","authenticated-orcid":false,"given":"Brendan","family":"Mumey","sequence":"additional","affiliation":[{"name":"School of Computing, Montana State University, Bozeman, United States"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2387-0952","authenticated-orcid":false,"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Verona, Italy"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-3785-0247","authenticated-orcid":false,"given":"Lucia","family":"Williams","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Montana, Missoula, United States"}]}],"member":"320","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"e_1_3_2_2_1","article-title":"Network flows: Theory, algorithms and applications","author":"Ahujia Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahujia, Thomas L. Magnanti, and James B. Orlin. 1993. Network flows: Theory, algorithms and applications. New Jersey: Prentice-Hall (1993).","journal-title":"New Jersey: Prentice-Hall"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45257-5_14"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu317"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1200"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.18"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btad640"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-04749-7_14"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90041-D"},{"issue":"4","key":"e_1_3_2_11_1","first-page":"701","article-title":"Note on dilworth\u2019s decomposition theorem for partially ordered sets","volume":"7","author":"Fulkerson Delbert R.","year":"1956","unstructured":"Delbert R. Fulkerson. 1956. Note on dilworth\u2019s decomposition theorem for partially ordered sets. Proceedings of the American Mathematical Society 7, 4 (1956), 701\u2013702.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00464-4"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-019-2786-5"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195830"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1993.262879"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2022.0261"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.7"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOMW.2015.7414053"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-020-00705-6"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3122"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2017.2779509"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-016-1060-7"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2015.2418753"},{"key":"e_1_3_2_27_1","first-page":"S15:1\u2013S15:10","volume-title":"BMC bioinformatics","author":"Tomescu Alexandru I.","year":"2013","unstructured":"Alexandru I. Tomescu, Anna Kuosmanen, Romeo Rizzi, and Veli M\u00e4kinen. 2013. A novel min-cost flow method for estimating transcript expression with RNA-Seq. BMC bioinformatics 14, 5 (2013), S15:1\u2013S15:10."},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211023"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.05.043"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBM47256.2019.8983180"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3641820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T11:14:24Z","timestamp":1710328464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3641820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3641820"],"URL":"https:\/\/doi.org\/10.1145\/3641820","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"assertion":[{"value":"2023-04-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}