dc.contributor.author Eiben, Eduard dc.contributor.author Lokshtanov, Daniel dc.contributor.author Mouawad, Amer E. dc.date.accessioned 2021-01-13T12:57:56Z dc.date.available 2021-01-13T12:57:56Z dc.date.created 2019-12-12T18:08:58Z dc.date.issued 2019 dc.Published Leibniz International Proceedings in Informatics. 2019, 144, 42:1-42:11. en_US dc.identifier.issn 1868-8969 dc.identifier.uri https://hdl.handle.net/11250/2722781 dc.description.abstract In 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.language.iso eng en_US dc.publisher Dagstuhl Publishing en_US dc.rights Navngivelse 4.0 Internasjonal * dc.rights.uri http://creativecommons.org/licenses/by/4.0/deed.no * dc.title Bisection of Bounded Treewidth Graphs by Convolutions en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2019 The Authors en_US dc.source.articlenumber 42 en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 1 dc.identifier.doi 10.4230/LIPIcs.ESA.2019.42 dc.identifier.cristin 1760252 dc.source.journal Leibniz International Proceedings in Informatics en_US dc.source.40 144 en_US dc.source.pagenumber 42:1-42:11 en_US
﻿

### This item appears in the following Collection(s)

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