DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.22

MaxCut Above Guarantee

Authors: Ivan Bliznets and Vladislav Epifanov

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

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.

Cite as

Ivan Bliznets and Vladislav Epifanov. MaxCut Above Guarantee. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2023.22},
  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}
}

Search Results

Documents authored by Epifanov, Vladislav

MaxCut Above Guarantee

Abstract

Cite as

Thanks for your feedback!

Could not send message