Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, July 18, 2024, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Jonas Lill

Parameterized Algorithm for Max-Cut in Multigraphs

Max-Cut is a well-known NP-complete problem on graphs. There exists many lower bounds for Max-Cut, such as the Edwards-Erdos bound which states that any unweighted connected graph on n vertices and m edges contains a cut of size at least m/2 + (n-1)/4. For weighted graphs, we have the Poljak-Turzik bound that states that any weighted connected graph contains a cut of size at least w(G)/2 + w(MST(G))/4, where w(G) is the total weight of the graph and w(MST(G)) is the weight of the minimal spanning tree of the graph. A little over 10 years ago, Crowston, Jones and Mnich proposed a parameterized algorithm that given a parameter k and a simple unweighted graph, finds a cut of size at least the m/2 + (n-1)/4 + k if one exists of this size. In this paper they posed the open question if this result could be extended to multigraphs. During my Bachelor Thesis, I worked on finding a algorithm parameterized above the Poljak-Turzik bound that works for multigraphs, and in this talk I will show this algorithm.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login