论文标题
A（可能）（可能）在有界树图上进行二合一的最佳算法
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
论文作者
论文摘要
给出了一个边缘加权图的最大/最小二分之一的问题，以找到两个组的两个集合的两组，其大小最多略有不同，因此两组之间的总边缘总重量是最大化/最小化的。尽管已知这两个问题是NP-硬化的，但有一个有效的算法用于有界树的图。特别是Jansen等。 （Siam J.Comput。2005）给出了$ O（2^tn^3）$ - 时间算法当给出了输入图的宽度$ t $的树分解时，其中$ n $是输入图的顶点的数量。 Eiben等。 （ESA 2019）通过给出$ O（8^tt^5n^2 \ log n）$ time算法，提高了运行时间的$ n $。此外，他们表明没有$ o（n^{2- \ varepsilon}）$ - 在某些合理的复杂性假设下，树的时间算法。 在本文中，我们显示了两个问题的$ O（2^t（tn）^2）$ - 时间算法，这与其条件下限渐近地紧密。我们还表明，在强指数时间假设下，树宽的指数依赖性在渐近上是最佳的。最后，我们讨论了两个问题在特殊图类别方面的（在）障碍性。
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 $O(2^tn^3)$-time algorithm when given a tree decomposition of width $t$ of the input graph, where $n$ is the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of $n$ in the running time by giving an $O(8^tt^5n^2\log n)$-time algorithm. Moreover, they showed that there is no $O(n^{2-\varepsilon})$-time algorithm for trees under some reasonable complexity assumption. In this paper, we show an $O(2^t(tn)^2)$-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. Finally, we discuss the (in)tractability of both problems with respect to special graph classes.
