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 (8 t t O (1) log ⁡ n ⋅ τ (n)) , assuming a decomposition of width t as input. Plugging in the O (n 2) time algorithm for (min ⁡ , +) - Convolution yields a O (8 t t O (1) n 2 log ⁡ n) time algorithm for Bisection. This improves over the (dependence on n of the) O (2 t n 3) 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 (8 t t O (1) n 1.864 log ⁡ n). [ABSTRACT FROM AUTHOR]