---
OA_place: publisher
OA_type: gold
_id: '18758'
abstract:
- lang: eng
text: 'MaxCut is a classical NP-complete problem and a crucial building block in
many combinatorial algorithms. The famous Edwards-Erdős bound states that any
connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4.
Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem
on simple connected graphs admits an FPT algorithm, where the parameter k is the
difference between the desired cut size c and the lower bound given by the Edwards-Erdős
bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run
in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in
two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively,
graphs with positive integer weights). Secondly, we change the parameter; instead
of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík
bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size
at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and
w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple
graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound
can be larger and thus yield a smaller parameter k. Our algorithm also runs in
parameterized linear time, i.e., f(k)⋅ O(m+n).'
acknowledgement: "Kalina Petrova: Swiss National Science Foundation, grant no. CRSII5
173721. This project\r\nhas received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 101034413.\r\nSimon Weber: Swiss National Science Foundation under project no.
204320"
alternative_title:
- LIPIcs
article_number: '2'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Jonas
full_name: Lill, Jonas
last_name: Lill
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
- first_name: Simon
full_name: Weber, Simon
last_name: Weber
citation:
ama: 'Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound. In: 19th International Symposium on Parameterized
and Exact Computation. Vol 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2024. doi:10.4230/LIPIcs.IPEC.2024.2'
apa: 'Lill, J., Petrova, K. H., & Weber, S. (2024). Linear-time MaxCut in multigraphs
parameterized above the Poljak-Turzík bound. In 19th International Symposium
on Parameterized and Exact Computation (Vol. 321). Egham, United Kingdom:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2024.2'
chicago: Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in
Multigraphs Parameterized above the Poljak-Turzík Bound.” In 19th International
Symposium on Parameterized and Exact Computation, Vol. 321. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.IPEC.2024.2.
ieee: J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound,” in 19th International Symposium on Parameterized
and Exact Computation, Egham, United Kingdom, 2024, vol. 321.
ista: 'Lill J, Petrova KH, Weber S. 2024. Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound. 19th International Symposium on Parameterized and
Exact Computation. IPEC: Symposium on Parameterized and Exact Computation, LIPIcs,
vol. 321, 2.'
mla: Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above
the Poljak-Turzík Bound.” 19th International Symposium on Parameterized and
Exact Computation, vol. 321, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024, doi:10.4230/LIPIcs.IPEC.2024.2.
short: J. Lill, K.H. Petrova, S. Weber, in:, 19th International Symposium on Parameterized
and Exact Computation, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-06
location: Egham, United Kingdom
name: 'IPEC: Symposium on Parameterized and Exact Computation'
start_date: 2024-09-04
corr_author: '1'
date_created: 2025-01-05T23:01:57Z
date_published: 2024-12-05T00:00:00Z
date_updated: 2026-01-05T13:46:07Z
day: '05'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.4230/LIPIcs.IPEC.2024.2
ec_funded: 1
external_id:
arxiv:
- '2407.01071'
isi:
- '001534851900002'
file:
- access_level: open_access
checksum: a64b9a0e41f7b867d25cb155825ccd53
content_type: application/pdf
creator: dernst
date_created: 2025-01-08T09:14:59Z
date_updated: 2025-01-08T09:14:59Z
file_id: '18775'
file_name: 2024_LIPIcs_Lill.pdf
file_size: 927326
relation: main_file
success: 1
file_date_updated: 2025-01-08T09:14:59Z
has_accepted_license: '1'
intvolume: ' 321'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 19th International Symposium on Parameterized and Exact Computation
publication_identifier:
isbn:
- '9783959773539'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '19603'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 321
year: '2024'
...