{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T05:23:10Z","timestamp":1670304190382},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0093117"]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0635084"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"\n We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an\n n<\/jats:italic>\n -vertex graph\n G<\/jats:italic>\n along with\n k<\/jats:italic>\n 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\n flow-cut gap<\/jats:italic>\n : the largest gap, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem.\n <\/jats:p>\n \n Our first result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is \u03a9\u02dc(\n n<\/jats:italic>\n 1\/7<\/jats:sup>\n ) 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\n n<\/jats:italic>\n ) 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\n n<\/jats:italic>\n ). Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2\n \n \u03a9(log\n 1-\u03f5<\/jats:sup>\n n<\/jats:italic>\n )\n <\/jats:sup>\n for any constant \u03f5 > 0, unless NP \u2286 ZPP. This improves upon the recent \u03a9(log\n n<\/jats:italic>\n \/log log\n n<\/jats:italic>\n )-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.\n <\/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","source":"Crossref","is-referenced-by-count":22,"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"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, Pennsylvania"}]}],"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","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."},{"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\/pdf\/10.1145\/1502793.1502795","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T20:48:32Z","timestamp":1670273312000},"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":"http:\/\/dx.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":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2009,4]]}}}