We study the design of robust subexponential algorithms for classical connectivity problems on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$. In this setting, each vertex corresponds to a geometric object, and two vertices are adjacent if and only if their objects intersect. We introduce a new tool for designing such algorithms, which we call a $λ$-linked partition. This is a partition of the vertex set into groups of highly connected vertices. Crucially, such a partition can be computed in polynomial time and does not require access to the geometric representation of the graph. We apply this framework to problems related to paths and cycles in graphs. First, we obtain the first robust ETH-tight algorithms for Hamiltonian Path and Hamiltonian Cycle, running in time $2^{O(n^{1-1/d})}$ on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$. This resolves an open problem of de Berg et al. [STOC 2018] and completes the study of these problems on geometric intersection graphs from the viewpoint of ETH-tight exact algorithms. We further extend our approach to the parameterized setting and design the first robust subexponential parameterized algorithm for Long Path in any fixed dimension $d$. More precisely, we obtain a randomized robust algorithm running in time $2^{O(k^{1-1/d}\log^2 k)}\, n^{O(1)}$ on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$, where $k$ is the natural parameter. Besides $λ$-linked partitions, our algorithm also relies on a low-treewidth pattern covering theorem that we establish for geometric intersection graphs, which may be viewed as a refinement of a result of Marx-Pilipczuk [ESA 2017]. This structural result may be of independent interest.

Abstract. Consider a graph [Formula: see text] with a long path [Formula: see text]. When is it the case that [Formula: see text] also contains a long induced path? This question has been investigated in general as well as within a number of different graph classes since the 1980s. We have recently observed in a companion paper [ Long induced paths in sparse graphs and graphs with forbidden patterns, preprint, arXiv:2411.08685, 2024] that most existing results can be recovered in a simple way by considering forbidden ordered patterns of edges along the path [Formula: see text]. In particular, we proved that if we forbid some fixed ordered matching along a path of order [Formula: see text] in a graph [Formula: see text], then [Formula: see text] must contain an induced path of order [Formula: see text]. Moreover, we completely characterized the forbidden ordered patterns forcing the existence of an induced path of polynomial size. The purpose of the present paper is to completely characterize the ordered patterns [Formula: see text] such that forbidding [Formula: see text] along a path [Formula: see text] of order [Formula: see text] implies the existence of an induced path of order [Formula: see text]. These patterns are star forests with some specific ordering, which we call constellations. As a direct consequence of our result, we show that if a graph [Formula: see text] has a path of length [Formula: see text] and does not contain [Formula: see text] as a topological minor, then [Formula: see text] contains an induced path of order [Formula: see text]. The previously best known bound was [Formula: see text] for some unspecified function [Formula: see text] depending on the Topological Minor Structure Theorem of Grohe and Marx (2015).

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.

The goal of local certification is to locally convince the vertices of a graph $G$ that $G$ satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether $G$ satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in $n$-vertex graphs, planarity can be certified locally with certificates of size $O(\log n)$, we show that several closely related graph classes require certificates of size $Ω(n)$. This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of $Ω(n^{1-δ})$ for any $δ>0$ on the size of the certificates, and an upper bound of $O(n \log n)$. The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.

Suppose ${\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion: given a graph $G$ and integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result in a graph that does not contain any graph from $\mathcal{F}$ as an immersion. This problem is a close relative of the $\mathcal{F}$-Minor Deletion problem studied by Fomin et al. [ Proceedings of FOCS, IEEE, 2012, pp. 470--479], where one deletes vertices in order to remove all minor models of graphs from $\mathcal{F}$. We prove that whenever all graphs from $\mathcal{F}$ are connected and at least one graph of $\mathcal{F}$ is planar and subcubic, then the $\mathcal{F}$-Immersion Deletion problem admits a constant-factor approximation algorithm running in time $\mathcal{O}(m^3 \cdot n^3 \cdot \log m)$, a linear kernel that can be computed in time $\mathcal{O}(m^4 \cdot n^3 \cdot \log m)$, and a $\mathcal{O}(2^{\mathcal{O}(k)} + m^4 \cdot n^3 \cdot \log m)$-time fixed-parameter algorithm, where $n,m$ count the vertices and edges of the input graph. These results mirror the findings of Fomin et al., who obtained a similar set of algorithmic results for $\mathcal{F}$-Minor Deletion, under the assumption that at least one graph from $\mathcal{F}$ is planar. An important difference is that we are able to obtain a linear kernel for $\mathcal{F}$-Immersion Deletion, while the exponent of the kernel of Fomin et al. for $\mathcal{F}$-Minor Deletion depends heavily on the family $\mathcal{F}$. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ ACM Trans. Algorithms, 13 (2017), p. 35]. This reveals that the kernelization complexity of $\mathcal{F}$-Immersion Deletion is quite different from that of $\mathcal{F}$-Minor Deletion.

