Édouard Bonnet

Édouard Bonnet, Hung Le, Marcin Pilipczuk et al.

Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just being disjoint. In this paper, we give a coarse analogue of the classic theorem that an $n$-vertex graph excluding a fixed minor admits a balanced separator of size $O(\sqrt{n})$. Specifically, we prove that for every integer $d$, real $\varepsilon>0$, and graph $H$, there exist constants $c$ and $r$ such that every $n$-vertex graph $G$ excluding $H$ as a $d$-fat minor admits a set $S \subseteq V(G)$ that is a balanced separator of $G$ and can be covered by $c n^{\frac{1}{2}+\varepsilon}$ balls of radius $r$ in $G$. Our proof also works in the weighted setting where the balance of the separator is measured with respect to any weight function on the vertices, and is effective: we obtain a randomized polynomial-time algorithm to compute either such a balanced separator, or a $d$-fat model of $H$ in $G$.

Édouard Bonnet, Yeonsu Chang, Julien Duron et al.

Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operatorname{cml}^\downarrow$, where component max-leaf is the maximum number of leaves in any spanning tree of any connected component. Reduced component max-leaf is strictly sandwiched between clique-width and reduced bandwidth, it is bounded in unit interval graphs, and unbounded in planar graphs. We design polynomial-time algorithms for problems such as \textsc{Maximum Induced $d$-Regular Subgraph} and \textsc{Induced Disjoint Paths} in graphs given with a contraction sequence witnessing low $\operatorname{cml}^\downarrow$, unifying and extending tractability results for classes of bounded clique-width and unit interval graphs. We get the following collapses in sparse classes of bounded $\operatorname{cml}^\downarrow$: bounded maximum degree implies bounded treewidth, whereas $K_{t,t}$-subgraph-freeness implies strongly sublinear treewidth; we show the latter, more generally, for classes of bounded reduced cutwidth. We establish the former result by showing that graphs with bounded $\operatorname{cml}^\downarrow$ admit balanced separators dominated by a bounded number of vertices. We then showcase an application of the reduced parameters to establishing non-transducibility results. We prove that for most reduced parameters $p^\downarrow$ (including reduced bandwidth), the family of classes of bounded $p^\downarrow$ is closed under first-order transductions. We then answer a question of [BKW '26] by showing that the 3-dimensional grids have unbounded reduced bandwidth. As the class of planar graphs (or any class of bounded genus) has bounded reduced bandwidth [BKW '26], this reproves a recent result [GPP, LICS '25] that planar graphs do not first-order transduce the 3-dimensional grids.

Édouard Bonnet

We introduce the meta-problem Sidestep$(Π, \mathsf{dist}, d)$ for a problem $Π$, a metric $\mathsf{dist}$ over its inputs, and a map $d: \mathbb N \to \mathbb R_+ \cup \{\infty\}$. A solution to Sidestep$(Π, \mathsf{dist}, d)$ on an input $I$ of $Π$ is a pair $(J, Π(J))$ such that $\mathsf{dist}(I,J) \leqslant d(|I|)$ and $Π(J)$ is a correct answer to $Π$ on input $J$. This formalizes the notion of answering a related question (or sidestepping the question), for which we give some motivations, and compare it to the neighboring concepts of smoothed analysis, certified algorithms, planted problems, edition problems, and approximation algorithms. Informally, we call hardness radius the ``largest'' $d$ such that Sidestep$(Π, \mathsf{dist}, d)$ is NP-hard. This framework calls for establishing the hardness radius of problems $Π$ of interest for the relevant distances $\mathsf{dist}$. We exemplify it with graph problems and two distances $\mathsf{dist}_Δ$ and $\mathsf{dist}_e$ (the edge edit distance) such that $\mathsf{dist}_Δ(G,H)$ (resp. $\mathsf{dist}_e(G,H)$) is the maximum degree (resp. number of edges) of the symmetric difference of $G$ and $H$ if these graphs are on the same vertex set, and $+\infty$ otherwise. We show that the decision problems Independent Set, Clique, Vertex Cover, Coloring, Clique Cover have hardness radius $n^{\frac{1}{2}-o(1)}$ for $\mathsf{dist}_Δ$, and $n^{\frac{4}{3}-o(1)}$ for $\mathsf{dist}_e$, that Hamiltonian Cycle has hardness radius 0 for $\mathsf{dist}_Δ$, and somewhere between $n^{\frac{1}{2}-o(1)}$ and $n/3$ for $\mathsf{dist}_e$, and that Dominating Set has hardness radius $n^{1-o(1)}$ for $\mathsf{dist}_e$. We leave several open questions.

Édouard Bonnet, Florian Jamain, Abdallah Saffidine

In this paper, we study three connection games among the most widely played: Havannah, Twixt, and Slither. We show that determining the outcome of an arbitrary input position is PSPACE-complete in all three cases. Our reductions are based on the popular graph problem Generalized Geography and on Hex itself. We also consider the complexity of generalizations of Hex parameterized by the length of the solution and establish that while Short Generalized Hex is W[1]-hard, Short Hex is FPT. Finally, we prove that the ultra-weak solution to the empty starting position in hex cannot be fully adapted to any of these three games.