Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

• 成果类型: Article
• 署名作者: Baiou, Mourad; Barahona, Francisco
• 署名单位: Centre National de la Recherche Scientifique (CNRS); International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1227-3
• 发表日期: 2018
• 页码: 59-75
• 关键词: multicommodity flows; algorithm; ratio

摘要

We study the sparsest cut problem when the capacity-demand graph is planar, and give a combinatorial polynomial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no K5 minor. We also show how to find a maximum concurrent flow in these two cases. We also prove that the sparsest cut problem is NP-hard if we only impose that the capacity-demand graph has no K6 minor. We use ideas that had been developed for the max-cut problem, and show how to exploit the connections among these problems.