@inproceedings{5f7fad58705c496ba3de73d0e0b7a7d1,
title = "MaxCut Above Guarantee",
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.",
keywords = "Tripartite, 3-colorable, chordal, maximum cut, FPT-algorithm, linear kernel",
author = "Ivan Bliznets and Vladislav Epifanov",
note = "Funding Information: Funding Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No. 853234). Publisher Copyright: {\textcopyright} Ivan Bliznets and Vladislav Epifanov;",
year = "2023",
month = aug,
day = "21",
doi = "10.4230/LIPIcs.MFCS.2023.22",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Dagstuhl Publishing",
editor = "Jerome Leroux and Sylvain Lombardy and David Peleg",
booktitle = "48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)",
}