An Optimal Algorithm for Bisection for Bounded-Treewidth Graph
An Optimal Algorithm for Bisection for Bounded-Treewidth Graph
复制标题
有界树宽图二分的最优算法
DOI：
10.1007/978-3-030-59901-0_3
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sone Taiga
中科院分区：
文献类型：
--
作者：
Hanaka Tesshu;Kobayashi Yasuaki;Sone Taiga
在给定边加权图的情况下，最大/最小对分问题是寻找顶点集合的二分成两个大小至多相差一的集合，使得两个集合之间的边的总权重最大化/最小化。虽然这两个问题都是NP难的，但对于有界树宽图，还是有一个有效的算法。特别是，Jansen等人。(暹罗J.康普特)2005)给出了输入图宽度的树形分解的一个时间算法，这里是输入图的顶点数。Eiben et al.(ESA 2019)将运行时间改进为。在合理的复杂性假设下，证明了树的无时间算法。本文给出了这两个问题的一个时间算法，该算法渐近于它们的条件下界。我们还证明了在强指数时间假设下，树宽的指数相关性是渐近最优的。此外，我们还讨论了这两个问题关于特殊图类的可处理性。
The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (SIAM J. Comput. 2005) gave an-time algorithm when given a tree decomposition of widthtof the input graph, wherenis the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the running time to. Moreover, they showed that there is no-time algorithm for trees under some reasonable complexity assumption.In this paper, we show an-time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Moreover, we discuss the (in)tractability of both problems with respect to special graph classes.