---
res:
  bibo_abstract:
  - "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).@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Jonas
      foaf_name: Lill, Jonas
      foaf_surname: Lill
  - foaf_Person:
      foaf_givenName: Kalina H
      foaf_name: Petrova, Kalina H
      foaf_surname: Petrova
      foaf_workInfoHomepage: http://www.librecat.org/personId=554ff4e4-f325-11ee-b0c4-a10dbd523381
  - foaf_Person:
      foaf_givenName: Simon
      foaf_name: Weber, Simon
      foaf_surname: Weber
  bibo_doi: 10.1007/s00453-025-01306-y
  bibo_volume: 87
  dct_date: 2025^xs_gYear
  dct_identifier:
  - UT:001463103800001
  dct_isPartOf:
  - http://id.crossref.org/issn/0178-4617
  - http://id.crossref.org/issn/1432-0541
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík
    bound@
...