---
res:
  bibo_abstract:
  - '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).@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.4230/LIPIcs.IPEC.2024.2
  bibo_volume: 321
  dct_date: 2024^xs_gYear
  dct_identifier:
  - UT:001534851900002
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959773539
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík
    bound@
...