Enumerative kernelization is a relatively recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms, with two main models being proposed. The first, known as enum-kernels and due to Creignou et al. [Theory Comput. Syst., 2017], was too permissive, leading to constant-sized kernels for every problem solvable with FPT-delay. To remedy this, Golovach et al. [J. Comput. Syst. Sci., 2022] proposed the polynomial-delay enumeration kernelization model that, while addressing the shortcoming of the previous one, appears to be too strict, which we believe is a central reason for the slow development that the area has enjoyed so far. In this paper, we propose a new model for enumeration kernels, which we have called polynomial-delay (PD) kernels. It is more flexible than Golovach et al.’s kernels while still preserving their qualities; informally, it allows us to ignore "bad" solutions of the compressed instance when producing the solution set of the input instance, but still requires that the "good" solutions are lifted with polynomial-delay. After discussing the main properties of our model, we design a generic framework for vertex-subset problems to adapt decision kernels into PD kernels of the same size. We showcase our model’s increased versatility and the expressive power of our framework on the Enum Vertex Cover problem, where we want to list all vertex covers of size at most k of a given graph. In particular, we manage to generalize the kernelization dichotomy by Bougeret et al. [SIAM J. Discrete Math., 2022] about the existence of polynomial kernels for Vertex Cover parameterized by the vertex deletion distance to a minor-closed graph class, as well as the solution size and feedback vertex number parameterizations. The second one, in particular, is significantly simpler than the kernel designed by Bougeret et al. [IPEC, 2025], requiring only a few lines for its lifting algorithm. Beyond our framework, we also show how to generalize to the enumeration setting the kernel of Bougeret et al. [Algorithmica, 2019] for the vertex-deletion distance to c-treedepth.

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions of first-order logic such as FO+dp admit efficient model checking on graph classes excluding a fixed topological minor, comparable results for richer fragments of CMSO were previously unknown. We further develop the framework of Sau, Stamoulis, and Thilikos [SODA 2025] for fragmenting CMSO via annotated graph parameters, which restrict set quantification to vertex sets satisfying bounded structural conditions. Following this approach, we identify a fragment of CMSO, namely the one defined by allowing quantification only over sets having what we call low monodimensionality, that generalizes several previously-known logics and we show that model checking for this fragment, enhanced with the disjoint-paths predicate, is fixed-parameter tractable on topological-minor-free graph classes. Such classes essentially delimit the tractability for this logic on subgraph-closed classes. As a consequence, our results lift several known algorithmic meta-theorems beyond first-order logic to the topological-minor-free setting.

For a finite collection of connected graphs $\mathcal{F}$, the $\mathcal{F}$-MINOR-DELETION problem consists in, given a graph $G$ and an integer $\ell$, deciding whether $G$ contains a vertex set of size at most $\ell$ whose removal results in an $\mathcal{F}$-minor-free graph. We lift the existence of (approximate) polynomial kernels for $\mathcal{F}$-MINOR-DELETION by the solution size to (approximate) polynomial kernels parameterized by the vertex-deletion distance to graphs of bounded elimination distance to $\mathcal{F}$-minor-free graphs. This results in exact polynomial kernels for every family $\mathcal{F}$ that contains a planar graph, and an approximate polynomial kernel for PLANAR VERTEX DELETION. Moreover, combining our result with a previous lower bound, we obtain the following infinite set of dichotomies, assuming $NP \not\subseteq coNP/poly$: for any finite set $\mathcal{F}$ of biconnected graphs on at least three vertices containing a planar graph, and any minor-closed class of graphs $\mathcal{C}$, $\mathcal{F}$-MINOR-DELETION admits a polynomial kernel parameterized by the vertex-deletion distance to $\mathcal{C}$ if and only if $\mathcal{C}$ has bounded elimination distance to $\mathcal{F}$-minor-free graphs. For instance, this yields dichotomies for CACTUS VERTEX DELETION, OUTERPLANAR VERTEX DELETION, and TREEWIDTH-$t$ VERTEX DELETION for every integer $t \geq 0$. Prior to our work, such dichotomies were only known for the particular cases of VERTEX COVER and FEEDBACK VERTEX SET. We also provide lower bounds on the size of the kernels.

