MaxCut Above Guarantee

Ivan Bliznets, Vladislav Epifanov

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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(k5) 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 23 |E| lower bound in tripartite graphs.

Original languageEnglish
Title of host publication48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
EditorsJerome Leroux, Sylvain Lombardy, David Peleg
PublisherDagstuhl Publishing
Number of pages14
ISBN (Electronic)9783959772921
DOIs
Publication statusPublished - 21 Aug 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume272
ISSN (Print)1868-8969

Keywords

  • Tripartite
  • 3-colorable
  • chordal
  • maximum cut
  • FPT-algorithm
  • linear kernel

Fingerprint

Dive into the research topics of 'MaxCut Above Guarantee'. Together they form a unique fingerprint.

Cite this