Document Open Access Logo

Bisection of Bounded Treewidth Graphs by Convolutions

Authors Eduard Eiben, Daniel Lokshtanov, Amer E. Mouawad

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.42.pdf
  • Filesize: 0.49 MB
  • 11 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Informatics, University of Bergen, Norway
Daniel Lokshtanov
  • Department of Computer Science, US Santa Barbara, United States
Amer E. Mouawad
  • Department of Computer Science, American University of Beirut, Lebanon

Cite As Get BibTex

Eduard Eiben, Daniel Lokshtanov, and Amer E. Mouawad. Bisection of Bounded Treewidth Graphs by Convolutions. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 42:1-42:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.42

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • bisection
  • convolution
  • treewidth
  • fine-grained analysis
  • hardness in P

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better Approximations for Tree Sparsity in Nearly-linear Time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 2215-2229, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3039686.3039831.
  2. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-Approximation Algorithm for Treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: http://dx.doi.org/10.1137/130947374.
  3. Hans L. Bodlaender and Torben Hagerup. Parallel Algorithms with Optimal Speedup for Bounded Treewidth. SIAM J. Comput., 27(6):1725-1746, December 1998. URL: http://dx.doi.org/10.1137/S0097539795289859.
  4. Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams. Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 375-384. IEEE Computer Society, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.48.
  5. Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171-191, 1987. Google Scholar
  6. Thang Nguyen Bui, C. Heigham, Curt Jones, and Frank Thomson Leighton. Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms. In Donald E. Thomas, editor, Proceedings of the 26th ACM/IEEE Design Automation Conference, Las Vegas, Nevada, USA, June 25-29, 1989., pages 775-778. ACM Press, 1989. URL: http://dx.doi.org/10.1145/74382.74527.
  7. Thang Nguyen Bui and Andrew Peck. Partitioning Planar Graphs. SIAM J. Comput., 21(2):203-215, 1992. Google Scholar
  8. Thang Nguyen Bui and Lisa C. Strite. An Ant System Algorithm For Graph Bisection. In GECCO, pages 43-51. Morgan Kaufmann, 2002. Google Scholar
  9. Timothy M. Chan and Moshe Lewenstein. Clustered Integer 3SUM via Additive Combinatorics. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 31-40. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746568.
  10. Bruno Courcelle. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  11. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed parameter tractable. In STOC, pages 323-332. ACM, 2014. Google Scholar
  12. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (min, +)-Convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. URL: https://dl.acm.org/citation.cfm?id=3293465, URL: http://dx.doi.org/10.1145/3293465.
  13. Uriel Feige and Robert Krauthgamer. A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput., 31(4):1090-1118, 2002. Google Scholar
  14. Uriel Feige, Robert Krauthgamer, and Kobbi Nissim. Approximating the minimum bisection size (extended abstract). In STOC, pages 530-536, 2000. Google Scholar
  15. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. M Goldberg and Z Miller. A parallel algorithm for bisection width in trees. Computers & Mathematics with Applications, 15(4):259-266, 1988. Google Scholar
  17. Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel. Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS '01, pages 365-375, Berlin, Heidelberg, 2001. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=646515.759237.
  18. Subhash Khot and Nisheeth K. Vishnoi. The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into l_1. J. ACM, 62(1):8:1-8:39, 2015. Google Scholar
  19. Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. URL: http://dx.doi.org/10.1007/BFb0045375.
  20. Robert Malcolm Macgregor. On partitioning a graph: a theoretical and empirical study. Technical report, UC Berkeley, 1979. Google Scholar
  21. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 255-264. ACM, 2008. URL: http://dx.doi.org/10.1145/1374376.1374415.
  22. René van Bevern, Andreas Emil Feldmann, Manuel Sorge, and Ondrej Suchý. On the Parameterized Complexity of Computing Graph Bisections. In WG, pages 76-87, 2013. Google Scholar
  23. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, 2018. Google Scholar
  24. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM, 65(5):27:1-27:38, August 2018. URL: http://dx.doi.org/10.1145/3186893.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact