The complexity of finding uniform sparsest cuts in various graph classes

详细信息	查看全文 | 推荐本文 |

• 作者：Paul Bonsma^a ; ¹ ; ^{bonsma@informatik.hu-berlin.de} ; Hajo Broersma^b ; ² ; ^{hajo.broersma@dur.ac.uk} ; Viresh Patel^b ; ² ; ^{viresh.patel@dur.ac.uk} ; Artem Pyatkin^b ; ² ; ³ ; ^{artem.pyatkin@dur.ac.uk}
• 关键词：Sparsest cut ; Parameterized complexity ; Treewidth ; Clique-width ; Unit interval graph
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：136-149
• 文件大小：292 K

摘要

Given an undirected graph , the (uniform, unweighted) sparsest cut problem is to find a vertex subset minimizing . We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. In particular, we show that the sparsest cut problem can be solved in linear time for unit interval graphs, and in cubic time for graphs of bounded treewidth. For cactus graphs and outerplanar graphs this can be improved to linear time and quadratic time, respectively. For graphs of clique-width k for which a short decomposition is given, we show that the problem can be solved in time , where n is the number of vertices in the input graph. We also establish that a running time of the form is optimal in this case, assuming that the Exponential Time Hypothesis holds.