{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T16:42:04Z","timestamp":1778863324703,"version":"3.51.4"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0093117"],"award-info":[{"award-number":["CCR-0093117"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0635084"],"award-info":[{"award-number":["CCF-0635084"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an<jats:italic>n<\/jats:italic>-vertex graph<jats:italic>G<\/jats:italic>along with<jats:italic>k<\/jats:italic>source-sink pairs, and the goal is to find the minimum cardinality subset of edges whose removal separates all source-sink pairs. The sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of the number of deleted edges to the number of source-sink pairs that are separated by this deletion. The natural linear programming relaxation for multicut corresponds, by LP-duality, to the well-studied maximum (fractional) multicommodity flow problem, while the standard LP-relaxation for sparsest cut corresponds to maximum concurrent flow. Therefore, the integrality gap of the linear programming relaxation for multicut\/sparsest cut is also the<jats:italic>flow-cut gap<\/jats:italic>: the largest gap, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem.<\/jats:p><jats:p>Our first result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is \u03a9\u02dc(<jats:italic>n<\/jats:italic><jats:sup>1\/7<\/jats:sup>) in directed graphs. We show a similar result for the gap between maximum concurrent flow and sparsest cut in directed graphs. These results improve upon a long-standing lower bound of \u03a9(log<jats:italic>n<\/jats:italic>) for both types of flow-cut gaps. We notice that these polynomially large flow-cut gaps are in a sharp contrast to the undirected setting where both these flow-cut gaps are known to be \u0398(log<jats:italic>n<\/jats:italic>). Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2<jats:sup>\u03a9(log<jats:sup>1-\u03f5<\/jats:sup><jats:italic>n<\/jats:italic>)<\/jats:sup>for any constant \u03f5 &gt; 0, unless NP \u2286 ZPP. This improves upon the recent \u03a9(log<jats:italic>n<\/jats:italic>\/log log<jats:italic>n<\/jats:italic>)-hardness result for these problems. We also show that existence of PCP's for NP with perfect completeness, polynomially small soundness, and constant number of queries would imply a polynomial factor hardness of approximation for both these problems. All our results hold for directed acyclic graphs.<\/jats:p>","DOI":"10.1145\/1502793.1502795","type":"journal-article","created":{"date-parts":[[2009,4,15]],"date-time":"2009-04-15T13:37:07Z","timestamp":1239802627000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Polynomial flow-cut gaps and hardness of directed cut problems"],"prefix":"10.1145","volume":"56","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute, Chicago, Illinois"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250888"},{"key":"e_1_2_1_2_1","volume-title":"CIAC '97: Proceedings of the 3rd Italian Conference on Algorithms and Complexity. Springer-Verlag","author":"Alimonti P."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334206"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132592"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060673"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109564"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0015-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250816"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132593"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Chuzhoy J. and Khanna S. 2006b. Hardness of directed routing with congestion. ECCC Technical Report TR06-109. Chuzhoy J. and Khanna S. 2006b. Hardness of directed routing with congestion. ECCC Technical Report TR06-109.","DOI":"10.1145\/1250790.1250816"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301265"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873188"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. Technical Report MCS04-04, Department of Computer Science and Applied Math.","author":"Feige U.","year":"2004"},{"key":"e_1_2_1_18_1","unstructured":"Ford L. and Fulkerson D. 1962. Flows in networks. Princeton University Press Princeton NJ. Ford L. and Fulkerson D. 1962. Flows in networks. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_20_1","volume-title":"SODA '03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Gupta A.","year":"2003"},{"key":"e_1_2_1_21_1","unstructured":"Guruswami V. and Talwar K. 2006. Hardness of low congestion routing in directed graphs. ECCC Technical Report TR06-141. Guruswami V. and Talwar K. 2006. Hardness of low congestion routing in directed graphs. ECCC Technical Report TR06-141."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.10.005"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v45:4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0031-x"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502795","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1502793.1502795","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:37Z","timestamp":1750253377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502795"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1502793.1502795"],"URL":"https:\/\/doi.org\/10.1145\/1502793.1502795","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}