A replacement action is a function ℒ that maps each graph H to a collection of graphs of size at most |V(H)|. Given a graph class ℋ, we consider a general family of graph modification problems, called ℒ-Replacement to ℋ, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H₁ of G on at most k vertices by a graph H₂ in ℒ(H₁) so that the resulting graph belongs to ℋ. ℒ-Replacement to ℋ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves ℒ-Replacement to ℋ in time 2^poly(k) ⋅ |V(G)|² for every minor-closed graph class ℋ, where poly is a polynomial whose degree depends on ℋ, under a mild technical condition on ℒ. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to ℋ within the same running time. Our second algorithm is an improvement of the first one when ℋ is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2^𝒪(k⁹) ⋅ |V(G)|², where the 𝒪(⋅) notation depends on g. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.

An elimination tree of a connected graph G is a rooted tree on the vertices of G obtained by choosing a root v and recursing on the connected components of G-v to obtain the subtrees of v. The graph associahedron of G is a polytope whose vertices correspond to elimination trees of G and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where G is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph G, is fixed-parameter tractable parameterized by the distance k. Prior to our work, only the case where G is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of k.

In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when c ≤ k/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is W[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal.

Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creignou et al. [Theory Comput. Syst., 2017], and development in the area has started to accelerate with the work of Golovach et al. [J. Comput. Syst. Sci., 2022]. The latter introduced polynomial-delay enumeration kernels and applied them in the study of structural parameterizations of the Matching Cut problem and some variants. Few other results, mostly on Longest Path and some generalizations of Matching Cut, have also been developed. However, little success has been seen in enumeration versions of Vertex Cover and Feedback Vertex Set, some of the most studied problems in kernelization. In this paper, we address this shortcoming. Our first result is a polynomial-delay enumeration kernel with 2k vertices for Enum Vertex Cover, where we wish to list all solutions with at most k vertices. This is obtained by developing a non-trivial lifting algorithm for the classical crown decomposition reduction rule, and directly improves upon the kernel with 𝒪(k²) vertices derived from the work of Creignou et al. Our other result is a polynomial-delay enumeration kernel with 𝒪(k³) vertices and edges for Enum Feedback Vertex Set; the proof is inspired by some ideas of Thomassé [TALG, 2010], but with a weaker bound on the kernel size due to difficulties in applying the q-expansion technique.

It is well known that directed treewidth does not enjoy the nice algorithmic properties of its undirected counterpart. There exist, however, some positive results that, essentially, present XP algorithms for the problem of finding, in a given digraph D , a subdigraph isomorphic to a digraph H that can be formed by the union of k directed paths (with some extra properties), parameterized by k and the directed treewidth of D . Our motivation is to tackle the following question: Are there subdigraphs, other than the directed paths, that can be found efficiently in digraphs of bounded directed treewidth? In a nutshell, the main message of this article is that, other than the directed paths, the only digraphs that seem to behave well with respect to directed treewidth are the stars. For this, we present a number of positive and negative results, generalizing several results in the literature, as well as some directions for further research.

Given a graph G , a matching is a subset of edges of G that do not share an endpoint. A matching M is uniquely restricted if the subgraph induced by the endpoints of the edges of M has exactly one perfect matching. Given a graph G and a positive integer ℓ , Uniquely Restricted Matching asks whether G has a uniquely restricted matching of size at least ℓ . In this paper, we study the parameterized complexity of Uniquely Restricted Matching under various parameters. Specifically, we show that Uniquely Restricted Matching admits a fixed-parameter tractable (FPT) algorithm on line graphs when parameterized by the solution size. We also establish that the problem is FPT when parameterized by the treewidth of the input graph. Furthermore, we show that Uniquely Restricted Matching does not admit a polynomial kernel with respect to the vertex cover number plus the size of the matching unless NP ⊆ coNP/poly.

Given a graph G and a vertex set X, the annotated treewidth tw(G,X ) of X in G is the maximum treewidth of an X-rooted minor of G, i.e., a minor H where the model of each vertex of H contains some vertex of X. That way, tw(G, X ) can be seen as a measure of the contribution of X to the tree-decomposability of G. We introduce the logic CMSO/tw as the fragment of monadic second-order logic on graphs obtained by restricting set quantification to sets of bounded annotated treewidth. We prove the following Algorithmic Meta-Theorem (AMT): for every non-trivial minor-closed graph class, model checking for CMSO/tw formulas can be done in quadratic time. Our proof works for the more general CMSO/tw+dp logic, that is CMSO/tw enhanced by disjoint-path predicates. Our AMT can be seen as an extension of Courcelle’s theorem to minor-closed graph classes where the bounded-treewidth condition in the input graph is replaced by the bounded-treewidth quantification in the formulas. Our results yield, as special cases, all known AMTs whose combinatorial restriction is non-trivial minor-closedness.

We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of constant congestion from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger’s Theorem on appropriately defined digraphs, and an alternative simpler one using matroids, however with worse polynomial running time. As an application, we manage to simplify and improve several results of Edwards et al. in 2017 and of Giannopoulou et al. in 2022 about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology. We hope that our min-max relations will find further applications as, in our opinion, they are simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence , defining some property of the modified part of the graph, and the target sentence , defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic ( CMSO ) and have models of bounded treewidth, while target sentences express first-order logic ( FO ) properties. Our logic captures problems that are not definable in FO and, moreover, may have instances of unbounded treewidth. Our main result is that, for this compound logic, model-checking can be done in quadratic time on minor-free graphs. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique . It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle’s theorem and Gaifman’s theorem. Our algorithmic meta-theorem encompasses, unifies, and extends the known meta-algorithmic results for CMSO and FO on minor-closed graph classes.

For a fixed graph $H$, the $H$-SUBGRAPH HITTING problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of $H$ as a subgraph. This problem can be seen as a generalization of VERTEX COVER, which corresponds to the case $H = K_2$. We initiate a study of $H$-SUBGRAPH HITTING from the point of view of characterizing structural parameterizations that allow for polynomial kernels, within the recently active framework of taking as the parameter the number of vertex deletions to obtain a graph in a "simple" class $C$. Our main contribution is to identify graph parameters that, when $H$-SUBGRAPH HITTING is parameterized by the vertex-deletion distance to a class $C$ where any of these parameters is bounded, and assuming standard complexity assumptions and that $H$ is biconnected, allow us to prove the following sharp dichotomy: the problem admits a polynomial kernel if and only if $H$ is a clique. These new graph parameters are inspired by the notion of $C$-elimination distance introduced by Bulian and Dawar [Algorithmica 2016], and generalize it in two directions. Our results also apply to the version of the problem where one wants to hit $H$ as an induced subgraph, and imply in particular, that the problems of hitting minors and hitting (induced) subgraphs have a substantially different behavior with respect to the existence of polynomial kernels under structural parameterizations.

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. Finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations, some distance metrics have been extensively studied. We investigate median and closest problems on permutations over the metrics: breakpoint, swap, block-interchange, short-block-move, and transposition. In biological matters some values are usually small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation for some metrics, even for k = 3; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics parameterized by the target distance d.

International audience

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or $\mathcal{G}$-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle's theorem and Gaifman's theorem. We finally prove extensions where the target property is expressible in FOL+DP, i.e., the enhancement of FOL with disjoint-paths predicates.

Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^poly(k)⋅n². This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2^poly(k)⋅n³. The elimination distance of G to G, denoted by ed_G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] proved the existence of an FPT-algorithm, with parameter k, to decide whether ed_G(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_G(G) ≤ k in time 2^{2^{2^poly(k)}}⋅n². This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^{2^O(k²log k)}⋅n² and one running in time 2^{poly(k)}⋅n³. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_G(G) ≤ k in time 2^O(tw⋅ k + tw log tw)⋅n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on G. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs E_k(G) = {G ∣ ed_G(G) ≤ k}.

We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.

Given a graph G on n vertices and two integers k and d, the Contraction(vc) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] proved that Contraction(vc) admits an XP algorithm running in time f(d)⋅nO(d). They asked whether this problem is FPT under this parameterization. In this article, we prove that: (i) Contraction(vc) is W[1]-hard parameterized by k+d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k+d)⋅no(k+d) for any function f. This answers negatively the open question stated in Lima et al. [JCSS 2021]. (ii) Contraction(vc) is NP-hard even when k=d. (iii) Contraction(vc) can be solved in time 2O(d)⋅nk−d+O(1). This improves the algorithm of Lima et al. [JCSS 2021], and shows that when k=d, Contraction(vc) is FPT parameterized by d (or by k).

