---
OA_place: publisher
OA_type: hybrid
_id: '19603'
abstract:
- lang: eng
  text: "MaxCut is a classical NP-complete problem and a crucial building block in
    many\r\ncombinatorial algorithms. The famousEdwards-Erdös bound states that any
    connected\r\ngraph on n vertices with m edges contains a cut of size at least
    m/2 + n−1/4 . Crowston,\r\nJones and Mnich [Algorithmica, 2015] showed that the
    MaxCut problem on simple\r\nconnected graphs admits an FPT algorithm, where the
    parameter k is the difference\r\nbetween the desired cut size c and the lower
    bound given by the Edwards-Erdös\r\nbound. This was later improved by Etscheid
    and Mnich [Algorithmica, 2017] to run\r\nin parameterized linear time, i.e., f
    (k) · O(m). We improve upon this result in two\r\nways: Firstly, we extend the
    algorithm to work also for multigraphs (alternatively,\r\ngraphs with positive
    integer weights). Secondly, we change the parameter; instead of\r\nthe difference
    to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík\r\nbound.
    The Poljak-Turzík bound states that any weighted graph G has a cut of weight\r\nat
    least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF
    (G)\r\ndenotes the weight of its minimum spanning forest. In connected simple
    graphs the\r\ntwo bounds are equivalent, but for multigraphs the Poljak-Turzík
    bound can be larger\r\nand thus yield a smaller parameter k. Our algorithm also
    runs in parameterized linear\r\ntime, i.e., f (k) · O(m + n)."
acknowledgement: "Kalina Petrova is supported by the Swiss National Science Foundation,
  grant no. CRSII5 173721, and also receives funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
  No 101034413. Simon Weber is supported by the Swiss National Science Foundation
  under project no. 204320.\r\nOpen access funding provided by Swiss Federal Institute
  of Technology Zurich."
article_processing_charge: Yes (via OA deal)
article_type: original
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. <i>Algorithmica</i>. 2025;87:983-1007. doi:<a href="https://doi.org/10.1007/s00453-025-01306-y">10.1007/s00453-025-01306-y</a>
  apa: Lill, J., Petrova, K. H., &#38; Weber, S. (2025). Linear-time MaxCut in multigraphs
    parameterized above the Poljak-Turzík bound. <i>Algorithmica</i>. Springer Nature.
    <a href="https://doi.org/10.1007/s00453-025-01306-y">https://doi.org/10.1007/s00453-025-01306-y</a>
  chicago: Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in
    Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>Algorithmica</i>.
    Springer Nature, 2025. <a href="https://doi.org/10.1007/s00453-025-01306-y">https://doi.org/10.1007/s00453-025-01306-y</a>.
  ieee: J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized
    above the Poljak-Turzík bound,” <i>Algorithmica</i>, vol. 87. Springer Nature,
    pp. 983–1007, 2025.
  ista: Lill J, Petrova KH, Weber S. 2025. Linear-time MaxCut in multigraphs parameterized
    above the Poljak-Turzík bound. Algorithmica. 87, 983–1007.
  mla: Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above
    the Poljak-Turzík Bound.” <i>Algorithmica</i>, vol. 87, Springer Nature, 2025,
    pp. 983–1007, doi:<a href="https://doi.org/10.1007/s00453-025-01306-y">10.1007/s00453-025-01306-y</a>.
  short: J. Lill, K.H. Petrova, S. Weber, Algorithmica 87 (2025) 983–1007.
date_created: 2025-04-20T22:01:28Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2026-01-05T13:46:08Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1007/s00453-025-01306-y
ec_funded: 1
external_id:
  isi:
  - '001463103800001'
file:
- access_level: open_access
  checksum: eab3f1834b0ba347b05ae9897729c0ad
  content_type: application/pdf
  creator: dernst
  date_created: 2026-01-05T13:45:57Z
  date_updated: 2026-01-05T13:45:57Z
  file_id: '20957'
  file_name: 2025_Algorithmica_Lill.pdf
  file_size: 448554
  relation: main_file
  success: 1
file_date_updated: 2026-01-05T13:45:57Z
has_accepted_license: '1'
intvolume: '        87'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 983-1007
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '18758'
    relation: earlier_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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2025'
...