Eiben, Eduard ;
Lokshtanov, Daniel ;
Mouawad, Amer E.
Bisection of Bounded Treewidth Graphs by Convolutions
Abstract
In the Bisection problem, we are given as input an edgeweighted 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])^{n1}_{i = 0} and (b[i])^{n1}_{i = 0}, the task is to compute the sequence (c[i])^{n1}_{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 subquadratic 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 subquadratic algorithm for Bisection with running time O(8^t t^{O(1)} n^{1.864} log n).
BibTeX  Entry
@InProceedings{eiben_et_al:LIPIcs:2019:11163,
author = {Eduard Eiben and Daniel Lokshtanov and Amer E. Mouawad},
title = {{Bisection of Bounded Treewidth Graphs by Convolutions}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {42:142:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11163},
URN = {urn:nbn:de:0030drops111639},
doi = {10.4230/LIPIcs.ESA.2019.42},
annote = {Keywords: bisection, convolution, treewidth, finegrained analysis, hardness in P}
}
06.09.2019
Keywords: 

bisection, convolution, treewidth, finegrained analysis, hardness in P 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 