Abstract. Given a graph [Formula: see text] and an integer [Formula: see text], let [Formula: see text] denote the minimum number of colors required to color the edges of [Formula: see text] such that, in each color class, the subgraph induced by the edges of that color has all nonzero degrees congruent to 1 modulo [Formula: see text]. In 1992, Pyber proved that [Formula: see text] for every graph [Formula: see text], and posed the question of whether [Formula: see text] can be bounded solely in terms of [Formula: see text] for every [Formula: see text]. This question was answered in 1997 by Scott, who showed that [Formula: see text], and further asked whether [Formula: see text]. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively proving that [Formula: see text], and conjectured that the multiplicative constant could be reduced to 1. A step towards this latter conjecture was made in 2024 by Nweit and Yang, who improved the bound to [Formula: see text]. In this paper, we further improve the multiplicative constant to 9. More specifically, we prove that there is a function [Formula: see text] for which [Formula: see text] if [Formula: see text] is odd, and [Formula: see text] if [Formula: see text] is even. In doing so, we prove that [Formula: see text] for every [Formula: see text]-degenerate graph [Formula: see text], which plays a central role in our proof.

The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph $G$ and a parameter $k$, one has to decide if there is a set $S$ of at most $k$ vertices such that $G-S$ is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time $2^{o(k)}n^{\mathcal{O}(1)}$ in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such $2^{o(k)}n^{\mathcal{O}(1)}$ algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time $2^{k^\varepsilon} \mathop{\rm poly}(n)$, for some $\varepsilon<1$, where $n$ denotes the number of vertices of the instance and $k$ the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of ``thin'' objects like segment graphs or more generally $s$-string graphs.

In the $K_r$-Cover problem, given a graph $G$ and an integer $k$ one has to decide if there exists a set of at most $k$ vertices whose removal destroys all $r$-cliques of $G$. In this paper we give an algorithm for $K_r$-Cover that runs in subexponential FPT time on graph classes satisfying two simple conditions related to cliques and treewidth. As an application we show that our algorithm solves $K_r$-Cover in time * $2^{O_r\left (k^{(r+1)/(r+2)}\log k \right)} \cdot n^{O_r(1)}$ in pseudo-disk graphs and map-graphs; * $2^{O_{t,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $K_{t,t}$-subgraph-free string graphs; and * $2^{O_{H,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $H$-minor-free graphs.

We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.

We describe DreyFVS, a heuristic for Directed Feedback Vertex Set submitted to the 2022 edition of Parameterized Algorithms and Computational Experiments Challenge. The Directed Feedback Vertex Set problem asks to remove a minimal number of vertices from a digraph such that the resulting digraph is acyclic. Our algorithm first performs a guess on a reduced instance by leveraging the Sinkhorn-Knopp algorithm, to then improve this solution by pipelining two local search methods.