Abstract
We give a nearlylinear time reduction that encodes any linear program as a 2commodity flow problem with only a small blowup in size. Under mild assumptions similar to those employed by modern fast solvers for linear programs, our reduction causes only a polylogarithmic multiplicative increase in the size of the program, and runs in nearlylinear time. Our reduction applies to highaccuracy approximation algorithms and exact algorithms. Given an approximate solution to the 2commodity flow problem, we can extract a solution to the linear program in linear time with only a polynomial factor increase in the error. This implies that any algorithm that solves the 2commodity flow problem can solve linear programs in essentially the same time. Given a directed graph with edge capacities and two sourcesink pairs, the goal of the 2commodity flow problem is to maximize the sum of the flows routed between the two sourcesink pairs subject to edge capacities and flow conservation. A 2commodity flow problem can be formulated as a linear program, which can be solved to high accuracy in almost the current matrix multiplication time (CohenLeeSong JACM'21). Our reduction shows that linear programs can be approximately solved, to high accuracy, using 2commodity flow as well.
Our proof follows the outline of Itai’s polynomialtime reduction of a linear program to a 2commodity flow problem (JACM’78). Itai’s reduction shows that exactly solving 2commodity flow and exactly solving linear programming are polynomialtime equivalent. We improve Itai’s reduction to nearly preserve the problem representation size in each step. In addition, we establish an error bound for approximately solving each intermediate problem in the reduction, and show that the accumulated error is polynomially bounded. We remark that our reduction does not run in strongly polynomial time and that it is open whether 2commodity flow and linear programming are equivalent in strongly polynomial time.
BibTeX  Entry
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.54,
author = {Ding, Ming and Kyng, Rasmus and Zhang, Peng},
title = {{TwoCommodity Flow Is Equivalent to Linear Programming Under NearlyLinear Time Reductions}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {54:154:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16395},
URN = {urn:nbn:de:0030drops163950},
doi = {10.4230/LIPIcs.ICALP.2022.54},
annote = {Keywords: TwoCommodity Flow Problems, Linear Programming, FineGrained Complexity}
}
Keywords: 

TwoCommodity Flow Problems, Linear Programming, FineGrained Complexity 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 