International audience

Abstract For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This class was introduced in the early 1990s by Bíró, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Maximum Clique, Maximum Independent Set, or Minimum Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width (via mim-width). Pipelined with the plethora of known algorithms on graphs of bounded boolean-width, this describes a large class of problems solvable in polynomial time on H-graphs. We also observe that H-graphs are graphs with polynomially many minimal separators. Combined with the work of Fomin, Todinca and Villanger on algorithmic properties of such classes of graphs, this identify another wide class of problems solvable in polynomial time on H-graphs. The most fundamental optimization problems among the problems solvable in polynomial time on H-graphs are Maximum Clique, Maximum Independent Set, and Minimum Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Maximum Independent Set and Minimum Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, then Minimum Dominating Set is fixed-parameter tractable parameterized by the size of H. For Maximum Clique we show that it admits a polynomial kernel parameterized by H and the solution size.

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for K t -free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration in bipartite graphs.

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f : ℕ → ℝ such that for all k ∊ ℕ and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G–X has no H-minor. We prove that this remains true with f(k) = ck log k for some constant c = c(H). This bound is best possible, up to the value of c, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with f(k) = ck logd k for some universal constant d. The proof is constructive and yields a polynomial-time O(log OPT)-approximation algorithm for packing subgraphs containing an H-minor.

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kanté et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.

The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110:47 - 66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1):67 - 76, 1990]. This allows us to give, for every k in N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most $$2^{{O}(k^3\log k)}$$ . As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $$2^{{O}(k^2\log k)}\cdot n$$ , where k is the optimum width and n is the number of vertices. While being slower by a $$\log k$$ -factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005; J Algorithms 56(1):25–49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. These graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This notion was introduced in the early 1990s by Biro, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Clique, Independent Set, or Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width. We also prove that H-graphs are graphs with polynomially many minimal separators. Pipelined with the plethora of known algorithms on graphs of bounded boolean-width and graphs with polynomially many minimal separators, this describes a large class of optimization problems that are solvable in polynomial time on H-graphs. The most fundamental optimization problems among those solvable in polynomial time on H-graphs are Clique, Independent Set, and Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Independent Set and Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, Dominating Set is fixed-parameter tractable (FPT) parameterized by the size of H. Besides, we show that Clique admits a polynomial kernel parameterized by H and the solution size.

Given two graphs G and H, we define $$\mathsf{v}\hbox {-}\mathsf{cover}_{H}(G)$$ (resp. $$\mathsf{e}\hbox {-}\mathsf{cover}_{H}(G)$$ ) as the minimum number of vertices (resp. edges) whose removal from G produces a graph without any minor isomorphic to H. Also $$\mathsf{v}\hbox {-}\mathsf{pack}_{H}(G)$$ (resp. $$\mathsf{e}\hbox {-}\mathsf{pack}_{H}(G)$$ ) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of G that contain a minor isomorphic to H. We denote by $$\theta _{r}$$ the graph with two vertices and r parallel edges between them. When $$H=\theta _{r}$$ , the parameters $$\mathsf{v}\hbox {-}\mathsf{cover}_{H}$$ , $$\mathsf{e}\hbox {-}\mathsf{cover}_{H}$$ , $$\mathsf{v}\hbox {-}\mathsf{pack}_{H}$$ , and $$\mathsf{e}\hbox {-}\mathsf{pack}_{H}$$ are NP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large $$\theta _r$$ -girth, 2015, arXiv:1510.03041 ), we give an algorithmic proof that if $$\mathsf{v}\hbox {-}\mathsf{pack}_{{\theta _{r}}}(G)\le k$$ , then $$\mathsf{v}\hbox {-}\mathsf{cover}_{\theta _{r}}(G) = O(k\log k)$$ , and similarly for $$\mathsf{e}\hbox {-}\mathsf{pack}_{\theta _{r}}$$ and $$\mathsf{e}\hbox {-}\mathsf{cover}_{\theta _{r}}$$ . In other words, the class of graphs containing $${\theta _{r}}$$ as a minor has the vertex/edge Erdős–Pósa property, for every positive integer r. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an $$O(\log \mathrm{OPT})$$ -approximation algorithm for $$\mathsf{v}\hbox {-}\mathsf{pack}_{{\theta _{r}}}$$ , $$\mathsf{v}\hbox {-}\mathsf{cover}_{{\theta _{r}}}$$ , $$\mathsf{e}\hbox {-}\mathsf{pack}_{{\theta _{r}}}$$ , and $$\mathsf{e}\hbox {-}\mathsf{cover}_{{\theta _{r}}}$$ that runs in $$O(n\cdot \log (n)\cdot m)$$ steps. Also, we derive several new Erdős–Pósa-type results from the techniques that we introduce.

Let $W_t$ denote the wheel on t+1 vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k \geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as a minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.