Abstract. For a fixed finite collection of graphs [Formula: see text] the [Formula: see text]-M-Deletion problem is as follows: given an [Formula: see text]-vertex input graph [Formula: see text] find the minimum number of vertices that intersect all minor models in [Formula: see text] of the graphs in [Formula: see text]. by Courcelle’s Theorem, this problem can be solved in time [Formula: see text] where [Formula: see text] is the treewidth of [Formula: see text] for some function [Formula: see text] depending on [Formula: see text]. In a recent series of articles, we have initiated the program of optimizing asymptotically the function [Formula: see text]. Here we provide an algorithm showing that [Formula: see text] for every collection [Formula: see text]. Prior to this work, the best known function [Formula: see text] was double-exponential in [Formula: see text]. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [ Proc. of the 25 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802–1811] for the particular case [Formula: see text] and of Kociumaka and Pilipczuk [ Algorithmica, 81 (2019), pp. 3655–3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [ Inform. Comput., 256 (2017), pp. 62–82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections [Formula: see text] [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135–152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56–77], our algorithm yields the following complexity dichotomy when [Formula: see text] contains a single connected graph [Formula: see text] assuming the Exponential Time Hypothesis: [Formula: see text] if [Formula: see text] is a contraction of the chair or the banner , and [Formula: see text] otherwise.

International audience

We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance $(G,k)$ of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a predetermined complexity parameter of $G$. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce $G$ to a member of a simple graph class $\mathcal{F}$, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes $\mathcal{F}$ for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to $\mathcal{F}$ admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families $\mathcal{F}$ for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if $\mathcal{F}$ has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.

The grid theorem of Robertson and Seymour [ J. Combin. Theory Ser. B, 41 (1986), pp. 92--114] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the grid theorem in digraphs was conjectured by Johnson et al. [ J. Combin. Theory Ser. B, 82 (2001), pp. 138--154] and proved by Kawarabayashi and Kreutzer [ Proceedings of STOC, 2015, pp. 655--664]. Namely, they showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor, and stated that their proof can be turned into an \sf XP algorithm, with parameter $k$, that either constructs a decomposition of the appropriate width or finds the claimed large cylindrical grid as a butterfly minor. In this paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this \sf XP algorithm into a fixed-parameter tractable (\sf FPT) algorithm. Toward this, our main technical contributions are two \sf FPT algorithms with parameter $k$. The first one either produces an arboreal decomposition of width $3k-2$ or finds a haven of order $k$ in a digraph $D$, improving on the original result for arboreal decompositions by Johnson et al. [ J. Combin. Theory Ser. B, 82 (2001), pp. 138--154]. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices $T$ in \sf FPT time with parameter $|T|$, a result that we consider to be of its own interest.

Let 𝒢 be a minor-closed graph class. We say that a graph G is a k -apex of 𝒢 if G contains a set S of at most k vertices such that G\S belongs to 𝒢 . We denote by 𝒜 k ( 𝒢 ) the set of all graphs that are k -apices of 𝒢 . In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of 𝒜 k ( 𝒢 ), i.e., the minor-minimal set of graphs not belonging to 𝒜 k ( 𝒢 ). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2 poly (k) ⋅ n 3 and either returns a set S certifying that G ∈ 𝒜 k ( 𝒢 ), or reports that G ∉ 𝒜 k ( 𝒢 ). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of 𝒢 . In the special case where 𝒢 excludes some apex graph as a minor, we give an alternative algorithm running in 2 poly (k) ⋅ n 2 -time.

In the Directed Disjoint Paths problem, we are given a digraph $D$ and a set of requests $\{(s_1, t_1), \ldots, (s_k, t_k)\}$, and the task is to find a collection of pairwise vertex-disjoint paths $\{P_1, \ldots, P_k\}$ such that each $P_i$ is a path from $s_i$ to $t_i$ in $D$. This problem is NP-complete for fixed $k=2$ and W[1]-hard with parameter $k$ in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Positive results are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified part of size prescribed by a parameter. Namely, in the Disjoint Enough Directed Paths problem, given an $n$-vertex digraph $D$, a set of $k$ requests, and non-negative integers $d$ and $s$, the task is to find a collection of paths connecting the requests such that at least $d$ vertices of $D$ occur in at most $s$ paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of $D$. Among other results, we show that the problem is W[1]-hard in DAGs with parameter $d$ and, on the positive side, we give an algorithm in time $\mathcal{O}(n^{d+2} \cdot k^{d\cdot s})$ and a kernel of size $d \cdot 2^{k-s}\cdot \binom{k}{s} + 2k$ in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number $k$ of terminals and $p$, where $p = n - q$ and $q$ is the size of the solution.

In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call {lop-kernels}. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP / poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.

A target set selection model is a graph G with a threshold function τ : V(G) → N upper-bounded by the vertex degree. For a given model, a set S0 ⊆ V(G) is a target set if V(G) can be partitioned into non-empty subsets S0, S1,....,St such that, for all i∈{1,....,t}, Si contains exactly every vertex v having at least τ(v) neighbors in S0∪⋯∪Si−1. We say that t is the activation time tτ(S0) of the target set S0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set S0 that maximizes tτ(S0). That is, given a graph G, a threshold function τ in G, and an integer k, the objective of the TSS-time problem is to decide whether G contains a target set S0 such that tτ(S0)≥k. Let τ*=maxV∈V(G)τ(v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C: if C has bounded local treewidth, the problem is FPT parameterized by k and τ*; otherwise, it is NP-complete even for fixed k = 4 and τ* = 2. We also prove that, with τ = 2, the problem is NP-hard in bipartite graphs for fixed k = 5, and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S0 in a given tree maximizing tτ(S0).

For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S⊆V(G) such that G∖S excludes H as an induced subgraph. We are interested in determining, for a fixed H, the smallest function fH(t) such that H-IS-Deletion can be solved in time fH(t)⋅nO(1) assuming the Exponential Time Hypothesis, where t and n denote the treewidth and the number of vertices of G, respectively. We show that fH(t)=2O(th−2) for every H on h≥3 vertices, and that fH(t)=2O(t) if H is a clique or an independent set. When H deviates slightly from a clique, the function fH(t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then fH(t)=2Θ(th−2). Moreover, fH(t)=2Ω(th) when H=Kh,h, answering a question of Pilipczuk [MFCS 2011].

We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance $(G,k)$ of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a pre-determined complexity parameter of $G$. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce $G$ to a member of a simple graph class $\mathcal{F}$, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes $\mathcal{F}$ for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to $\mathcal{F}$, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families $\mathcal{F}$ for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if $\mathcal{F}$ has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.

Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2^{poly(k)}n³ time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2^{poly(k)}n² time.

For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.

For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f (tw) · n(1), where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f (tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw)·n(1) for the more general problem where all minor models of connected graphs in a finite family need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case = {K5, K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

Given a graph G, a properk-coloring of G is a partition $$c = (S_i)_{i\in [1,k]}$$ of V(G) into k stable sets $$S_1,\ldots , S_{k}$$ . Given a weight function $$w: V(G) \rightarrow {\mathbb {R}}^+$$ , the weight of a color $$S_i$$ is defined as $$w(i) = \max _{v \in S_i} w(v)$$ and the weight of a coloringc as $$w(c) = \sum _{i=1}^{k}w(i)$$ . Guan and Zhu (Inf Process Lett 61(2):77–81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by $$\sigma (G,w)$$ , as the minimum weight of a proper coloring of G. The problem of determining $$\sigma (G,w)$$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time $$n^{o(\log n)}$$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is $$\sigma (G,w) \le \sum _{v \in V(G)} w(v) - k$$ ? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 2016), who provided an FPT algorithm running in time $$2^{{\mathcal {O}}(k \log k)} \cdot n^{{\mathcal {O}}(1)}$$ , and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time $$9^k \cdot n^{{\mathcal {O}}(1)}$$ , and prove that no algorithm in time $$2^{o(k)} \cdot n^{{\mathcal {O}}(1)}$$ exists under the ETH. On the other hand, we present a kernel with at most $$(2^{k-1}+1) (k-1)$$ vertices, and rule out the existence of polynomial kernels unless $$\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$$ , even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

For two positive integers k and $$\ell $$ ℓ , a $$(k \times \ell )$$ ( k × ℓ ) -spindle is the union of k pairwise internally vertex-disjoint directed paths with $$\ell $$ ℓ arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $$\ell \ge 1$$ ℓ ≥ 1 , finding the largest k such that an input digraph G contains a subdivision of a $$(k \times \ell )$$ ( k × ℓ ) -spindle is polynomial-time solvable if $$\ell \le 3$$ ℓ ≤ 3 , and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.

Abstract We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Treefor short) introduced by Wirth and Steffan. In this problem, given an undirected edge‐colored graphG, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree ofGof minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of theDiameter‐Treeproblem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Δ of the input graph. We prove thatDiameter‐Treeispara‐NP‐hard for any combination of two of these three parameters, and that it isFPTparameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we proveDiameter‐Treeto beNP‐hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it isNP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem isNP‐hard if Δ = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove thatDiameter‐Treeis inXPandW[1]‐hard parameterized by the treewidth plus Δ.

For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph $G$ and an integer $k$, deciding whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of $\mathcal{F}$-M-Deletion when the parameter is the treewidth of $G$, denoted by ${tw}$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that $\mathcal{F}$-M-Deletion can be solved in time $f_{{\cal F}}({tw}) \cdot n^{\mathcal{O}(1)}$ on $n$-vertex graphs. We prove that $f_{{\cal F}}({tw}) = 2^{2^{\mathcal{O} ({tw} \cdot\log {tw})}}$ for every collection ${\cal F}$, that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw} \cdot\log {tw})}$ if ${\cal F}$ contains a planar graph, and that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw})}$ if in addition the input graph $G$ is planar or embedded in a surface. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, called $\mathcal{F}$-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring $\mathcal{F}$ to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic.

