Abstract MaxCut is a classical $$\textsf{NP}$$ 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 $$\frac{m}{2}+\frac{n-1}{4}$$ 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)\cdot O(m)$$ 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 weight at least $$\frac{w(G)}{2}+\frac{w_{MSF}(G)}{4}$$ w ( G ) 2 + w MSF ( G ) 4 , where w(G) denotes the total weight of G, and $$w_{MSF}(G)$$ 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)\cdot O(m+n)$$ f ( k ) · O ( m + n ) .

In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HRG. Despite the wide success of the models, the parameter regime in which graph distances are polylogarithmic is poorly understood. We provide new and improved lower bounds. In a certain portion of the parameter regime, those match the known upper bounds. Compared to the best previous lower bounds by Hao and Heydenreich, our result has several advantages: it gives matching bounds for a larger range of parameters, thus settling the question for a larger portion of the parameter space. It strictly improves the lower bounds by Hao and Heydenreich for all parameters settings in which those bounds were not tight. It gives tail bounds on the probability of having short paths, which imply shape theorems for the $k$-neighbourhood of a vertex whenever our lower bounds are tight, and tight bounds for the size of this $k$-neighbourhood. And last but not least, our proof is much simpler and not much longer than two pages, and we demonstrate that it generalizes well by showing that the same technique also works for first passage percolation.