License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.40
URN: urn:nbn:de:0030-drops-84115
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8411/
Go to the corresponding LIPIcs Volume Portal

Lokshtanov, Daniel ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

Balanced Judicious Bipartition is Fixed-Parameter Tractable

pdf-format:
LIPIcs-FSTTCS-2017-40.pdf (0.7 MB)

Abstract

The family of judicious partitioning problems, introduced by Bollob\'as and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollob\'as and Scott, and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is FPT (which also proves that JB is FPT).

BibTeX - Entry

@InProceedings{lokshtanov_et_al:LIPIcs:2018:8411,
  author =	{Daniel Lokshtanov and Saket Saurabh and Roohani Sharma and Meirav Zehavi},
  title =	{{Balanced Judicious Bipartition is Fixed-Parameter Tractable}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{40:40--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8411},
  URN =		{urn:nbn:de:0030-drops-84115},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.40},
  annote =	{Keywords: Judicious Partition, Tree Decomposition, Parameterized Complexity, Odd Cycle Transversal, Minimum Bisection}
}

Keywords: Judicious Partition, Tree Decomposition, Parameterized Complexity, Odd Cycle Transversal, Minimum Bisection
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI