We study classes of graphs with bounded clique-width that are well-quasi-ordered by the induced subgraph relation, in the presence of labels on the vertices. We prove that, given a finite presentation of a class of graphs, one can decide whether the class is labelled-well-quasi-ordered. This answers positively to two conjectures of Pouzet in the restricted case of bounded clique-width classes. Namely, we prove that being labelled-well-quasi-ordered by a set of size 2 or by a well-quasi-ordered infinite set are equivalent conditions, and that in such cases, one can freely assume that the graphs are equipped with a total ordering on their vertices. Finally, we provide a structural characterization of those classes as those that are of bounded clique-width and do not existentially transduce the class of all finite paths.

A graph H is an induced minor of G if there exists an induced minor model of H in G , that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H , each inducing a connected subgraph in G , such that two vertices of H are adjacent if and only if there is an edge in G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K 2 , q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G , if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K 2 , 3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K 2 , 3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.

Abstract. We show that if the edges or vertices of an undirected graph [Formula: see text] can be covered by [Formula: see text] shortest paths, then the pathwidth of [Formula: see text] is upper-bounded by a single-exponential function of [Formula: see text]. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph [Formula: see text] and a set of [Formula: see text] pairs of vertices called terminals, asks whether [Formula: see text] can be covered by [Formula: see text] shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph [Formula: see text] and a set of [Formula: see text] terminals, asks whether there exist [Formula: see text] shortest paths covering [Formula: see text], each joining a distinct pair of terminals). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter [Formula: see text].

In the Trivially Perfect Editing problem one is given an undirected graph G = (V,E) and an integer k and seeks to add or delete at most k edges in G to obtain a trivially perfect graph. In a recent work, Dumas et al. [Dumas et al., 2023] proved that this problem admits a kernel with O(k³) vertices. This result heavily relies on the fact that the size of trivially perfect modules can be bounded by O(k²) as shown by Drange and Pilipczuk [Drange and Pilipczuk, 2018]. To obtain their cubic vertex-kernel, Dumas et al. [Dumas et al., 2023] then showed that a more intricate structure, so-called comb, can be reduced to O(k²) vertices. In this work we show that the bound can be improved to O(k) for both aforementioned structures and thus obtain a kernel with O(k²) vertices. Our approach relies on the straightforward yet powerful observation that any large enough structure contains unaffected vertices whose neighborhood remains unchanged by an editing of size k, implying strong structural properties.

We consider the Trivially Perfect Editing problem, where one is given an undirected graph $$G = (V,E)$$ and a parameter $$k \in {\mathbb {N}}$$ and seeks to edit (add or delete) at most k edges from G to obtain a trivially perfect graph. The related Trivially Perfect Completion and Trivially Perfect Deletion problems are obtained by only allowing edge additions or edge deletions, respectively. Trivially perfect graphs are both chordal and cographs, and have applications related to the tree-depth width parameter and to social network analysis. All variants of the problem are known to be NP-complete (Burzyn et al., in Discret Appl Math 154(13):1824–1844, 2006; Nastos and Gao, in Soc Netw 35(3):439–450, 2013) and to admit so-called polynomial kernels (Drange and Pilipczuk, in Algorithmica 80(12):3481–3524, 2018; Guo, in: Tokuyama, (ed) Algorithms and Computation, 18th International Symposium, ISAAC. Lecture Notes in Computer Science, Springer, Sendai, 2007. https://doi.org/10.1007/978-3-540-77120-3_79 ; Bathie et al., in Algorithmica 1–27, 2022). More precisely, Drange and Pilipczuk (Algorithmica 80(12):3481–3524, 2018) provided $$O(k^7)$$ vertex-kernels for these problems and left open the existence of cubic vertex-kernels. In this work, we answer positively to this question for all three variants of the problem. Notice that a quadratic vertex-kernel was recently obtained for Trivially Perfect Completion by Bathie et al. (Algorithmica 1–27, 2022).

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a function of k. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph G and a set of k terminals, asks whether there exist binom(k,2) shortest paths, each joining a distinct pair of terminals such that these paths cover G). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k.

In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $\mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G' \in \mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size $O(k/\log k)$. We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.