MaxCut Above Guarantee

Ivan Bliznets; Vladislav Epifanov

doi:10.4230/LIPIcs.MFCS.2023.22

MaxCut Above Guarantee

Ivan Bliznets, Vladislav Epifanov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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(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 ²₃ |E| lower bound in tripartite graphs.

Original language	English
Title of host publication	48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Editors	Jerome Leroux, Sylvain Lombardy, David Peleg
Publisher	Dagstuhl Publishing
Number of pages	14
ISBN (Electronic)	9783959772921
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2023.22
Publication status	Published - 21 Aug 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	272
ISSN (Print)	1868-8969

Bibliographical note

Funding Information:
Funding Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 853234).

Publisher Copyright:
© Ivan Bliznets and Vladislav Epifanov;

Keywords

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

Access to Document

10.4230/LIPIcs.MFCS.2023.22Licence: CC BY

LIPIcs-MFCS-2023-22Final published version, 815 KBLicence: CC BY

Cite this

@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)",

}

MaxCut Above Guarantee. / Bliznets, Ivan; Epifanov, Vladislav.
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). ed. / Jerome Leroux; Sylvain Lombardy; David Peleg. Dagstuhl Publishing, 2023. 22 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - MaxCut Above Guarantee

AU - Bliznets, Ivan

AU - Epifanov, Vladislav

N1 - Funding Information: Funding Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 853234). Publisher Copyright: © Ivan Bliznets and Vladislav Epifanov;

PY - 2023/8/21

Y1 - 2023/8/21

N2 - 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.

AB - 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.

KW - Tripartite

KW - 3-colorable

KW - chordal

KW - maximum cut

KW - FPT-algorithm

KW - linear kernel

UR - http://www.scopus.com/inward/record.url?scp=85171448756&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2023.22

DO - 10.4230/LIPIcs.MFCS.2023.22

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

A2 - Leroux, Jerome

A2 - Lombardy, Sylvain

A2 - Peleg, David

PB - Dagstuhl Publishing

ER -

MaxCut Above Guarantee

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this