MaxCut Above Guarantee
Publication date
2023-08-21
Authors
Bliznets, Ivan
Epifanov, Vladislav
Editors
Leroux, Jerome
Lombardy, Sylvain
Peleg, David
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
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
Citation
Bliznets, I & Epifanov, V 2023, MaxCut Above Guarantee. in J Leroux, S Lombardy & D Peleg (eds), 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)., 22, Leibniz International Proceedings in Informatics, LIPIcs, vol. 272, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2023.22