We prove that an $\varepsilon$-approximate fixpoint of a map $f:[0,1]^{d} \rightarrow[0,1]^{d}$ can be found with $\mathcal{O}\left(d^{2}\left(\log \frac{1}{\varepsilon}+\log \frac{1}{1-\lambda}\right)\right)$ queries to f if f is $\lambda$-contracting with respect to an $\ell_{p}$-metric for some $p \in[1, \infty) \cup\{\infty\}$. This generalizes a recent result of Chen, Li, and Yannakakis [STOC 2024] from the $\ell_{\infty}$-case to all $\ell_{p}$ metrics. Previously, all query upper bounds for $p \in[1, \infty) \backslash\{2\}$ were either exponential in $d, \log \frac{1}{\varepsilon}$, or $\log \frac{1}{1-\lambda}$. Chen, Li, and Yannakakis also show how to ensure that all queries to f lie on a discrete grid of limited granularity in the $\ell_{\infty}$-case. We provide such a rounding for the $\ell_{1}$-case, placing an appropriately defined version of the $\ell_{1}$-case in FPdt. To prove our results, we introduce the notion of $\ell_{p}$-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any $p \in[1, \infty) \cup\{\infty\}$ and any mass distribution (or point set), we prove that there exists a centerpoint c such that every $\ell_{p}$-halfspace defined by c and a normal vector contains at least a $\frac{1}{d+1}$-fraction of the mass (or points).

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 ) .