Bisection of bounded treewidth graphs by convolutions

摘要

We prove that if (min⁡,+)-Convolution can be solved in O(τ(n)) time, then Bisection on treewidth t graphs can be solved in time O(8ttO(1)log⁡n⋅τ(n)), assuming a decomposition of width t as input. Plugging in the O(n2) time algorithm for (min⁡,+)-Convolution yields a O(8ttO(1)n2log⁡n) time algorithm for Bisection. This improves over the (dependence on n of the) O(2tn3) time algorithm of Jansen et al. [SICOMP 2005] at the cost of a worse dependence on t. “Conversely”, we show that if Bisection can be solved in time O(β(n)) on edge weighted trees, then so can (min⁡,+)-Convolution. Thus, obtaining a sub-quadratic algorithm for Bisection on trees is extremely challenging, and could even be impossible. On the other hand, for unweighted graphs of treewidth t, by making use of the algorithm for Bounded Difference (min⁡,+)-Convolution of Chan and Lewenstein [STOC 2015], we obtain a sub-quadratic algorithm for Bisection with running time O(8ttO(1)n1.864log⁡n).