A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [IPEC 2018], we introduce a natural generalization of this problem, which we call d-Cut: for a positive integer d, a d-cut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d-Cut on (2d+2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d+2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [IPEC 2018], is a polynomial kernel for d-Cut for every positive integer d, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O^*(2^n).

In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarský et al. (J Comput Syst Sci 84:219–242, 2017) proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c, where $$c \ge 1$$ is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that Vertex Cover admits a polynomial kernel on general graphs for any integer $$c \ge 1$$ , and that Dominating Set does not for any integer $$c \ge 2$$ even on degenerate graphs, unless $$\text {NP} \subseteq \text {coNP}/\text {poly}$$ . For the positive result, we build on the techniques of Jansen and Bodlaender (Proceedings of the 28th symposium on theoretical aspects of computer science (STACS), volume 9 of LIPIcs, pp 177–188, 2011), and for the negative result we use a polynomial parameter transformation for $$c\ge 3$$ and an or-cross-composition for $$c = 2$$ . As existing results imply that Dominating Set admits a polynomial kernel on degenerate graphs for $$c = 1$$ , our result provides a dichotomy about the existence of polynomial kernels for Dominating Set on degenerate graphs with this parameter.

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G,w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph $(G,w)$ and an integer $k$, the question is whether $\sigma(G,w) \leq \sum_{v \in V(G)} w(v) - k$. We prove that this problem is FPT by providing an algorithm running in time $9^k \cdot n^{O(1)}$, and it is easy to see that no algorithm in time $2^{o(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1) (k-1)$ vertices, and we rule out the existence of polynomial kernels unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

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$.

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.

For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: - f_{K_4}(w) = 2^{Theta(wlog w)}. - f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4. - f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X ⊆ V ( G ), called a treewidth-modulator , such that the treewidth of G − X is bounded by a constant. Our decomposition, called a protrusion decomposition , is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter k ) that has a finite integer index and such that Y es -instances have a treewidth-modulator of size O ( k ) admits a linear kernel on the class of H -topological-minor-free graphs, for any fixed graph H . This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and H -minor-free graphs. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n -vertex graph G and a non-negative integer k , P lanar - F -D eletion asks whether G has a set X ⊆ V ( G ) such that | X | ⩽ k and G − X is H -minor-free for every H ϵ F . As our second application, we present the first single-exponential algorithm to solve P lanar - F -D eletion . Namely, our algorithm runs in time 2 O ( k ) · n 2 , which is asymptotically optimal with respect to k . So far, single-exponential algorithms were only known for special cases of the family F .

In this paper we design FPT-algorithms for two parameterized problems. The first is List Digraph Homomorphism: given two digraphs G and H and a list of allowed vertices of H for every vertex of G, the question is whether there exists a homomorphism from G to H respecting the list constraints. The second problem is a variant of Multiway Cut, namely Min-Max Multiway Cut: given a graph G, a non-negative integer l, and a set T of r terminals, the question is whether we can partition the vertices of G into r parts such that (a) each part contains one terminal and (b) there are at most l edges with only one endpoint in this part. We parameterize List Digraph Homomorphism by the number w of edges of G that are mapped to non-loop edges of H and we give a time 2^{O(l * log(h) + l^{2 * log(l)}} * n^{4} * log(n) algorithm, where h is the order of the host graph H.We also prove that Min-Max Multiway Cut can be solved in time 2^{O((l * r)^2 * log(l *r))} * n^{4} * log(n). Our approach introduces a general problem, called List Allocation, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an FPT-algorithm for the List Allocation problem that is designed using a suitable adaptation of the randomized contractions technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629--638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503--510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613--624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for $r$-Dominating Set and $r$-Scattered Set on apex-minor-free graphs, and for Planar-$\mathcal{F}$-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in $\mathcal{F}$ are connected.

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result [Bodlaender et al., FOCS 2009] on graphs of bounded genus, then generalized by [Fomin et al., SODA 2010] to graphs excluding a fixed minor, and by [Kim et al., ICALP 2013] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for Planar-F-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

The $c$-pumpkin is the graph with two vertices linked by $c \geq 1$ parallel edges. A $c$-pumpkin-model in a graph $G$ is a pair $\{A, B\}$ of disjoint subsets of vertices of $G$, each inducing a connected subgraph of $G$, such that there are at least $c$ edges in $G$ between $A$ and $B$. We focus on hitting and packing $c$-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time $2^{\mathcal{O}(k)} n^{\mathcal{O}(1)}$ deciding, for any fixed $c \geq 1$, whether all $c$-pumpkin-models can be hit by at most $k$ vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases $c=1,2$ respectively. Finally, we present an $\mathcal{O}(\log n)$-approximation algorithm for both the problems of hitting all $c$-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint $c$-pumpkin-models.

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k . Our technique applies to general families of problems where standard dynamic programming runs in 2 O ( k ⋅log k ) ⋅ n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition , generalizing sphere cut decompositions of planar graphs, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of noncrossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k ) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2 O ( k ) ⋅ n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network$G$and a positive integer$d$, regenerators must be placed in such a way that in any lightpath there are no more than$d$hops without meeting a regenerator. The cost function we consider is given by the total number of regenerators placed at the nodes, which we believe to be a more accurate estimation of the real cost of the network than the number of locations considered in the work of Flammini(IEEE/ACM Trans. Netw., vol. 19, no. 2, pp. 498–511, Apr. 2011). Furthermore, in our model we assume that we are given a finite set of$p$possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied. While this problem can be easily solved when$d=1$or$p=1$, we prove that for any fixed$d,p \geq 2$, it does not admit a PTAS, even if$G$has maximum degree at most 3 and the lightpaths have length$ {\cal O}(d)$. We complement this hardness result with a constant-factor approximation algorithm with ratio$\ln (d \cdot p)$. We then study the case where$G$is a path, proving that the problem is polynomial-time solvable for two particular families of instances. Finally, we generalize our model in two natural directions, which allows us to capture the model of Flamminias a particular case, and we settle some questions that were left open therein.

Abstract We study the minimization of ADMs (Add‐Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all‐to‐all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factorCandN, the size of the ring. We first study exhaustively the casesC= 1,C= 2, andC= 3, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the caseC> 3, focusing specifically on the caseC=k(k+ 1)/2 for somek≥ 1. We give optimal decompositions for several congruence classes ofNusing the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 20–35 2011

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications (in bioinformatics, constraint-based temporal reasoning, resource allocation, and scheduling problems, among others). Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs—namely, the problem of deciding whether a given graph is a tolerance graph—as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs [M. C. Golumbic and A. N. Trenk, Tolerance Graphs, Cambridge Stud. Adv. Math. 89, Cambridge University Press, Cambridge, UK, 2004]) since their introduction in 1982 [M. C. Golumbic and C. L. Monma, Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 35 (1982), pp. 321–331]. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an acyclic orientation of permutation and trapezoid graphs. Our main tool is a new algorithm that uses vertex splitting to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it was also proved a powerful tool in the design of efficient recognition algorithms for other classes of graphs [G. B. Mertzios and D. G. Corneil, Discrete Appl. Math., 159 (2011), pp. 1131–1147].

We study the following graph partitioning problem: Given two positive integers C and $\Delta$, find the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most C edges and each vertex appears in at most $M(C,\Delta)$ subgraphs. This problem is naturally motivated by traffic grooming, which is a major issue in optical networks. Namely, we introduce a new pseudodynamic model of traffic grooming in unidirectional rings, in which the aim is to design a network able to support any request graph with a given bounded degree. We show that optimizing the equipment cost under this model is essentially equivalent to determining the parameter $M(C,\Delta)$. We establish the value of $M(C,\Delta)$ for almost all values of C and $\Delta$, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between 3 and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. For these open cases, we provide upper bounds that differ from the optimal value by at most one.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs --~namely, the problem of deciding whether a given graph is a tolerance graph~-- as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction in 1982~\cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}.

We study grooming for two-period optical networks, a variation of the traffic grooming problem for wavelength division multiplexed (WDM) ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among n nodes, each request using $1/C$ of the bandwidth; and during the second period there is all-to-all uniform traffic only among a subset V of v nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of add-drop multiplexers (ADMs)) for any $n,v$ and $C=4$ and $C'\in\{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most C edges and where furthermore it contains at most $C'$ edges of the complete graph on v specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [M. C. Golumbic and C. L. Monma, Congr. Numer., 35 (1982), pp. 321–331], as it finds many important applications in constraint-based temporal reasoning, resource allocation, and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal $\mathcal{O}(n\log n)$ algorithms for computing a minimum coloring and a maximum clique and an $\mathcal{O}(n^{2})$ algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times $\mathcal{O}(n^{2})$ and $\mathcal{O}(n^{3})$ for these problems, respectively.