Show simple item record

dc.contributor.authorEiben, Eduard
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorMouawad, Amer E.
dc.PublishedLeibniz International Proceedings in Informatics. 2019, 144, 42:1-42:11.en_US
dc.description.abstractIn the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint in A and the other in B is minimized. We show that the complexity of the Bisection problem on trees, and more generally on graphs of bounded treewidth, is intimately linked to the (min, +)-Convolution problem. Here the input consists of two sequences (a[i])^{n-1}_{i = 0} and (b[i])^{n-1}_{i = 0}, the task is to compute the sequence (c[i])^{n-1}_{i = 0}, where c[k] = min_{i=0,...,k}(a[i] + b[k - i]). In particular, we prove that if (min, +)-Convolution can be solved in O(tau(n)) time, then Bisection of graphs of treewidth t can be solved in time O(8^t t^{O(1)} log n * tau(n)), assuming a tree decomposition of width t is provided as input. Plugging in the naive 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(beta(n)) on edge weighted trees, then (min, +)-Convolution can be solved in O(beta(n)) time as well. 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 a recent 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).en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleBisection of Bounded Treewidth Graphs by Convolutionsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2019 The Authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal