License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.22
URN: urn:nbn:de:0030-drops-185560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18556/
Go to the corresponding LIPIcs Volume Portal

Bliznets, Ivan ; Epifanov, Vladislav

MaxCut Above Guarantee

pdf-format:
LIPIcs-MFCS-2023-22.pdf (0.8 MB)

Abstract

In this paper, we study the computational complexity of the Maximum Cut problem parameterized above guarantee. Our main result provides a linear kernel for the Maximum Cut problem in connected graphs parameterized above the spanning tree. This kernel significantly improves the previous O(k⁵) kernel given by Madathil, Saurabh, and Zehavi [ToCS 2020]. We also provide subexponential running time algorithms for this problem in special classes of graphs: chordal, split, and co-bipartite. We complete the picture by lower bounds under the assumption of the ETH. Moreover, we initiate a study of the Maximum Cut problem above 2/3|E| lower bound in tripartite graphs.

BibTeX - Entry

@InProceedings{bliznets_et_al:LIPIcs.MFCS.2023.22,
  author =	{Bliznets, Ivan and Epifanov, Vladislav},
  title =	{{MaxCut Above Guarantee}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18556},
  URN =		{urn:nbn:de:0030-drops-185560},
  doi =		{10.4230/LIPIcs.MFCS.2023.22},
  annote =	{Keywords: Tripartite, 3-colorable, chordal, maximum cut, FPT-algorithm, linear kernel}
}

Keywords: Tripartite, 3-colorable, chordal, maximum cut, FPT-algorithm, linear kernel
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

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