Résumé
We investigate the existence in geometric graph classes of subexponential parameterized algorithms for cycle-hitting problems like \textsc{Triangle Hitting} (TH), \textsc{Feedback Vertex Set} (FVS) or \textsc{Odd Cycle Transversal} (OCT). These problems respectively ask for the existence in a graph $G$ of a set $X$ of at most $k$ vertices such that $G-X$ is triangle-free, acyclic, or bipartite. It is know that subexponential FPT algorithms of the form $2^{o(k)}n^{O(1)}$ exist in planar and even $H$-minor free graphs from bidimensionality theory [Demaine et al. 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of similarly sized ``fat'' objects ([Fomin et al. 2012]\nocite{Fomin12}, [Grigoriev et al. 2014], or disk graphs [Lokshtanov et al. 2022], [An et al. 2023]). In this paper we first identify sufficient conditions, for any graph class $\mathcal{C}$ included in string graphs, to admit subexponential FPT algorithms for any problem in $\mathcal{P}$, a family of bidimensional problems where one has to find a set of size at most $k$ hitting a fixed family of graphs, containing in particular \FVS. Informally, these conditions boil down to the fact that for any $G \in \mathcal{C}$, the \emph{local radius of $G$} (a new parameter introduced in [Lokshtanov et al. 2023]) is polynomial in the clique number of $G$ and in the maximum matching in the neighborhood of a vertex.To demonstrate the applicability of this generic result, we bound the local radius for two special classes: intersection graphs of axis-parallel squares and of contact graphs of segments in the plane. This implies that any problem $\Pi \in \mathcal{P}$ (in particular, \FVS) can be solved in:\begin{itemize} \item $2^{O(k^{3/4}\log k)}n^{O(1)}$-time in contact segment graphs, \item $2^{O(k^{9/10}\log k)}n^{O(1)}$ in intersection graphs of axis-parallel squares\end{itemize}On the positive side, we also provide positive results for Triangle Hitting by solving it in: \begin{itemize} \item $2^{O(k^{3/4}\log k)}n^{O(1)}$-time in contact segment graphs, \item $2^{O(\sqrt d t^2 (\log t) k^{2/3}\log k)} n^{O(1)}$-time in $K_{t,t}$-free \dDIR graphs (intersection of segments with at most $d$ possible slopes) \end{itemize}On the negative side, assuming the ETH we rule out the existence of algorithms solving:\begin{itemize} \item Triangle Hitting and Odd Cycle Transversal in time $2^{o(n)}$ in 2-DIR graphs and more generally in time $2^{o(\sqrt{\Delta n})}$ in 2-DIR graphs with maximum degree $\Delta$, and \item Triangle Hitting, Feedback Vrtex Set, and Odd Cycle Transversal in time $2^{o(\sqrt{n})}$ in $K_{2,2}$-free contact-2-DIR graphs of maximum degree~6.\end{itemize}Observe that together, these results show that the absence of large $K_{t,t}$ is a necessary and sufficient condition for the existence of subexponential FPT algorithms for Triangle Hitting in 2-DIR.