Source author record

Jean-Florent Raymond

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

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.

preprint2023arXiv

Long induced paths in minor-closed graph classes and beyond

In this paper we show that every graph of pathwidth less than $k$ that has a path of order $n$ also has an induced path of order at least $\frac{1}{3} n^{1/k}$ . This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound. This result is then used to prove the two following generalizations: - every graph of treewidth less than $k$ that has a path of order $n$ contains an induced path of order at least $\frac{1}{4} (\log n)^{1/k}$ ; - for every non-trivial graph class that is closed under topological minors there is a constant $d \in (0,1)$ such that every graph from this class that has a path of order $n$ contains an induced path of order at least $(\log n)^d$ . We also describe consequences of these results beyond graph classes that are closed under topological minors.

preprint2020arXiv

Enumerating minimal dominating sets in $K_t$ -free graphs and variants

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 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 variants. This answers a question of Kanté et al. about enumeration in bipartite graphs.

preprint2020arXiv

On the tractability of optimization problems on H-graphs

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 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 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 (FPT) by the size of $H$ . For Maximum Clique we show that it admits a polynomial kernel parameterized by $H$ and the solution size.

preprint2016arXiv

Linear kernels for edge deletion problems to immersion-closed graph classes

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. [FOCS 2012], 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 $O(m^3 \cdot n^3 \cdot \log m)$ ; a linear kernel that can be computed in time $O(m^4 \cdot n^3 \cdot \log m)$ ; and a $O(2^{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. [FOCS 2012], 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. [ICALP 2015]. This reveals that the kernelization complexity of $\mathcal{F}$ -Immersion Deletion is quite different than that of $\mathcal{F}$ -Minor Deletion.

preprint2016arXiv

Packing and Covering Immersion Models of Planar subcubic Graphs

A graph $H$ is an immersion of a graph $G$ if $H$ can be obtained by some sugraph $G$ after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bbb{N}\rightarrow\Bbb{N}$ , such that if $H$ is a connected planar subcubic graph on $h>0$ edges, $G$ is a graph, and $k$ is a non-negative integer, then either $G$ contains $k$ vertex/edge-disjoint subgraphs, each containing $H$ as an immersion, or $G$ contains a set $F$ of $f(k,h)$ vertices/edges such that $G\setminus F$ does not contain $H$ as an immersion.

preprint2016arXiv

Recent techniques and results on the Erdős-Pósa property

Several min-max relations in graph theory can be expressed in the framework of the Erdős-Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic.

preprint2016arXiv

Scattered packings of cycles

We consider the problem Scattered Cycles which, given a graph $G$ and two positive integers $r$ and $\ell$ , asks whether $G$ contains a collection of $r$ cycles that are pairwise at distance at least $\ell$ . This problem generalizes the problem Disjoint Cycles which corresponds to the case $\ell = 1$ . We prove that when parameterized by $r$ , $\ell$ , and the maximum degree $Δ$ , the problem Scattered Cycles admits a kernel on $24 \ell^2 Δ^\ell r \log(8 \ell^2 Δ^\ell r)$ vertices. We also provide a $(16 \ell^2 Δ^\ell)$ -kernel for the case $r=2$ and a $(148 Δr \log r)$ -kernel for the case $\ell = 1$ . Our proofs rely on two simple reduction rules and a careful analysis.

preprint2016arXiv

Well-quasi-ordering H-contraction-free graphs

A well-quasi-order is an order which contains no infinite decreasing sequence and no infinite collection of incomparable elements. In this paper, we consider graph classes defined by excluding one graph as contraction. More precisely, we give a complete characterization of graphs H such that the class of H-contraction-free graphs is well-quasi-ordered by the contraction relation. This result is the contraction analogue on the previous dichotomy theorems of Damsaschke [Induced subgraphs and well-quasi-ordering, Journal of Graph Theory, 14(4):427-435, 1990] on the induced subgraph relation, Ding [Subgraphs and well-quasi-ordering, Journal of Graph Theory, 16(5):489-502, 1992] on the subgraph relation, and Błasiok et al. [Induced minors and well-quasi-ordering, ArXiv e-prints, 1510.07135, 2015] on the induced minor relation.

preprint2015arXiv

An edge variant of the Erdős-Pósa property

For every $r\in \mathbb{N}$ , we denote by $θ_{r}$ the multigraph with two vertices and $r$ parallel edges. Given a graph $G$ , we say that a subgraph $H$ of $G$ is a model of $θ_{r}$ in $G$ if $H$ contains $θ_{r}$ as a contraction. We prove that the following edge variant of the Erd{\H o}s-P{ó}sa property holds for every $r\geq 2$ : if $G$ is a graph and $k$ is a positive integer, then either $G$ contains a packing of $k$ mutually edge-disjoint models of $θ_{r}$ , or it contains a set $S$ of $f_r(k)$ edges such that $G\setminus S$ has no $θ_{r}$ -model, for both $f_r(k) = O(k^2r^3 \mathrm{polylog}~kr)$ and $f_r(k) = O(k^4r^2 \mathrm{polylog}~kr).$

preprint2015arXiv

Low Polynomial Exclusion of Planar Graph Patterns

The celebrated grid exclusion theorem states that for every $h$ -vertex planar graph $H$ , there is a constant $c_{h}$ such that if a graph $G$ does not contain $H$ as a minor then $G$ has treewidth at most $c_{h}$ . We are looking for patterns of $H$ where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel ( $c_{h}=O(h)$ ), the double wheel ( $c_{h}=O(h^2\cdot \log^{2} h)$ ), any graph of pathwidth at most 2 ( $c_{h}=O(h^{2})$ ), and the yurt graph ( $c_{h}=O(h^{4})$ ).

preprint2013arXiv

Polynomial Gap Extensions of the Erdős-Pósa Theorem

Given a graph $H$ , we denote by ${\cal M}(H)$ all graphs that can be contracted to $H$ . The following extension of the Erdős-Pósa Theorem holds: for every $h$ -vertex planar graph $H$ , there exists a function $f_{H}$ such that every graph $G$ , either contains $k$ disjoint copies of graphs in ${\cal M}(H)$ , or contains a set of $f_{H}(k)$ vertices meeting every subgraph of $G$ that belongs in ${\cal M}(H)$ . In this paper we prove that this is the case for every graph $H$ of pathwidth at most 2 and, in particular, that $f_{H}(k) = 2^{O(h^2)}\cdot k^{2}\cdot \log k$ . As a main ingredient of the proof of our result, we show that for every graph $H$ on $h$ vertices and pathwidth at most 2, either $G$ contains $k$ disjoint copies of $H$ as a minor or the treewidth of $G$ is upper-bounded by $2^{O(h^2)}\cdot k^{2}\cdot \log k$ . We finally prove that the exponential dependence on $h$ in these bounds can be avoided if $H=K_{2,r}$ . In particular, we show that $f_{K_{2,r}}=O(r^2\cdot k^2)$

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jean-Florent Raymond

Research overview

Is this your work?

12 publications

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

Long induced paths in minor-closed graph classes and beyond

Enumerating minimal dominating sets in $K_t$ -free graphs and variants

On the tractability of optimization problems on H-graphs

Linear kernels for edge deletion problems to immersion-closed graph classes

Packing and Covering Immersion Models of Planar subcubic Graphs

Recent techniques and results on the Erdős-Pósa property

Scattered packings of cycles

Well-quasi-ordering H-contraction-free graphs

An edge variant of the Erdős-Pósa property

Low Polynomial Exclusion of Planar Graph Patterns

Polynomial Gap Extensions of the Erdős-Pósa Theorem

See the researcher in context

Building this map preview

Jean-Florent Raymond

Research overview

Is this your work?

12 publications

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

Long induced paths in minor-closed graph classes and beyond

Enumerating minimal dominating sets in KtK_tKt​-free graphs and variants

On the tractability of optimization problems on H-graphs

Linear kernels for edge deletion problems to immersion-closed graph classes

Packing and Covering Immersion Models of Planar subcubic Graphs

Recent techniques and results on the Erdős-Pósa property

Scattered packings of cycles

Well-quasi-ordering H-contraction-free graphs

An edge variant of the Erdős-Pósa property

Low Polynomial Exclusion of Planar Graph Patterns

Polynomial Gap Extensions of the Erdős-Pósa Theorem

See the researcher in context

Building this map preview

Enumerating minimal dominating sets in $K_t$ -free graphs and variants