Júlio Araújo

Marin Bougeret
email: marin.bougeret@lirmm.fr

Victor Campos

Ignasi Sau
email: ignasi.sau@lirmm.fr

Introducing lop-kernels: a framework for kernelization lower bounds

Keywords: 2012 ACM Subject Classification Design Parameterized complexity, polynomial kernel, kernelization lower bound, maximum minimal vertex cover, Erdős-Hajnal property, induced subgraphs

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 kernelization lower bounds for a certain type of kernels for 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. We present further applications for Tree Deletion Set and for Maximum Independent Set on Kt-free graphs.

Back to the MMVC problem, 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. 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.

Introduction

A vertex cover in a graph G is a subset of vertices containing at least one endpoint of every edge. In the associated optimization problem, called Minimum Vertex Cover, the objective is to find, given an input graph G, a vertex cover in G of minimum size. This problem has been one of the leitmotifs of the area of parameterized complexity [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], serving as a test bed for many of the most fundamental techniques. An instance of a parameterized problem is of the form (x, k), where x is the total input (typically, a graph) and k is a positive integer called the parameter. The crucial notion is that of fixed-parameter tractable algorithm, FPT for short, which is an algorithm deciding whether (x, k) is a positive instance in time f (k) • |x| O (1) , where f is a computable function depending only on k. In the parameterized Vertex Cover problem, we are given a graph G and an integer parameter k, and the objective is to decide whether G contains a vertex cover of size at most k. One of the main fields within parameterized complexity is kernelization [START_REF] Fedor | Theory of Parameterized Preprocessing[END_REF], where the objective is to decide whether an instance (x, k) of a parameterized problem can be transformed in polynomial time into an equivalent instance (x , k ) whose total size is bounded by a function of k; the reduced instance is called a kernel, and finding kernels of small size, typically polynomial or even linear in k in the best case, is one of the most active areas of parameterized complexity.

Considering the "max-min" version of minimization problems, that is, maximizing the size of a minimal solution of the corresponding problem, is a natural approach that has been applied to several problems such as Dominating Set [START_REF] Bazgan | The many facets of upper domination[END_REF][START_REF] Dublois | Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation[END_REF] (whose "max-min" version is called Upper Domination), Feedback Vertex Set [START_REF] Dublois | In)approximability of Maximum Minimal FVS[END_REF], or Hitting Set [START_REF] Araújo | Parameterized complexity of computing maximum minimal blocking and hitting sets[END_REF][START_REF] Damaschke | Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover[END_REF]. The initial motivation of this article is the "max-min" version of Minimum Vertex Cover, called Maximum Minimal Vertex Cover, or just MMVC for short.

Previous work.

In his habilitation, Fernau [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF] presented FPT algorithms for MMVC as well as some results about its kernelization parameterized by the solution size k. It is easy to note, as observed in [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF], that the problem admits a kernel with at most k 2 vertices: if some vertex has degree at least k, we can safely answer "yes" (cf. Lemma 2 for a proof); otherwise, the maximum degree is at most k -1, and it follows that every instance without isolated vertices (which may be safely removed) that has at least k 2 vertices is a yes-instance, hence we have a trivial kernel with at most k 2 vertices. Fernau [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF] presented a kernel with at most 4k vertices for MMVC restricted to planar instances using the algorithmic version of the Four Color Theorem [START_REF] Robertson | The four-colour theorem[END_REF], and claimed in [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF]Corollary 4.25] a kernel with at most 2k vertices on general graphs using spanning trees. Unfortunately, this latter kernelization algorithm is incorrect, as we discuss in Section 6.

Boria et al. [START_REF] Boria | On the max min vertex cover problem[END_REF] initiated a study of the complexity of MMVC and presented a number of results, in particular a polynomial-time approximation algorithm with ratio n 1/2 on n-vertex graphs, and showed that, unless P = NP, no polynomial-time approximation algorithm with ratio n 1/2-ε exists for any ε > 0. They also presented FPT algorithms for MMVC for several choices of the parameters such as the treewidth, the size of a maximum matching, or the size of a minimum vertex cover of the input graph. The authors asked explicitly whether kernels of size o(k 2 ) exist for MMVC parameterized by k.

Zehavi [START_REF] Zehavi | Maximum Minimal Vertex Cover Parameterized by Vertex Cover[END_REF] presented tight FPT algorithms, under the Strong Exponential Time Hypothesis, for MMVC and its weighted version parameterized by the size of a minimum vertex cover. Recently, Bonnet and Paschos [START_REF] Bonnet | Sparsification and subexponential approximation[END_REF] and Bonnet et al. [START_REF] Bonnet | Time-approximation trade-offs for inapproximable problems[END_REF] considered the inapproximability of MMVC in subexponential time.

Note that the MMVC problem is the dual of the well-studied Minimum Independent Dominating Set problem (to see this, note that the complement of any minimal vertex Another application of our results deals with the Tree Deletion Set problem. In this case, the fact that this problem does not admit a polynomial-time O(n 1-ε )-approximation for any ε > 0 unless P = NP [START_REF] Yannakakis | The effect of a connectivity requirement on the complexity of maximum subgraph problems[END_REF] implies, together with Corollary 22, that Tree Deletion Set parameterized by the solution size does not admit a polynomial lop-kernel, unless P = NP (Corollary 28). However, Tree Deletion Set does admit a polynomial kernel with O(k 4 ) vertices [START_REF] Archontia | Tree Deletion Set has a polynomial kernel but no OPT O(1) approximation[END_REF]. Therefore, this polynomial kernel cannot be a lop-kernel, and so far it constitutes the only non-artificial example of non-lop-kernel that we are aware of.

Our last application concerns the Maximum Independent Set problem restricted to K t -free graphs. In particular, we show (Corollary 30) that a lop-kernel with O(k t-1-ε ) vertices for Maximum Independent Set on K t -free graphs would improve the best known approximation ratio n t-2 t-1 that follows from Ramsey's theorem [START_REF] Frank | On a problem of formal logic[END_REF]. Finally, generalizing a conjecture of Bonnet et al. [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF], we conjecture that for every fixed graph H, the Maximum Independent Set problem restricted to H-free graphs admits a polynomial lop-kernel.

Comparison with other frameworks. Compared to existing frameworks to obtain lower bounds on kernelization, such as cross-compositions [START_REF] Hans | On problems without polynomial kernels[END_REF][START_REF] Hans | Kernelization lower bounds by cross-composition[END_REF], weak compositions [START_REF] Dell | Kernelization of packing problems[END_REF][START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF][START_REF] Hermelin | Weak compositions and their applications to polynomial lower bounds for kernelization[END_REF], polynomial parameter transformations [START_REF] Binkele-Raible | Kernel(s) for problems with no kernel: On out-trees with many leaves[END_REF][START_REF] Hans | Kernel bounds for disjoint cycles and disjoint paths[END_REF], or techniques to obtain lower bounds on the coefficients of linear kernels [START_REF] Chen | Parametric duality and kernelization: Lower bounds and upper bounds on kernel size[END_REF], or that relate approximation and kernelization [START_REF] Faisal | Approximation algorithms inspired by kernelization methods[END_REF][START_REF] Biswas | Approximation in (poly-) logarithmic space[END_REF][START_REF] Guo | Safe approximation and its relation to kernelization[END_REF][START_REF] Kratsch | Polynomial kernelizations for MIN F + Π1 and MAX NP[END_REF][START_REF] Lokshtanov | Lossy kernelization[END_REF], our approach has the advantages that it is quite simple, straightforward to apply, and relies on the same hypothesis on which the corresponding inapproximability result is based, typically the standard hypothesis that P = NP. On the negative side, it has the following two drawbacks. The first one is that, in order to obtain a non-trivial lower bound on the kernel size, it can only be applied to problems which are quite hard to approximate, for example within a factor O(n r-ε ) for some constant r > 0, as it is the case of MMVC and MMFVS. The second, and probably most important, drawback of our techniques is that they are able to rule out the existence of what we call lop-kernels of certain sizes, but smaller non-standard kernels that do not preserve the value of large optimal solutions might, a priori, still exist (as it is the case for Tree Deletion Set, as discussed above). Hence, since our framework seems to be orthogonal to existing ones, we think that it adds to the above list of techniques to obtain kernelization lower bounds.

Other results on the kernelization of MMVC. Coming back to the MMVC problem parameterized by the solution size, given the above negative result on general graphs, we identify graph classes where MMVC is still NP-hard and admits a subquadratic kernel. In particular, we deal with graph classes defined by excluding an induced subgraph H that satisfies the Erdős-Hajnal property [START_REF] Erdős | Ramsey-type theorems[END_REF], that is, for which there exists a constant δ > 0 such that every H-free graph on n vertices contains either a clique or an independent set of size n δ . In particular, we present a kernel for MMVC with O(k 7/4 ) vertices on the well-studied class of bull-free graphs (Theorem 32), with O(k 2t-3 t-1 ) vertices on K t -free graphs graphs for every t ≥ 3 (Theorem 34), and with O(k 5/3 ) vertices on paw-free graphs (Theorem 37). To the best of our knowledge, this is the first time that the Erdős-Hajnal property is used to obtain polynomial kernels (we would like to note that it was used by Kratsch et al. [START_REF] Kratsch | Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs[END_REF] to obtain kernelization lower bounds).

Our strategy to obtain these subquadratic kernels on H-free graphs is as follows. By the high-degree rule mentioned above, given an instance (G, k), we may assume that the maximum degree of G is at most k -1. We find greedily a minimal vertex cover X of G. If |X| ≥ k we are done, so we may assume that |X| ≤ k -1, hence the goal is to bound the size of S := V (G) \ X. Using that G[X] is also H-free, the Erdős-Hajnal property implies (Lemma 31) that X can be partitioned in polynomial time into a sublinear (in k) number of independent sets and cliques. Since S is an independent set and we may assume that G has no isolated vertices, in order to bound |S| by a subquadratic function of k, it is enough to show that, for each of the sublinearly many cliques or independent sets Y that partition X, its neighborhood in S has size O(k). This is easy if Y is an independent set: if |N S (Y )| ≥ k we can conclude that (G, k) is a yes-instance (Lemma 2), so we may assume that |N S (Y )| ≤ k -1. The case where Y is a clique is more interesting, and we need ad-hoc arguments depending on each particular excluded induced subgraph H.

We also present several positive results for MMVC restricted to other particular graph classes, such as K 1,t -free graphs (Lemma 38), graph classes with bounded chromatic number (Lemma 39), or graph classes with bounded cliquewidth (Observation 40).

Finally, we show (Theorem 42) that MMVC, parameterized by the size of a minimum vertex cover (or of a maximum matching) of the input graph, does not admit a polynomial kernel unless NP ⊆ coNP/poly, even restricted to bipartite graphs. This result complements the FPT algorithms for MMVC under these parameterizations given by Boria et al. [START_REF] Boria | On the max min vertex cover problem[END_REF] and Zehavi [START_REF] Zehavi | Maximum Minimal Vertex Cover Parameterized by Vertex Cover[END_REF], and shows that, in what concerns the existence of polynomial kernels for MMVC, the most natural structural parameters smaller than the solution size are not large enough to yield polynomial kernels (note that the treewidth of any graph is at most one more than its vertex cover number, hence our result rules out the existence of polynomial kernels for MMVC parameterized by treewidth as well). The proof consists of a polynomial parameter transformation from Monotone Sat parameterized by the number of variables. In particular, our reduction yields also the NP-hardness of MMVC on bipartite graphs, which provides an alternative proof to the one of Boliac and Lozin [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF] via the NP-hardness of Minimum Independent Dominating Set on bipartite graphs.

Organization.

In Section 2 we provide some basic preliminaries about graphs, the MMVC problem, parameterized complexity, and approximation algorithms. In Section 3 (resp. Section 4) we present our framework to obtain kernelization lower bounds for maximization (minimization) problems. In both sections, the contents are split into three subsections: we start with the general definitions, then we focus on the particular and relevant case of vertex-optimization problems, and then we present the general results for what we call "well-behaved" optimization problems. In Section 5 we present several applications of the framework of lop-kernels for concrete problems, and in Section 6 we discuss the flaw in the linear kernel for MMVC claimed by Fernau [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF]. Section 7 is devoted to the subquadratic kernels for MMVC on particular graph classes, as well as to other positive results for MMVC. Our reduction to rule out the existence of polynomial kernels for MMVC parameterized by the size of a minimum vertex cover (or a maximum matching) is presented in Section 8. We conclude the article in Section 9 with a discussion and some directions for further research.

Preliminaries

Graphs and functions. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined notation. For an integer p ≥ 1, we let [p] be the set containing all integers i with 1 ≤ i ≤ p. We use to denote the disjoint union.

G \ S = G[V (G) \ S], and for a vertex v ∈ V (G), we abbreviate G \ {v} as G \ v. A vertex v is complete to a set S ⊆ V (G) if v is adjacent to every vertex in S. The open (resp. closed) neighborhood of a vertex v in a graph G is denoted by N (v) (resp. N [v]), whenever the graph G is clear from the context. For vertex sets X, Y ⊆ V (G), we define N [X] = v∈X N [v], N (X) = N [X]\X, N Y [X] = N [X]∩Y , and N Y (X) = N Y [X]\X.
The degree of a vertex v in a graph G is defined as |N (v)|, and we denote it by deg G (v), or just deg(v) of the graph is clear from the context. For an integer t ≥ 1, we denote by P t (resp. I t , K t ) the path (resp. edgeless graph, complete graph) on t vertices. For two integers a, b ≥ 1, we denote by K a,b the bipartite graph with parts of sizes a and b.

A clique (resp. independent set) in a graph G is a set of vertices that are pairwise adjacent (resp. not adjacent). A graph property is hereditary if whenever it holds for a graph G, it holds for all its induced subgraphs as well. Note that the properties of being an edgeless graph, a complete graph, or an independent set are hereditary. We denote by ∆(G) (resp. ω(G) the maximum vertex degree (resp. clique size) of a graph G.

A vertex cover of a graph G is a set of vertices containing at least one endpoint of every edge, and it is minimal if no proper subset of it is a vertex cover. One of the concrete problems that we study in this paper is formally stated as follows. We state it as a decision problem, since most of our results consider its parameterization by the solution size k.

Maximum Minimal Vertex Cover (MMVC)

Input: A graph G and a positive integer k. Question: Does G contain a minimal vertex cover of size at least k?

For a graph G, we denote by mmvc(G) the maximum size of a minimal vertex cover of G.

The following observation has been already used in previous work [START_REF] Boria | On the max min vertex cover problem[END_REF][START_REF] Zehavi | Maximum Minimal Vertex Cover Parameterized by Vertex Cover[END_REF].

Observation 1. Let G be a graph. A set X ⊆ V (G) is a minimal vertex cover of G if and only if X is a vertex cover of G and, for every vertex v ∈ X, N (v) X.
The next lemma provides a useful way to conclude that we are dealing with a yes-instance in the kernelization algorithms presented in Section 7.

Lemma 2.

Let G be a graph and let S ⊆ V (G) be an independent set. There exists a minimal vertex cover of G containing N (S).

Proof. Note that, since S is an independent set, V (G) \ S is a vertex cover of G. Hence, there exists a minimal vertex cover X of G such that X ⊆ V (G) \ S. We claim that N (S) ⊆ X. Suppose for the sake of contradiction that there exists a vertex v ∈ N (S) such that v / ∈ X. Since v has a neighbor u in S and S ∩ X = ∅, the edge {u, v} would not be covered by X.

Note that, in particular, Lemma 2 implies that if (G, k) is an instance of the Maximum Minimal Vertex Cover problem and v ∈ V (G) is a vertex of degree at least k, then we can conclude that (G, k) is a yes-instance. This will allow us to assume, in our kernelization algorithms, that ∆(G) ≤ k -1.

Parameterized complexity.

We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions used in this article. A parameterized problem is a language L ⊆ Σ * × N. For an instance

I = (x, k) ∈ Σ * × N, k is called the parameter.
A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| c . For instance, the Vertex Cover problem parameterized by the size of the solution is FPT.

For an instance (x, k) of a parameterized problem Q, a kernelization algorithm is an algorithm A that, in polynomial time, generates from (x, k) an equivalent instance (x , k ) of Q such that |x | + k ≤ f (k), for some computable function f : N → N, where |x | denotes the size of x . If f (k) is bounded from above by a polynomial of the parameter, we say that Q admits a polynomial kernel. In particular, if f (k) is bounded by a linear (resp. quadratic) function, then we say that Q admits a linear (resp. quadratic) kernel.

A polynomial parameter transformation, abbreviated as PPT, is an algorithm that, given an instance (x, k) of a parameterized problem A, runs in time polynomial in |x| and outputs an instance (x , k ) of a parameterized problem B such that k is bounded from above by a polynomial on k and (x, k) is positive if and only if (x , k ) is positive. If a parameterized problem A does not admit a polynomial kernel unless NP ⊆ coNP/poly and there exists a PPT from A to a parameterized problem B, then B does not admit a polynomial kernel unless NP ⊆ coNP/poly either [START_REF] Cygan | Parameterized Algorithms[END_REF].

Approximation algorithms. We refer the reader to [START_REF] Williamson | The Design of Approximation Algorithms[END_REF] for background on approximation algorithms, and we define here only some non-standard notions used in this article.

As, when dealing with graph problems, one typically measures the size of kernels in terms of the number of vertices or edges (and not in the classical bit-size of the instance), we introduce an arbitrary notion of size as follows. Given a optimization problem Π, we say that a non-negative integer-valued function | • | is a size function if, given an instance I of Π, |I| can be computed in polynomial time in the classical bit-size, and |I| is upper-bounded by a polynomial in the classical bit-size.

For an optimization problem Π, an instance I of Π, and a feasible solution s of Π in I, we denote by val Π (I, s) the value of the objective function of Π for s. We restrict ourselves to optimization problems Π whose objective functions for feasible solutions take non-negative integer values. For a maximization (resp. minimization) problem Π and an instance I of Π, we denote by opt Π (I) the maximum (resp. minimum) of val Π (I, s) over all feasible solutions s of Π in I.

A maximization (resp. minimization) problem Π is a vertex-maximization (resp. vertexminimization) problem if their instances consist of a graph G, and the objective is to find a vertex set S ⊆ V (G) of maximum (resp. minimum) size satisfying some conditions. For instance, Maximum Independent Set and Minimum Vertex Cover are typical examples of vertex-maximization and vertex-minimization problems, respectively.

For kernelization purposes, we need to consider the decision version of optimization problems. For a maximization (resp. minimization) problem Π whose instances are of the form I, we denote by Π dec the decision problem whose instances are of the form (I, k), where k is a non-negative integer, and where (I, k) is a yes-instance of Π dec if opt Π (I) ≥ k (resp. opt Π (I) ≤ k), and a no-instance otherwise.

Since we aim at establishing a link between the existence of certain kernels and approximation algorithms, we need to take care of constructibility issues. The standard definition of a kernelization algorithm [START_REF] Fedor | Theory of Parameterized Preprocessing[END_REF] does not involve constructing a solution of the considered problem. On the other hand, the standard definition of an approximation algorithm [START_REF] Williamson | The Design of Approximation Algorithms[END_REF] does take into account the construction of the corresponding solution. Hence, in order to establish such a connection, we need to consider slightly "non-standard" definitions of these objects.

Namely, we distinguish between constructive and non-constructive approximation algorithms, so that the kernelization lower bounds that we present are able to rule out constructive or non-constructive kernels (cf. the second paragraph of Section 3). To this end, we say that an algorithm for a maximization (resp. minimization) decision problem Π dec constructively decides an instance (I, k) if, whenever it holds that opt Π (I) ≥ k (resp. opt Π (I) ≤ k), the algorithm outputs a feasible solution s such that val Π (I, s) ≥ k (resp. val Π (I, s) ≤ k).

When using the term "approximation algorithm" with ratio ρ ≥ 1 for a maximization (resp. minimization) problem Π, we assume, unless stated otherwise, that it is constructive, that is, that the algorithm, given an instance I of Π, outputs a feasible solution s of Π in I such that opt Π (I)/val Π (I, s) ≤ ρ (resp. val Π (I, s)/opt Π (I) ≤ ρ). Note that the approximation ratio ρ is, in general, a non-negative integer-valued function that depends on I.

We define a value-approximation algorithm with ratio ρ ≥ 1 for a maximization (resp. minimization) problem Π as an algorithm that, given an instance I of Π, returns a nonnegative integer k such that 1 ≤ opt Π (I)/k ≤ ρ (resp. 1 ≤ k/opt Π (I) ≤ ρ). Again, here ρ is, in general, a non-negative integer-valued function that depends on I. Note that a value-approximation algorithm is not only not required to construct a feasible solution with value k, but also not required to guarantee that such a solution exists.

3

A framework for ruling out certain polynomial kernels: the case of maximization problems

In this section we introduce our generic framework to obtain lower bounds on the size of a certain type of polynomial kernels, which we call lop-kernels (see Definition 5), for a broad class of maximization problems that we proceed to introduce. Informally, the framework is based on simple and self-contained arguments proving that a "small" lop-kernel implies the existence of a "good" approximation algorithm. Then, the contrapositive of this statement implies that inapproximability results can be turned into lop-kernel lower bounds. It worth mentioning here that most of the inapproximability results in the literature hold for the value-approximation algorithms as defined at the end of Section 2, that is, for algorithms that are not required to construct in polynomial time an appropriate solution of the corresponding problem, but only to report a value within the appropriate range. In order to guarantee that it is also possible to use our framework when only the non-existence of constructive approximation algorithms is known, we introduce a variant of lop-kernels, called constructive lop-kernels, such that their existence implies the existence of a constructive approximation algorithm. However, in a first reading, we recommend to skip all technical details concerning constructibility.

We say that a maximization problem Π is well-behaved if it comes equipped with a size function (as defined in Section 2) and it satisfies the following condition, which we denote by C max :

There exists an algorithm that, given as input a real number c and an instance I of Π such that opt Π (I) ≤ c, runs in polynomial time for every fixed c and either decides that opt Π (I) = 0 and provides a feasible solution s with val Π (I, s) = 0, or provides a feasible solution s with val Π (I, s) > 0.

Observe that most of the classical maximization problems are well-behaved, and in particular any vertex-maximization problem whose decision version belongs to NP is wellbehaved, as we can enumerate all subsets of vertices of size at most c, and for each of them verify in polynomial time if it is a feasible solution. Given a well-behaved maximization problem Π, we say that a function u : N → N is an upper bound function for Π if for any instance I of Π, it holds that opt Π (I) ≤ u(|I|), where | • | is the size function of Π. Throughout the paper, we assume that the notions of size used in both the size of kernels and the upper bound function are the same. The reminder of this section is organized as follows. In Subsection 3.1 we present the definition of lop-rules and lop-kernels for well-behaved maximization problems, and we prove a general technical result, namely Lemma 8. In Subsection 3.2 we present the connection between lop-kernels and approximation algorithms for vertex-maximization problems, and in Subsection 3.3 we generalize it to arbitrary well-behaved maximization problems.

Definition of lop-rules and lop-kernels

Definition 3. A large optimal preserving reduction rule, or lop-rule for short, for a wellbehaved maximization problem Π, is a polynomial-time algorithm R that, given an instance

(I, k) of Π dec , computes another instance (I , k ) of Π dec with 0 ≤ k ≤ k and such that 1. if (I, k) is a no-instance of Π dec , then (I , k ) is a no-instance of Π dec , and 2. if (I, k) is a yes-instance of Π dec , then opt Π (G ) ≥ opt Π (G) -(k -k ), implying that (I , k ) is a yes-instance of Π dec . A lop-rule R is constructive if, given I and any solution s of I of such that val Π (I , s ) ≥ k , it constructs (in polynomial time) a solution s of I such that val Π (I, s) ≥ k.
Note that Property 2 in Definition 3 is stronger than the implication "if (I, k) is a yes-instance of Π dec , then (I , k ) is a yes-instance of Π dec ", which would yield the definition of a classical kernelization algorithm [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF]. Indeed, when we consider how this latter implication is generally proved in safeness proofs of classical kernels, one of the following scenarios often occurs: In Case (a), the rule preserves all optimal values, as it implies that opt Π (G ) ≥ opt Π (G) -(k -k ). In Case (b), the rule preserves only large optimal values, as it implies that if opt Π (G) ≥ k, then opt Π (G ) ≥ opt Π (G) -(k -k ), implying Property 2 above. Note that if opt Π (G) < k, then opt Π (G ) and opt Π (G) are not necessarily related. This justifies our choice for "large optimal preserving" rules. Case (c) corresponds to the weaker and classical implication "if (I, k) is a yes-instance of Π dec , then (I , k ) is a yes-instance of Π dec ".

The following observation is an immediate consequence of the definition of a lop-rule.

Observation 4. lop-rules can be composed. Formally, consider two lop-rules R 1 and R 2 . Then, the rule R that, given a instance

(I, k) of Π dec , returns R 2 (R 1 (I, k)), is also a lop-rule. Moreover, if R 2 and R 1 are constructive, then R is also constructive.
A typical example of a lop-rule for a vertex-maximization problem is when we can identify a "dominant" set of vertices that can be safely included into a solution. More precisely, consider a rule that, given a graph G, finds a subset T ⊆ V (G) and a graph G such that there exists an optimal solution S in G such that S = T ∪ S , where S is a solution in G , and for every solution S in G , S ∪ T is a solution in G. Such a rule is a (constructive) lop-rule, as we even fall into Case (a) described above.

Even if we are not aware of known reduction rules for vertex-maximization problems that are not lop-rules, we can artificially devise such an example. For instance, for the MMVC problem, given an instance (G, k), if there is a vertex that has more than k neighbors of degree one, we can safely delete all but any k of them to obtain a reduced graph G , and leave k unchanged. Note that this rule falls into Case (c) above, since by Lemma 2 both G and G are yes-instances of MMVC, but it does not satisfy Property 2 in Definition 3, since mmvc(G) may be arbitrarily larger than mmvc(G ).

If we defined a lop-kernel as an algorithm consisting only of lop-rules, we would exclude from being a lop-kernel, for instance, a rule that detects a yes-instance as in the above paragraph. This justifies the next definition, where we also allow lop-kernels to decide instances. Definition 5. Let Π be a well-behaved maximization problem and let s : N → N be a computable function. A lop-kernel of size s for Π parameterized by the solution size is a polynomial-time algorithm that takes as input an instance (I, k) of Π dec , and either decides that (I, k) is a yes-instance or a no-instance, or outputs a reduced instance (I , k ) by applying a sequence of lop-rules to (I, k), with

|I | ≤ s(k). A lop-kernel is constructive if,

in the first case, it constructively decides (I, k) (but in the second case it may not use constructive rules).

As it is common in kernels to exhaustively apply reduction rules, and then to either decide the reduced instance or to output it, let us introduce and discuss the following definition1 . Definition 6. Let Π be a well-behaved maximization problem and let s : N → N be a computable function. A lop-kernel of size s for Π parameterized by the solution size is a polynomial-time algorithm that takes as input an instance (I, k) of Π dec , computes an instance (I , k ) by applying a (possibly empty) sequence of lop-rules to (I, k), and either decides that (I , k ) is a yes-instance or a no-instance, or outputs (I , k ), with |I | ≤ s(k). A lop-kernel is constructive if, in the first case, it constructively decides (I , k ) and, in the second case, it only uses constructive lop-rules.

Firstly, observe that a lop-kernel (resp. constructive lop-kernel ) is a lop-kernel (resp. constructive lop-kernel). Indeed, if a lop-kernel decides (I , k ), then, as the definition of lop-rules implies that the reduced instance (I , k ) is equivalent to (I, k), it also decides (I, k). Moreover, if a lop-kernel is constructive and decides that (I , k ) is a yes-instance by providing a solution s with val Π (I , s ) ≥ k , then, as the rules are constructive, and according to Observation 4, we can build in polynomial time a solution s with val Π (I, s) ≥ k, and thus constructively decide (I, k). Secondly, observe that a lop-kernel is a lop-kernel , but that a constructive lop-kernel is not necessarily a constructive lop-kernel . The conclusion of this discussion is that for the non-constructive versions, both definitions are equivalent, and for the constructive versions, lop-kernels are slightly more general. As many inapproximability results even hold for the non-constructive version of approximation, we suggest the reader to stick to the non-constructive version, and thus to chose any of the two definitions. The only case where it could make a difference would be for a problem Π for which inapproximability results are only known for ruling out constructive approximation algorithms. Then, Corollary 11 will turn this inapproximability into a kernel lower bound even for constructive lop-kernels, and not only for constructive lop-kernels . This justifies why we consider henceforth only lop-kernels.

Our next objective is to prove that a lop-kernel yields an approximation algorithm. For this, we need the following definition, which is inspired by a similar notion introduced by Hochbaum and Shmoys [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems theoretical and practical results[END_REF], and referred to as f -relaxed decision procedure in [START_REF] Williamson | The Design of Approximation Algorithms[END_REF]. Definition 7. Let Π be a well-behaved maximization problem and let f : N → N be a function. An f -dual-approximation algorithm for Π is a polynomial-time algorithm that, given an instance (I, k) of Π dec , concludes one of the following:

opt Π (I) ≥ k. opt Π (I) < f (k). An f -dual approximation algorithm is constructive if, whenever it concludes that opt Π (I) ≥ k, it provides a solution s with val Π (I, s) ≥ k.
In the next lemma we prove that a lop-kernel of size s yields an f -dual-approximation algorithm (where f depends on s), which in turn yields a classical approximation algorithm whose ratio depends on s. To provide some insight on the statement of the next lemma, keep in mind that for vertex-maximization problems, the upper bound function u is typically the identity function.

Lemma 8. Let Π be a well-behaved maximization problem with a non-decreasing upper bound function u and let s : N → N be a computable function. If Π admits a lop-kernel of size s, then Π admits an f -dual-approximation algorithm where f (k

) := u(s(k)) + k + 1.
Moreover, if the lop-kernel is constructive, then the f -dual-approximation algorithm is also constructive.

Proof. Let k ∈ N, (I, k) be an instance of Π dec , and R be a lop-kernel of size s for Π. We describe an f -dual approximation algorithm A which takes as input I and k, starts by running R with input (I, k), and continues based on its possible output. If R decides that (I, k) is a yes-instance, then opt Π (I) ≥ k, and A returns opt Π (I) ≥ k as well. Notice that if R is constructive, then it provides a solution s of I such that val Π (I, s) ≥ k, and A returns this solution as well. Otherwise, we claim that it is safe for A to return opt

Π (I) ≤ f (k). Indeed, if R decides that (I, k) is a no-instance, then opt Π (I) < k, implying opt Π (I) < u(s(k)) + k = f (k).
Finally, suppose that R outputs an equivalent instance (I , k ) obtained from (I, k) using only lop-rules and such that |I | ≤ s(k). By using Observation 4 we can assume that (I , k ) is obtained from (I, k) by a single lop-rule, and Property 2 in Definition 3 implies that opt

Π (I) ≤ opt Π (I ) + (k -k ) ≤ u(|I |) + k ≤ u(s(k)) + k < f (k),
where we have used the fact that u is non-decreasing.

Let us now turn to our main results relating the size of lop-kernels to the existence of approximation algorithms. To keep statements as simple as possible, we first provide in Subsection 3.2 results that correspond to the specialized versions for vertex-maximization problems of the general results presented in Subsection 3.3.

Connection between lop-kernels and approximation algorithms for vertex-maximization problems

In this subsection we deal with vertex-maximization problems. The following lemma is a folklore result [START_REF] Williamson | The Design of Approximation Algorithms[END_REF], but as it is generally tuned for a particular function f appearing in the considered context, we need to restate it in a general form.

Lemma 9.

Let Π be a vertex-maximization problem whose decision version is in NP, and f : N → N be a computable function.

For every real number

c > 1, if Π admits an f -dual-approximation algorithm with f (k) = O(k c ),

then Π admits a polynomial-time value-approximation algorithm with ratio O(n

c-1 c ) on n-vertex graphs. 2. For every real number β ≥ 1, if Π admits an f -dual-approximation algorithm with f (k) = βk + 1, then Π admits a polynomial-time value-approximation algorithm with ratio β + ε for every real number ε > 0. Moreover, if the f -dual-approximation is constructive, then the corresponding approximation algorithm is also constructive.

Proof.

Let A be an f -dual-approximation algorithm for Π. We proceed to construct a polynomial-time approximation algorithm for Π with the claimed ratio. We consider the two statements of the lemma separately.

Case 1:

f (k) = O(k c ).
Given an n-vertex graph G as instance of Π, we find k 0 ∈ {0, . . . , n} defined as the largest positive integer k such that algorithm A returns that opt Π (G) ≥ k. Note that k 0 can be found in polynomial time by performing at most n + 1 calls to algorithm A. If there is no such k 0 , or if k 0 = 0, then opt Π (G) < max(f (0), f (1)) = O(1), and since the decision version of Π is in NP, we can find an optimal solution in polynomial time by verifying all vertex subsets of size at most max(f (0), f (1)). Otherwise, that is, if k 0 ≥ 1, our approximation algorithm returns k 0 , or if is constructive it returns a solution S 0 (a subset of vertices here) such that |S 0 | ≥ k 0 . Let us prove that it provides the claimed approximation ratio. We distinguish two subcases depending on the value of k 0 . Suppose first that

k 0 ≥ n 1/c . Since opt Π (G) ≤ n, in this case we get that opt Π (G) k 0 ≤ n n 1/c = n c-1 c .
Otherwise, it holds that k 0 < n 1/c . By the definition of k 0 we have opt Π (G) < f (k 0 + 1) = O((k 0 + 1) c ) = O((k 0 ) c ). Thus, in this case we get that

opt Π (G) k 0 = O((k 0 ) c ) k 0 = O (k 0 ) c-1 = O n c-1 c
.

Since in both cases we have a ratio of O(n c-1 c ), the lemma follows in Case 1.

Case 2:

f (k) = βk + 1.
Let ε > 0 be a arbitrary real number, let ε = ε β , and let us provide a polynomial-time approximation algorithm with ratio β(1 + ε ) = β + ε. As in Case 1, we start by finding k 0 , defined as the largest positive integer k such that algorithm

A returns that opt Π (G) ≥ k. By definition of k 0 we have opt Π (G) < f (k 0 + 1) = β(k 0 + 1) + 1 ≤ β(k 0 + 2). If k 0 < 2 ε , then opt Π (G)
is constant, and again by enumerating all subsets of size at most β( 2 ε + 2) we find an optimal solution. Otherwise, we return k 0 , or if is constructive it returns a solution S 0 (a subset of vertices here) such that

|S 0 | ≥ k 0 . We have opt Π (G) ≤ β(k 0 + 2) ≤ β(1 + ε )k 0 , concluding Case 2 of the proof.
As a vertex-maximization problem whose decision version is in NP is a well-behaved problem, the hypothesis of Lemma 8 is satisfied (taking the identity function as upper bound function), and thus the following theorem is immediate by pipelining Lemma 8 and Lemma 9.

Theorem 10. Let Π be a vertex-maximization problem whose decision version is in NP.

For every real number c > 1, if Π admits a lop-kernel with O(k c ) vertices, then it admits a polynomial-time value-approximation algorithm with ratio O(n

c-1 c ) on n-vertex graphs. 2. For every real number β ≥ 1, if Π admits a lop-kernel with βk vertices, then for any real number ε > 0, it admits a polynomial-time value-approximation algorithm with ratio (β + 1 + ε). Moreover, if the lop-kernel is constructive, then the corresponding approximation algorithm is also constructive.

As the framework of lop-kernels is mainly defined as a tool to get lop-kernel lower bounds from inapproximability, let us explicitly formulate the contrapositive of Theorem 10. Note that, when applying it to a concrete problem Π, the inapproximability of Π will rely on some complexity assumption, typically P = NP.

Corollary 11. Let Π be a vertex-maximization problem whose decision version is in

Connection between lop-kernels and approximation algorithms for well-behaved maximization problems

The following lemma and theorem are the versions of Lemma 9 and Theorem 10, respectively, in the more general setting of arbitrary well-behaved maximization problems.

Lemma 12.

Let Π be a well-behaved maximization problem, a ∈ R + , u : N → N, and f : N → N be functions such that u(n) = O(n a ), u is polynomial-time computable, and f is computable. Suppose that Π has u as upper bound function and that it admits an f -dual-approximation.

1. If f (k) = O(k d ) for some real number d > 1,

then Π admits a polynomial-time valueapproximation algorithm with ratio O(n a(d-1) d

), where n is the size of the input. 2. If f (k) = λk d + k + 1 for some real numbers d ≤ 1 and λ > 0, then Π admits a polynomial-time value-approximation algorithm with ratio λ2 d + 3. Moreover, if the f -dual-approximation algorithm is constructive, then the corresponding approximation algorithm is also constructive.

Proof. Let A be an f -dual-approximation algorithm for Π. For both cases in the statement in the lemma, we proceed to construct a polynomial-time approximation algorithm for Π with the claimed ratio.

Given an instance I of Π, we find k 0 ∈ {0, . . . , u(n)} (recall that n = |I|) defined as the largest positive integer k such that algorithm A returns that opt Π (G) ≥ k. Note that k 0 can be found in polynomial time as |I| is polynomial-time computable and its value n is polynomially upper-bounded in the classical bit-size of the instance, and that u(n) can be computed in polynomial time as well. If there is no such k 0 , or if k 0 = 0, then opt Π (G) < max(f (0), f (1)) = O(1), and since Π is well-behaved, we can, given max(f (0), f (1)), decide in polynomial time if either opt Π (I) = 0 and provide a solution s with val Π (I, s) = 0, or provide a solution s with val Π (I, s) > 0. In both cases we even have a constructive constant-factor approximation, and as opt Π (I) < f (1) = λ + 2, we get the claimed ratio in both cases. Otherwise, that is, when k 0 ≥ 1, our approximation algorithm returns k 0 , or if is constructive it returns a solution s 0 such that val Π (I, s 0 ) ≥ k 0 . Let us prove that it provides the claimed approximation ratio. We now distinguish the two cases claimed in the statement of the lemma.

Case 1:

f (k) = O(k d ).
Suppose first that k 0 ≥ n a/d . In this case we have

opt Π (I) k 0 ≤ u(n) k 0 = O(n a ) n a/d = O n a(d-1) d .
Otherwise, it holds that k 0 < n a/d . By the definition of k 0 we have opt

Π (G) < f (k 0 + 1) = O((k 0 + 1) d ) = O((k 0 ) d ).
Thus, in this case we get that

opt Π (I) k 0 = O((k 0 ) d ) k 0 = O (k 0 ) d-1 = O n a(d-1) d .
Since in both cases we have a ratio of O(n

a(d-1) d
), the lemma follows in Case 1.

Case 2:

f (k) = λk d + k + 1.
We have

opt Π (I) k 0 ≤ f (k 0 + 1) k 0 ≤ λ(k 0 + 1) d + k 0 + 2 k 0 Let h(x) = λ(x + 1) d + x + 2 x
and note that the approximation ratio is at most h(k 0 ). To bound h(k 0 ), we proceed to show that h(x) is decreasing in x when x > 0 and obtain the desired approximation ratio of h(k 0 ) ≤ h(1) = λ2 d + 3. To show that h(x) is indeed decreasing in x when x > 0, note that

∂h(x) ∂x = λ(x + 1) d x 2 • d x x + 1 -1 - 1 x 2 ,
which is negative when d ≤ 1 and x > 0.

The next theorem follows immediately by pipelining Lemma 8 and Lemma 12. Namely, starting with the hypothesis of Theorem 13, we first apply Lemma 8 and then Lemma 12 with d = ac and λ = αβ a . Theorem 13. Let Π be a well-behaved maximization problem, a, c ∈ R + , u : N → N, and ), where n is the size of the instance.

s : N → N be functions such that u(n) = O(n a ), s(k) = O(k c ), u is non-decreasing,

2.

If ac ≤ 1 and α, β ∈ R + are such that u(n) ≤ αn a and s(k) ≤ βk c , then Π admits a polynomial-time value-approximation algorithm with ratio αβ a 2 ac + 3. Moreover, if the lop-kernel is constructive, then the corresponding approximation algorithm is also constructive.

To provide some insight on the formulas used in the statement of Theorem 13, and especially on the role of the upper bound function u(n) = O(n a ), one can typically think of a graph problem where the output is a subset of edges, and where the size of an instance is the number of vertices of input graph. In that case, we have a = 2, and thus a lop-kernel of size (in terms of number of vertices) O(k c ) would only imply an O(n

2c-1 c
)-approximation algorithm, which is worse than the ratio O(n c-1 c ) obtained in Theorem 10, where a = 1. On the other hand, the ratio can also sometimes be slightly better, as there may exist problems with upper bound function u(n) = O(n a ) for some a < 1. Moreover, observe that for problems where a ≤ 1, the second item covers the case of linear kernels, which corresponds to c = 1.

By taking the contrapositive of Theorem 13, we obtain the following more general version of Corollary 11.

4

A framework for ruling out certain polynomial kernels: the case of minimization problems

In this section we adapt the framework of lop-kernels introduced in Section 3 to minimization problems. The definitions and results for minimization problems are very close to those for maximization problems, but there are a number of subtle differences that we will discuss as they appear.

We say that a minimization problem Π is well-behaved if it comes equipped with a size function (as defined in Section 2) and it satisfies the following condition, which we denote by C min : There exists a polynomial-time algorithm that, given as input an instance I of Π, decides if opt Π (I) = 0, and in this case provides a solution s where val Π (I, s) = 0, or otherwise provides any solution s.

Note that condition C min above is not the symmetric version of condition C max defined at the beginning of Section 3.

Given a well-behaved minimization problem Π, we say that a function u : N → N is an upper bound function for Π if for any instance I of Π and any solution s of I, we have val Π (I, s) ≤ u(|I|), where | • | is the size function of Π. Note that this notion of upper bound function differs from the one given for maximization problems. Again, throughout the paper, we assume that the notions of size used in both the size of kernels and the upper bound function are the same.

The reminder of this section is organized similarly to Section 3. Namely, in Subsection 4.1 we present the definition of lop-rules and lop-kernels for well-behaved minimization problems, and we prove a general technical result, namely Lemma 19. In Subsection 4.2 we present the connection between lop-kernels and approximation algorithms for vertex-minimization problems, and in Subsection 4.3 we generalize it to arbitrary well-behaved minimization problems.

Definition of lop-rules and lop-kernels

The following definition should be compared to Definition 3.

Definition 15.

A large optimal preserving reduction rule, or lop-rule for short, for a wellbehaved minimization problem Π, is a polynomial-time algorithm R that, given an instance

(I, k) of Π dec , computes another instance (I , k ) of Π dec with 0 ≤ k ≤ k and such that 1. if (I, k) is a yes-instance of Π dec , then (I , k ) is a yes-instance of Π dec , and 2. if (I, k) is a no-instance of Π dec , then opt Π (G ) ≥ opt Π (G) -(k -k ), implying that (I , k ) is a no-instance of Π dec . A lop-rule R is constructive if, for any solution s of I , it constructs (in polynomial time) a solution s of I such that val Π (I, s) ≤ val Π (I , s ) + (k -k ).
Note that Property 2 in Definition 15 is stronger than the implication "if (I, k) is a no-instance of Π dec , then (I , k ) is a no-instance of Π dec ", which would yield the definition of a classical kernelization algorithm. Observe also that the constructibility condition implies Property 2, unlike in the maximization case. Indeed, when we consider how this latter implication is generally proved in safeness proofs of classical kernels, we generally prove its contrapositive, and one of the following scenarios often occur: In Case (a), the rule preserves all optimal values, as it implies that opt Π (G ) ≥ opt Π (G) -(k -k ), and note that it implies Property 2 in Definition 15. Compared to the maximization case, Case (c) still implies only the classical implication "if (I, k) is a no-instance of Π dec , then (I , k ) is a no-instance of Π dec ", but note that Case (b) no longer implies Property 2. This is one of reasons why, in our opinion, the framework of lop-kernels seems to be more natural when applied to maximization problems.

The following observation is again an immediate consequence of the definition of a lop-rule.

Observation 16. lop-rules can be composed. Formally, consider two lop-rules R 1 and R 2 . Then, the rule R that, given a instance (I, k) of Π dec , returns R 2 (R 1 (I, k)), is also a lop-rule. Moreover, if R 2 and R 1 are constructive, then R is also constructive.

A typical example of a lop-rule for a vertex-minimization problem is when, for some problem Π, we can identify a "dominant" set of vertices that can be safely included into a solution. More precisely, consider a rule that, given a graph G, finds a subset T ⊆ V (G) and a graph G such that there exists an optimal solution S in G such that S = T ∪ S , where S is a solution in G , and for every solution S in G , S ∪ T is a solution in G. Such a rule is indeed a (constructive) lop-rule.

Even if almost all classical known reduction rules for minimization problems are loprules [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Fedor | Theory of Parameterized Preprocessing[END_REF], here is a simple example a non-lop-rule. Consider the Vertex Cover problem, and suppose that, given an instance (G, k), we find in G a matching M of size k + 1. The rule just outputs (G , k ) = (M, k), hence preserving the fact that (G, k) is a no-instance. However, this rule does not satisfy Property 2 in Definition 15, since the size of a minimum vertex cover of G may be arbitrarily large compared to k, hence the inequality opt Π (G ) ≥ opt Π (G) may not hold. In Section 5 we discuss a (much more involved) reduction rule for a vertex-minimization problem, namely Tree Deletion Set, which is not a lop-rule either.

As in the maximization case, if we defined a lop-kernel as an algorithm consisting only of lop-rules, we would exclude from being a lop-kernel, for instance, the algorithm consisting of the rule that detects a no-instance of Vertex Cover as in the above paragraph. This justifies the next definition, where we also allow lop-kernels to decide instances, and that should be compared to Definition 5.

Definition 17.

Let Π be a well-behaved minimization problem and let s : N → N be a computable function. A lop-kernel of size s for Π parameterized by the solution size is a polynomial-time algorithm that takes as input an instance (I, k) of Π dec , and either decides that (I, k) is a yes-instance or a no-instance, or outputs a reduced instance (I , k ) by applying a sequence of lop-rules to (I, k), with |I | ≤ s(k). A lop-kernel is constructive if, in the first case, it constructively decides (I, k), and, in the second case, it only uses constructive lop-rules.

Note that the constructibility condition in Definition 17 differs from that in Definition 5 for maximization problems. We need this stronger property in the proof of Lemma 19.

Our next objective is to prove that a lop-kernel yields the existence of a polynomial-time approximation algorithm. For this, we need the following definition, which is the version of Definition 7 for minimization problem.

Definition 18.

Let Π be a well-behaved minimization problem and let f : N → N. An f -dual-approximation algorithm for Π is a polynomial-time algorithm that, given an instance (I, k) of Π dec , concludes one of the following:

opt Π (I) ≤ f (k). opt Π (I) > k. An f -dual-approximation algorithm is constructive if, whenever it concludes that opt Π (I) ≤ f (k), it provides a solution s with val Π (I, s) ≤ f (k).
In the next lemma we prove that a lop-kernel of size s yields an f -dual-approximation algorithm (where f depends on s), which in turn yields a classical approximation algorithm whose ratio depends on s. As in the maximization case, to provide some insight on the statement of the next lemma, keep in mind that for vertex-minimization problems, the upper bound function u is typically the identity function. Note that in the next lemma, the derived function f (k) differs slightly from that of Lemma 8; this is due to technical reasons motivated by the fact that there the maximization and minimization versions of our framework are not totally symmetric.

Lemma 19.

Let Π be a well-behaved minimization problem with a non-decreasing upper bound function u and let s : N → N be a computable function. If Π admits a lop-kernel of size s, then Π admits an f -dual-approximation algorithm where f (k) := u(s(k)) + k. Moreover, if the lop-kernel is constructive, then the f -dual-approximation algorithm is also constructive.

Proof. Let k ∈ N, (I, k) be an instance of Π dec , and R be a lop-kernel of size s for Π. We describe an f -dual-approximation algorithm A which takes as input I and k, starts by running R with input (I, k), and continues based on its possible output. If R decides that (I, k) is a no-instance, then opt Π (I) > k, and A returns opt Π (I) > k. If R decides that (I, k) is a yes-instance, then opt Π (I) ≤ k, and A returns opt Π (I) ≤ k ≤ f (k) as well. Notice that if R is constructive, then it provides a solution s of I such that val Π (I, s) ≥ k, and A returns this solution as well.

Finally, suppose that R outputs an equivalent instance (I , k ) obtained from (I, k) using only lop-rules and such that |I | ≤ s(k). By using Observation 16 we can assume that (I , k ) is obtained from (I, k) by a single lop-rule. Let us start by the non-constructive case, in which A returns opt

Π (I) ≤ f (k). If opt Π (I) ≤ k, then we are done as k ≤ f (k). If opt Π (I) > k, Property 2 in Definition 15 implies that opt Π (I) ≤ opt Π (I ) + (k -k ) ≤ u(|I |) + k ≤ u(s(k)) + k = f (k)
, where we have used that u is non-decreasing. Let us now turn to the constructive case. As Π is well-behaved and verifies C min , we can compute in polynomial time a solution s (of any cost), and according to the definition of u we have val Π (I , s ) ≤ u(|I |) ≤ u(s(k)), where we have used again that u is non-decreasing. Finally, as the rule is constructive, we can construct in polynomial time a solution s such that val Π (I, s) ≤ val Π (I , s ) + k ≤ f (k), and algorithm A returns this solution as well.

Let us now turn to our main results relating the size of lop-kernels with the existence of approximation algorithms. As in Section 3, to keep statements as simple as possible, we provide in Subsection 4.2 results that correspond to the specialized versions for vertexmaximization problems of results in Subsection 4.3.

Connection between lop-kernels and approximation algorithms for vertex-minimization problems

In this subsection we deal with vertex-minimization problems. The following lemma, which should be compared to Lemma 9 Note that the hypothesis in the second item of Lemma 9 is slightly different from the one below, and that the obtained approximation ratios are also slightly different. ) on n-vertex graphs.

Lemma 20. Let Π be a vertex-minimization problem whose decision version is in

If Π admits a f -dual-approximation algorithm where f (k) = βk, then Π admits a polynomial-time value-approximation algorithm with ratio β. Moreover, if the f -dual-approximation is constructive, then the corresponding approximation algorithm is also constructive.

Proof. Let A be an f -dual-approximation algorithm for Π. We proceed to construct a polynomial-time approximation algorithm for Π with the claimed ratio. We consider the two statements of the lemma separately.

Case 1: f (k) = O(k c ).

Given an n-vertex graph G as instance of Π, we find k 0 ∈ {0, . . . , n} defined as the smallest positive integer k such that algorithm A returns that opt Π (G) ≤ f (k). Note that k 0 can be found in polynomial time by performing at most n + 1 calls to algorithm A. Notice that k 0 always exists as we cannot have opt Π (G) > n. If k 0 = 0, then opt Π (G) ≤ f (0) = O(1), and since the decision version of Π is in NP, we can find an optimal solution in polynomial time by verifying all vertex subsets of size at most f (0). Otherwise, that is, if k 0 ≥ 1, our approximation algorithm returns f (k 0 ), or if is constructive it returns a solution S 0 (that is, a subset of vertices) such that |S 0 | ≤ f (k 0 ). By definition of k 0 , we have that opt Π (G) > k 0 -1, or equivalently opt Π (G) ≥ k 0 . Let us prove that this algorithm provides the claimed approximation ratio. We distinguish two subcases depending on the value of k 0 . Suppose first that k 0 ≥ n 1/c . In this case we get that

f (k 0 ) opt Π (G) ≤ n k 0 ≤ O(n c-1 c ).
Otherwise, it holds that k 0 < n 1/c . In this case we get that

f (k 0 ) opt Π (G) ≤ f (k 0 ) k 0 < O(k c-1 0 ) = O(n c-1 c ).
Since in both cases we have a ratio of O(n c-1 c ), the lemma follows in Case 1.

Case 2: f (k) = βk.

As in Case 1, we start by finding k 0 defined as the smallest positive integer k such that algorithm A returns that opt Π (G) ≤ f (k). If k 0 = 0 we proceed as in the first case. Otherwise, we return f (k 0 ), or if the algorithm is constructive we return a solution S 0 (that is, a subset of vertices) such that |S 0 | ≥ f (k 0 ). We have

f (k 0 ) opt Π (G) ≤ f (k 0 ) k 0 ≤ β,
and the lemma follows in Case 2.

As a vertex-minimization problem whose decision version is in NP is a well-behaved problem, the hypothesis of Lemma 20 is satisfied (by taking the identity function as upper bound function), and thus the following theorem is immediate by pipelining Lemma 19 and Lemma 20. The next theorem should be compared to Theorem 10.

Theorem 21. Let Π be a vertex-minimization problem whose decision version is in NP.

For every real number c > 1, if Π admits a lop-kernel with O(k c ) vertices, then it admits a polynomial-time value-approximation algorithm with ratio O(n c-1 c

) on n-vertex graphs.

For every real number c > 1, if Π admits a lop-kernel with at most ck vertices, then it admits a polynomial-time value-approximation algorithm with ratio (c + 1). Moreover, if the lop-kernel is constructive, then the corresponding approximation algorithm is also constructive.

As the framework of lop-kernels is mainly defined as a tool to get lop-kernel lower bounds from inapproximability, let us explicitly formulate the contrapositive of Theorem 21. Note again that, when applying it to a concrete problem Π, the inapproximability of Π will rely on some complexity assumption, typically P = NP.

Case 1: f

(k) = O(k d ).
Suppose first that k 0 ≥ n a/d . In this case we have

f (k 0 ) opt Π (I) ≤ u(n) k 0 ≤ O(n a ) k 0 = O n a(d-1) d .
Otherwise, it holds that k 0 < n a/d In this case we get that

f (k 0 ) opt Π (I) = O((k 0 ) d ) k 0 = O (k 0 ) d-1 = O n a(d-1) d
.

Since in both cases we have a ratio of O(n a(d-1) d

), the lemma follows in Case 1.

Case 2: f (k) = λk d + k.

In this case we have

f (k 0 ) opt Π (I) ≤ λk d 0 + k 0 k 0 = λ(k 0 ) d-1 + 1.
As d ≤ 1, the last expression in the above equation is decreasing in k 0 , and as k 0 ≥ 1, the maximum is reached for k 0 = 1, and the approximation ratio claimed in Case 2 follows.

The next theorem, which should be compared to Theorem

If ac > 1, then Π admits a polynomial-time value-approximation algorithm with ratio O(n ac-1 c

).

2.

If ac ≤ 1 and α, β ∈ R + are such that u(n) ≤ αn a and s(k) ≤ βk c , then Π admits a polynomial-time value-approximation algorithm with ratio αβ a + 1. Moreover, if the lop-kernel is constructive, then the corresponding approximation algorithm is also constructive.

The discussion provided right after Theorem 13 also applies to the above theorem. The contrapositive of Theorem 24 yields the following corollary.

Corollary 25. Let Π be a well-behaved minimization problem with a non-decreasing polynomial-time computable upper bound function

u(n) = O(n a ) for a ∈ R + .
In what follows, the size of the instance, denoted by n, and the size of the kernel are defined according to the same size function | • | associated with Π. 1. For every real number r ∈ (0, 1), if Π does not admit a polynomial-time value-approximation algorithm with ratio O(n r ), then Π parameterized by the solution size does not admit a lop-kernel of size O(k 1 a-r ). 2. Suppose that u(n) ≤ αn a for some α ∈ R + . For every real number β > 1, if Π does not admit a polynomial-time value-approximation algorithm with ratio β, then Π parameterized by the solution size does not admit a lop-kernel of size β k c for any real numbers β , c such that ac ≤ 1 and αβ a + 1 ≤ β. Moreover, if the non-existence of approximation algorithms only holds for constructive approximation algorithms, then the lower bound only holds for constructive lop-kernels.

Applications of the framework of lop-kernels

In this section we provide several applications of the framework of lop-kernels introduced in Section 3 and Section 4.

Our first application concerns the Maximum Minimal Vertex Cover problem, defined in Section 2. Boria et al. [START_REF] Boria | On the max min vertex cover problem[END_REF] proved that Maximum Minimal Vertex Cover does not admit a polynomial-time O(n 1 2 -ε )-approximation algorithm for any ε > 0, unless P = NP. Hence, by applying Corollary 11 with r = 1 2 -ε we obtain the following corollary, which matches the best known kernel having O(k 2 ) vertices [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF].

Corollary 26. Maximum Minimal Vertex Cover parameterized by the solution size

does not admit a lop-kernel with O(k 2-ε ) vertices for any ε > 0, unless P = NP.

Our second application is similar to the first one. In the Maximum Minimal Feedback Vertex Set problem, given an n-vertex graph G and an integer k, the objective is to decide if there exists a minimal feedback vertex set S ⊆ V (G) (i.e., a set S such that G \ S is a forest) of size at least k. Dublois et al. [START_REF] Dublois | In)approximability of Maximum Minimal FVS[END_REF] recently proved that the problem does not admit a polynomial-time O(n 2 3 -ε )-approximation algorithm for any ε > 0, unless P = NP. Hence, by applying Corollary 11 with r = 2 3 -ε we obtain the following corollary, which matches the best known kernel with O(k 3 ) vertices also provided by Dublois et al. [START_REF] Dublois | In)approximability of Maximum Minimal FVS[END_REF].

Corollary 27. Maximum Minimal Feedback Vertex Set parameterized by the solution size does not admit a lop-kernel with O(k 3-ε ) vertices for any ε > 0, unless P = NP.

Our third application concerns a vertex-minimization problem. In the Tree Deletion Set problem, given a graph G and an integer k, the objective is to decide whether at most k vertices can be deleted from an n-vertex graph G in order to obtain a tree. It is known that this problem does not admit a polynomial-time O(n 1-ε )-approximation for any ε > 0 unless P = NP [START_REF] Yannakakis | The effect of a connectivity requirement on the complexity of maximum subgraph problems[END_REF]. Corollary 22 implies the following. The interesting fact is that Tree Deletion Set admits a kernel with O(k 4 ) vertices [START_REF] Archontia | Tree Deletion Set has a polynomial kernel but no OPT O(1) approximation[END_REF]. This kernel is the only non-artificial example of non-lop-kernel that we are aware of so far. Thus, the algebraic reduction rule presented by Giannopoulou et al. [START_REF] Archontia | Tree Deletion Set has a polynomial kernel but no OPT O(1) approximation[END_REF], which is based on identifying a subset of linear equations of appropriate size that captures all solutions of size at most k, cannot be (even transformed to) a lop-rule.

Our last application deals with the Maximum Independent Set problem restricted to K t -free graphs, for an integer t ≥ 3. Ramsey's theorem [START_REF] Frank | On a problem of formal logic[END_REF] implies that, given a K t -free graph on n vertices, it is always possible to find in polynomial time an independent set of size at least n 1 t-1 . This directly implies a polynomial-time n t-2 t-1 -approximation algorithm for Maximum Independent Set on K t -free graphs, and a constructive lop-kernel of size k t-1 (indeed, if the input graph has size al least k t-1 , we can safely declare it a yes-instance). To the best of our knowledge, improving this trivial approximation factor is still open, and the only known inapproximability result is the bound O(n 1 4 -ε ) on triangle-free graphs recently proved by Bonnet et al. [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF], which relies on the hypothesis that NP BPP. In the same paper [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF], the authors state the following conjecture, called the "Improved Approximation Conjecture": for every fixed graph H, there exists a constant ε > 0 such that Maximum Independent Set admits a (randomized) polynomial-time n 1-ε -approximation algorithm on H-free n-vertex graphs. We state the following conjecture.

Conjecture 29. For every fixed graph H, the Maximum Independent Set problem restricted to H-free graphs admits a polynomial lop-kernel.

Corollary 11, combined with the above discussion and the inapproximability result of Bonnet et al. [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF] on triangle-free graphs, imply the following.

Corollary 30. The following claims hold:

Maximum Independent Set parameterized by the solution size does not admit a lop-kernel with O(k 4-ε ) vertices on triangle-free graphs for any ε > 0, unless NP ⊆ BPP. For every real number ε > 0 and every integer t ≥ 3, a lop-kernel with O(k t-1-ε ) vertices for Maximum Independent Set on K t -free graphs would improve the best known approximation ratio n t-2 t-1 that follows from Ramsey's theorem [START_REF] Frank | On a problem of formal logic[END_REF]. Conjecture 29 implies the Improved Approximation Conjecture of Bonnet et al. [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF].

6

An attempt to obtain a linear kernel for MMVC

In this section we briefly explain the flaw in the linear kernel for Maximum Minimal Vertex Cover (MMVC) claimed by Fernau [34,Corollary 4.25], and that is based on joint unpublished work with Dehne, Fellows, Prieto, and Rosamond. The kernelization algorithm is a small modification of a linear kernel for the Nonblocker Set problem presented by Ore [START_REF] Ore | Theory of Graphs[END_REF]. A set of vertices S of a graph G is a nonblocker if its complement is a dominating set of G, that is, for every u ∈ S there exists v / ∈ S with {u, v} ∈ E(G). In the Nonblocker Set problem, we are given a graph G and an integer parameter k, and the goal is to decide whether G contains a nonblocker of size at least k. Suppose for simplicity that G is connected. The idea is to consider an arbitrary spanning tree T of G, root it arbitrarily at a vertex r, and partition V (G) = V 0 V 1 such that the vertices in V 0 (resp. V 1 ) are within even (resp. odd) distance from r in T . By construction, each of V 0 and V 1 is a nonblocker in G, so if one of them has size at least k, we can answer "yes", and otherwise |V (G)| ≤ 2k and we are done.

Back to MMVC, it is observed in [34, Reduction rule 24] that a simple reduction rule allows to assume that no connected component of G is a clique (in particular, an isolated vertex). Assume again for simplicity that G is connected. It is then claimed in [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF] that, using the same algorithm as for Nonblocker Set, the largest of V 0 and V 1 , say V 0 , can be always completed into a minimal vertex cover of G, which would immediately yield a kernel of size at most 2k for MMVC. Unfortunately, this claim is not true: when adding new vertices to V 0 in order to make it a vertex cover of G, we may lose the minimality property, and some vertices may need to be removed. For instance, let G be the graph obtained from a triangle on vertices u, v, w by adding p ≥ 2 pendant vertices to each of u, v, and w. Let T be the spanning tree obtained from G by removing the edge {v, w}, and root T at vertex u.

Then |V 0 | = 1 + 2p and |V 1 | = 2 + p, so |V 0 | > |V 1 |,
and note that the edge {v, w} is the only edge of G not covered by V 0 . But adding either of v or w to V 0 , say v, results in a non-minimal vertex cover of G, and therefore the p pendant vertices adjacent to v have to be removed from V 0 , which yields a set of size 2

+ p < |V (G)| 2 = 3+3p
2 , where we have used that p ≥ 2. In fact, deciding whether a set S ⊆ V (G) can the extended to a minimal vertex cover of G is an NP-complete problem [START_REF] Casel | Extension of Vertex Cover and Independent Set in Some Classes of Graphs[END_REF].

Subquadratic kernels for MMVC on particular graph classes

In this section we present subquadratic kernels for Maximum Minimal Vertex Cover restricted to particular graph classes when the parameter is the solution size k. Namely, in Subsection 7.1 we provide kernels using the Erdős-Hajnal property, and in Subsection 7.2 we provide further observations about other graph classes.

Kernels using the Erdős-Hajnal property

For a constant δ > 0, a graph H is said to satisfy the Erdős-Hajnal property with constant δ if every H-free graph G on n vertices contains either a clique or an independent set of size n δ . The (still open) Erdős-Hajnal conjecture [START_REF] Erdős | Ramsey-type theorems[END_REF] states that every graph H satisfies the Erdős-Hajnal property. As reported by Chudnovsky [START_REF] Chudnovsky | The Erdős-Hajnal Conjecture -A Survey[END_REF], the Erdős-Hajnal conjecture has been verified for only a small number of graphs, namely all graphs on at most four vertices, the bull (i.e., the graph obtained by adding a pendant vertex to two different vertices of a triangle), the complete graphs, and every graph that can be constructed from them using the so-called substitution operation [START_REF] Noga Alon | Ramsey-type theorems with forbidden subgraphs[END_REF], which we define later. Since our goal is to use the Erdős-Hajnal property in order to obtain kernels for Maximum Minimal Vertex Cover, we need an algorithmic version of it. As defined by Bonnet et al. [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF], for a constant δ > 0, a graph H is said to satisfy the constructive Erdős-Hajnal property with constant δ if there exists an algorithm that takes as input an H-free graph G on n vertices, and outputs in polynomial-time a clique or an independent set of G of size at least n δ . Fortunately for our purposes, all the graphs H shown to satisfy the Erdős-Hajnal property so far, also satisfy its constructive version [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF].

In the following simple lemma we show that, if H is a graph satisfying the constructive Erdős-Hajnal property, then the vertex set of an H-free graph can be partitioned in polynomial time into "few" cliques or independent sets. This partition will then be used to obtain subquadratic kernels on H-free graphs for several graphs H.

Lemma 31. Let H be a graph satisfying the constructive Erdős-Hajnal property with constant δ. The vertex set of any H-free graph G on n vertices can be partitioned in polynomial time into a collection of cliques C and a collection of independent sets

I such that |C| + |I| ≤ 1 2 (1-δ) -1 • n 1-δ .
Proof. Let G be an H-free graph on n vertices. We initialize X 0 = V (G), C = I = ∅, and we run the following procedure as far as

|X 0 | ≥ 1: Find in polynomial time a clique or an independent set Y in G[X 0 ] with |Y | ≥ |X 0 | δ . Note that this is possible since G[X 0 ] is an H-free graph for any X 0 ⊆ V (G).
Add Y to C or to I depending on whether Y is a clique or an independent set, respectively (if

|Y | = 1, choose C or I arbitrarily). Update X 0 ← X 0 \ Y .
Clearly, the above algorithm terminates in polynomial time. It remains to bound |C| + |I|, which is equal to the number of iterations of the algorithm. To this end, for a positive integer i, we say that an iteration belongs to step i of the algorithm if the current set X 0 at the start of the iteration satisfies n

2 i < |X 0 | ≤ n 2 i-1 .
We denote by t i the number of iterations of the algorithm within step i. By definition, |C| + |I| = ∞ i=1 t i . Let Y be a clique or an independent set found by the algorithm within step i. Since the current set X 0 satisfies

|X 0 | > n 2 i , we have that |Y | > n 2 i
δ . And since the sum of the sizes of the sets found before the last iteration of step i is at most n 2 i , it follows that t i ≤ n 2 i 1-δ . Note that, in particular, t i = 0 for i > log n . Therefore, we conclude that

|C| + |I| = ∞ i=1 t i ≤ ∞ i=1 n 2 i 1-δ = n 1-δ • ∞ i=1 1 2 1-δ i = n 1-δ • 1 2 (1-δ) -1 ,
and the lemma follows.

We are now ready to present the subquadratic kernel on bull-free graphs. Note that, since bipartite graphs are bull-free, MMVC restricted to bull-free graphs is NP-hard by [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF] (or by Theorem 42). In the kernels presented in this section, since we can easily obtain explicit constants, we decided not to use the big-O notation.

Theorem 32. The Maximum Minimal Vertex Cover problem parameterized by k restricted to bull-free graphs admits a kernel with at most c(k -1) 7/4 + k -1 vertices, where c = 2 Proof. Let (G, k) be an instance of the Maximum Minimal Vertex Cover problem, where G is a bull-free graph. Recall that by Lemma 2 we can assume that the maximum degree of G is at most k -1. We start by finding greedily, starting from V (G), a minimal vertex cover X of G. Note that X can be easily found in polynomial time by Observation 1. If |X| ≥ k, we conclude that (G, k) is a yes-instance, so we can assume that |X| ≤ k -1. Let S = V (G) \ X and note that S is an independent set.

Since the bull satisfies the constructive Erdős-Hajnal property with constant δ = 1 4 [START_REF] Bonnet | An algorithmic weakening of the Erdős-Hajnal conjecture[END_REF][START_REF] Chudnovsky | The Erdős-Hajnal conjecture for bull-free graphs[END_REF], we can apply Lemma 31 to the bull-free graph G[X] and obtain in polynomial time a partition of X into a collection of cliques C and a collection of independent sets I such that

|C| + |I| ≤ d • |X| 3/4 ≤ d • (k -1) 3/4 , where d = 1 2 3 4 -1 < 1.

Since we can assume that

G has no isolated vertices, as they can be safely removed without affecting the type of the instance, it follows that

S = C∈C N S (C) ∪ I∈I N S (I). (1)
Hence, our objective is to bound |N S (Y )| for every Y ∈ C ∪ I. Suppose first that I ∈ I is an independent set. From Lemma 2, if |N S (I)| ≥ k we can conclude that (G, k) is a yes-instance, so we can assume henceforth that for every independent set

I ∈ I, it holds |N S (I)| ≤ k -1. (2)
Suppose now that C ∈ C is a clique. We partition N S (C) = S 1 C S 2 C as follows. Let S 1 C be an inclusion-wise maximal set of vertices in N S (C) such that for any two (not necessarily distinct) vertices x, y

∈ S 1 C , |N C (x) ∪ N C (y)| ≤ |C| -1. That is, S 1 C is a maximal set in N S (C)
such that the neighborhoods of its vertices pairwise do not cover the whole clique C. We let

S 2 C = N S (C) \ S 1 C .
The following is the crucial property of the set S 1 C .

Claim 33. The vertices in S 1 C can be ordered x 1 , . . . , x p so that N C (x i ) ⊆ N C (x j ) whenever i ≤ j.

Proof. In order to prove the claim, it is sufficient to prove that, for any two vertices x, y

∈ S 1 C , either N C (x) ⊆ N C (y) or N C (y) ⊆ N C (x)
. Suppose for the sake of contradiction that there exist two vertices u

∈ N C (x) \ N C (y) and v ∈ N C (y) \ N C (x)
. By definition of the set S 1 C , there exists a vertex w ∈ C \ (N C (x) ∪ N C (y)). But then the vertices x, y, u, v, w induce a bull as illustrated in Figure 1, contradicting the hypothesis that G is bull-free. Since x could not be added to S 1 C , there exists a vertex y 1). Using again the fact that z has degree at most k -1 in G, we obtain that

∈ S 1 C such that N C (x) ∪ N C (y) = C. But since z ∈ C \ y∈S 1 C N C (y), necessarily z ∈ N C (x). It follows that z ∈ x∈S 2 C N C (x) (see Figure
|S 2 C | ≤ k -1. Summarizing, we have that for every clique C ∈ C, it holds |N S (C)| = |S 1 C | + |S 2 C | ≤ 2(k -1). (3)
Putting all pieces together, Equations ( 1), (2), and (3) and the fact that |X| ≤ k -1 and

|C| + |I| ≤ d • |X| 3/4
imply that, unless we have already concluded that (G, k) is a yes-instance, we have that

|V (G)| = |X| + |S| = |X| + | C∈C N S (C)| + | I∈I N S (I)| ≤ |X| + (|C| + |I|) • max Y ∈C∪I |N S (Y )| ≤ k -1 + d • (k -1) 3/4 • 2(k -1) = 2d • (k -1) 7/4 + k -1,
and the theorem follows.

It is easy to prove that, for every integer t ≥ 2, every K t -free graph G on n vertices has an independent set of size n 1 t-1 , by induction on t: for t = 2 the statement is trivial, and if t ≥ 3, then either ∆(G) < n t-2 t-1 , and an independent set of size n 1 t-1 can be found greedily by adding any vertex to it and deleting its neighborhood, or there exists a vertex v ∈ V (G) of degree at least n t-2 t-1 , in which case an independent set of size n 1 t-1 can be found applying the inductive hypothesis to the K t-1 -free graph G[N (v)]. Clearly, this proof can be translated to a polynomial-time algorithm to find an independent set of the appropriate size. Therefore, for any integer t ≥ 2, K t satisfies the constructive Erdős-Hajnal property with constant δ = 1 t-1 . The proof of the following theorem is a simplified version of that of Theorem 32. Note that, since bipartite graphs are K t -free for every t ≥ 3, MMVC is NP-hard on K t -free graphs [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF].

Theorem 34. For every integer t ≥ 3, the Maximum Minimal Vertex Cover problem parameterized by k restricted to K t -free graphs admits a kernel with at most c t (k-1)

2t-3 t-1 +k-1 vertices, where c t = t-1 2 t-2 t-1 -1 .
Proof. As in the proof of Theorem 32, given an instance (G, k) of Maximum Minimal Vertex Cover, where G is a K t -free graph, we partition V (G) = X S, where X is a minimal vertex cover of G with |X| ≤ k -1, and we use Lemma 31 to partition X into two collections C and I of cliques and independent sets, respectively, with

|C| + |I| ≤ d t • |X| t-2 t-1 , where d t = 1 2 t-2 t-1 -1
. Equations ( 1) and ( 2 (4)

Combining Equations ( 1), [START_REF] Allan | On domination and independent domination numbers of a graph[END_REF], and (4) we get

|V (G)| ≤ |X| + (|C| + |I|) • max Y ∈C∪I |N S (Y )| ≤ k -1 + d t • (k -1) t-2 t-1 • (t -1)(k -1),
and the theorem follows.

We now extend the results of Theorem 32 and Theorem 34 to more general excluded induced graphs H, by making use of the aforementioned substitution operation. As defined by Alon et al. [START_REF] Noga Alon | Ramsey-type theorems with forbidden subgraphs[END_REF], for two graphs H 1 and H 2 on disjoint vertex sets, we say that H is obtained from H 1 by substituting H 2 for v ∈ V (H 1 ) (or just obtained from H 1 by substituting

H 2 if the vertex v in question is not important) if V (H) = (V (H) \ {v}) ∪ V (H 2 ), H[V (H 2 )] = H 2 , H[V (H 1 ) \ {v}] = H 1 \ v, and u ∈ V (H 1 ) is adjacent in H to w ∈ V (H 2 ) if and only if u is adjacent in H 1 to v.
Alon et [START_REF] Noga Alon | Ramsey-type theorems with forbidden subgraphs[END_REF] For an integer t ≥ 2, we define the t-bull as the graph obtained from K t by adding a pendant vertex to two different vertices of the clique. Note that the 2-bull is equal to P 4 and that the 3-bull is equal to the bull. Note also that, for every t ≥ 3, the t-bull is obtained from the bull by substituting K t-2 for the vertex of degree two of the bull. Therefore, by the discussion in the above paragraph, since the bull and K t-2 satisfy the constructive Erdős-Hajnal property with constants 1 4 and 1 t-3 , respectively, it follows that, for every t ≥ 4, the t-bull satisfies the constructive Erdős-Hajnal property with constant

δ t = 1 t-3 1 4 + 5 t-3 = 4 t + 17
.

The proof of the next theorem follows again (and generalizes) that of Theorem 32. Note that Theorem 35 corresponds to the particular case t = 3 of Theorem 34. Note also that bipartite graphs are t-bull-free for t ≥ 3, hence MMVC is NP-hard on t-bull-free graphs for t ≥ 3 [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF]. On the other hand, 2-bull-free graphs are exactly P 4 -free graphs, also called cographs, which have cliquewidth at most two, hence by Observation 40 (proved later in Subsection 7.2) MMVC can be solved in polynomial time on this class. Theorem 35. For every integer t ≥ 3, the Maximum Minimal Vertex Cover problem parameterized by k restricted to t-bull-free graphs admits a kernel with at most c t (k -1) N C (y), there exists an index j ∈ [t -2] such that z j ∈ N C (x). That is, every vertex x ∈ S 2 C is adjacent to at least one of the vertices z 1 , . . . , z t-2 . Using again the fact that each of the vertices z 1 , . . . , z t-2 has degree at most k -1 in G, we obtain that |S 2 C | ≤ (t -2)(k -1). Summarizing, we have that

for every clique C ∈ C, it holds |N S (C)| = |S 1 C | + |S 2 C | ≤ (t -1)(k -1). (5)
Putting all pieces together, Equations ( 1), (2), and ( 5) and the fact that |X| ≤ k -1 and |C| + |I| ≤ d t • |X| 1-δt imply that, unless we have already concluded that (G, k) is a yes-instance, we have that

|V (G)| ≤ |X| + (|C| + |I|) • max Y ∈C∪I |N S (Y )| ≤ k -1 + d t • (k -1) 1-δt • (t -1)(k -1),
and the theorem follows.

Let the paw be the graph obtained from a triangle by adding a pendant edge. Gyárfás [START_REF] Gyárfás | Reflections on a Problem of Erdős and Hajnal[END_REF] showed that the paw satisfies the constructive Erdős-Hajnal property with constant δ = 1 3 . Note that bipartite graphs are paw-free, hence MMVC is NP-hard on paw-free graphs [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF].

Putting all pieces together, Equations ( 1), ( 2), and ( 6) and the fact that |X| ≤ k -1 and

|C| + |I| ≤ d • |X| 2/3
imply that, unless we have already concluded that (G, k) is a yes-instance, we have that

|V (G)| ≤ |X| + (|C| + |I|) • max Y ∈C∪I |N S (Y )| ≤ k -1 + d • (k -1) 2/3 • 2(k -1),
and the theorem follows.

Remarks on other graph classes

In this subsection we provide additional observations about the complexity of the Maximum Minimal Vertex Cover problem restricted to special graph classes.

Lemma 38. For every integer t ≥ 1, the Maximum Minimal Vertex Cover problem parameterized by k restricted to K 1,t -free graphs admits a kernel with at most t(k -1) vertices.

Proof. Given an instance (G, k) of Maximum Minimal Vertex Cover, where G is a K 1,t -free graph, we again partition V (G) = X S, where X is a minimal vertex cover of G with |X| ≤ k -1. Since G is K 1,t -free and S is an independent set, it holds that for every v ∈ X, |N S (v)| ≤ t -1, and since we can assume that G contains no isolated vertex, we obtain that

|V (G)| = |X| + | v∈X |N S (v)| ≤ k -1 + (t -1)(k -1) = t(k -1).
Let C be a graph class such that there exists a polynomial-time algorithm that, given a graph G ∈ C, outputs a proper coloring of the vertices of G using at most c colors, for some integer c ≥ 1. We say that such a graph class C is poly-χ-c-bounded. Examples of poly-χ-c-bounded classes are planar graphs, minor-free graphs, or, more generally, graphs of bounded expansion. We note that Fernau [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF]Corollary 4.14] provides a similar observation for the particular case of planar graphs. Lemma 39. For every integer c ≥ 1, the Maximum Minimal Vertex Cover problem parameterized by k restricted to the class of poly-χ-c-bounded graphs admits a kernel with at most c(k -1) vertices.

Proof. Given an instance (G, k) of MMVC, where G belongs to a poly-χ-c-bounded class, we first compute in polynomial time a proper vertex coloring of G using at most c colors. We may clearly assume that G has no isolated vertices, as such vertices can be safely removed.

Let V (G) = S 1 • • • S c be the corresponding partition of V (G) into independent sets. By Lemma 2, for every i ∈ [c] there exists a minimal vertex cover of G that contains N (S i ). Hence, if for some i ∈ [c] we have that |N (S i )| ≥ k, we can safely answer "yes", so we may assume that, for every i ∈ [c], |N (S i )| ≤ k -1. Since G has no isolated vertices and every set S i is an independent set, it follows that V (G) = i∈[c] N (S i ), so we have that

|V (G)| ≤ i∈[c] |N (S i )| ≤ c(k -1).
Another graph class K that allows for linear kernels is defined such that, for every graph G ∈ K, the minimum size of a dominating set of G is equal to the size of a minimum independent dominating set of G. We furthermore ask K to be hereditary. Such graphs have been studied, for instance, in [START_REF] Allan | On domination and independent domination numbers of a graph[END_REF][START_REF] Topp | On graphs with equal domination and independent domination numbers[END_REF], and include in particular K 1,3 -free graphs (note that a generalization to K 1,t -graphs is given in Lemma 38). us see why the class K allows for a linear kernel. As discussed at the end of Section 8, the complement of a dominating set is called a nonblocker, and the Nonblocker Set problem admits a linear kernel [START_REF] Fernau | Parameterized algorithms: a graph-theoretic approach[END_REF]. On the other hand, the complement of an independent dominating set is a minimal vertex cover. Hence, if G ∈ K, an instance (G, k) of Nonblocker Set is positive if and only if (G, k) is a positive instance of MMVC. Note the linear kernel for the Nonblocker Set problem discussed at the end of Section 8 outputs a subgraph G of G, and we have that G ∈ K since K is hereditary. Hence, the equivalence between Nonblocker Set and MMVC also holds for G , and it follows that this kernel is also a linear kernel for MMVC restricted to graphs in K.

Our last contribution in this section concerns graph classes of bounded cliquewidth. Cliquewidth, which we do not need to define here, is a graph parameter that is "smaller" than treewidth in the sense that graph classes of bounded treewidth have also bounded cliquewidth (the opposite is not true, as cliques have cliquewidth one but unbounded treewidth); see [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF] for the formal definition.

The variation of monadic second order logic of graphs called MSO 1 is defined by a syntax that includes the logical connectives ∨, ∧, ¬, variables for vertices, edges, sets of vertices (but not sets of edges), the quantifiers ∀, ∃ that can be applied to these variables, and the binary relations expressing whether a vertex belongs to a set, whether an edge is incident to vertex, whether two vertices are adjacent, and whether two sets are equal. It is well-known that finding a minimum or maximum weight vertex set that satisfies a given graph property expressed in MSO 1 can be solved in linear time on graphs of cliquewidth bounded by a constant [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF][START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF]. Observation 40. The Maximum Minimal Vertex Cover problem can be expressed in MSO 1 , and therefore it can be solved in linear time when restricted to any graph class of cliquewidth bounded by a constant.

Proof. Given a graph G, we can express the property of a vertex set S being a minimal vertex cover of G in the syntax of MSO 1 as follows: for every pair of vertices u, v such that u is adjacent to v, u ∈ S or v ∈ S (this guarantees that S is a vertex cover of G), and for every vertex v ∈ V (G), v / ∈ S or there exists a vertex u adjacent to v such that u / ∈ S (this guarantees, by Observation 1, that S is minimal).

Let the diamond be the graph obtained from K 4 by removing an edge. Since Brandstädt [START_REF] Brandstädt | P5, diamond)-free graphs revisited: structure and linear time optimization[END_REF] proved that {P 5 , diamond}-free graphs have bounded cliquewidth, from Observation 40 we immediately get the following corollary.

Corollary 41. The Maximum Minimal Vertex Cover problem restricted to {P 5 , diamond}free graphs can be solved in linear time.

Ruling out polynomial kernels for MMVC for smaller parameters

In this section we rule out, assuming that NP coNP/poly, the existence of polynomial kernels for MMVC parameterized by the size of a minimum vertex cover of the input graph. As mentioned in the introduction, the reduction given in Theorem 42 also provides an alternative proof of the NP-completeness of MMVC on bipartite graphs, which also follows from [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF]. We note that the existing NP-hardness reductions for MMVC, such as the one in [START_REF] Boliac | Independent domination in finitely defined classes of graphs[END_REF], do not seem to be easily modifiable so to yield the non-existence of polynomial kernels.

Theorem 42. The Maximum Minimal Vertex Cover problem parameterized by the size of a minimum vertex cover (or of a maximum matching) of the input graph does not admit a polynomial kernel unless NP ⊆ coNP/poly, even restricted to bipartite graphs.

Proof. We present a PPT from Monotone Sat parameterized by the number of variables, which is also an NP-completeness reduction. The Monotone Sat problem is the restriction of the Sat problem to formulas in which the literals in each clause are either all positive or all negative. This problem is well-known to be NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], and it is easy to see that, when parameterized by the number of variables, it does not admit a polynomial kernel unless NP ⊆ coNP/poly. Indeed, Fortnow and Santhanam [START_REF] Fortnow | Infeasibility of instance compression and succinct PCPs for NP[END_REF] proved that the Sat problem parameterized by the number of variables does not admit a polynomial kernel unless NP ⊆ coNP/poly, and the classical reduction from Sat to Monotone Sat that replaces each variable with a "positive" and a "negative" variable and adds extra clauses appropriately [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] is in fact a PPT when the parameter is the number of variables.

Given an instance φ of Monotone Sat, where the formula φ contains n variables and m clauses, we construct in polynomial time an instance (G, k) of Maximum Minimal Vertex Cover as follows. For each variable x i of φ, i ∈ [n], we add to G four vertices i , x + i , x - i , r i and three edges { i , x + i }, {x + i , x - i }, {x - i , r i }, hence inducing a P 4 . We call the vertex x + i (resp. x - i ) a positive (resp. a negative) vertex of G. For each clause C j of φ, j ∈ [m], we add to G a vertex c j , which we connect to the positive or negative vertices corresponding to the literals contained in C j . This concludes the construction of G, which is illustrated in Figure 2(a). Note that, since φ is a monotone formula, G is a bipartite graph. Note also that the set of vertices {x

+ i , x - i | i ∈ [n]
} is a minimum vertex cover of G of size 2n, and that the set of edges {{

i , x + i }, {x - i , r i } | i ∈ [n]
} is a maximum matching of G of size 2n. We claim that φ is satisfiable if and only if G contains a minimal vertex cover of size k := 2n + m. Suppose first that φ is satisfiable, and let σ be an assignment of the variables that satisfies all the clauses in φ. We proceed to define a minimal vertex cover X of G of size k. First, add to X all the clause vertices {c j | j ∈ [m]}. For every i ∈ [n], if σ(x i ) = true (resp. σ(x i ) = false), add to X vertices x - i and i (resp. x + i and r i ). See Figure 2(b) for an illustration, where the set X is shown with larger red vertices. Clearly, X is a vertex cover of G. To see that it is minimal, by Observation 1 it is enough to verify that, for every vertex v ∈ X, N [v] X. This condition holds easily for all vertices in X that are in the P 4 's, since for each P 4 its vertices in X are not adjacent. Let c j be a clause vertex. Since σ is a satisfying assignment of the variables, there exists a variable x i such that if σ(x i ) = true (resp. σ(x i ) = false) then x i ∈ C j (resp. xi ∈ C j ). By definition of X, if σ(x i ) = true (resp. σ(x i ) = false) then x + i / ∈ X (resp. x - i / ∈ X), and by construction of G we have that x + i ∈ N (c j ) (resp. x - i ∈ N (c j )), so in both cases N [c j ] X. Conversely, suppose that G contains a minimal vertex cover X of size k, and we proceed to define a variable assignment σ as follows. For i ∈ [n], as {x + i , x - i } ∈ E(G) we have that X contains one or two vertices in the set {x + i , x - i }. If x + i / ∈ X (resp. x - i / ∈ X) we set σ(x i ) = true (resp. σ(x i ) = false), and if both x + i and x - i belong to X we set σ(x i ) to true or to false arbitrarily. We claim that σ satisfies all the clauses in φ. For i ∈ [n], let P i be the P 4 of G induced by the vertices i , x + i , x - i , r i . Since X is a vertex cover, clearly |X ∩ V (P i )| ≥ 2. We claim that |X ∩V (P i )| = 2. Indeed, if |X ∩V (P i )| ≥ 3, then { i , x + i } ⊆ X or {x - i , r i } ⊆ X (or both). But then N [ i ] ⊆ X or N [r i ] ⊆ X (or both), contradicting Observation 1. Thus, |X ∩ V (P i )| = 2, which implies that |X ∩ i∈[n] V (P i )| = 2n, hence necessarily X contains the whole set {c j | j ∈ [m]} of clause vertices. Consider an arbitrary clause vertex c j . Since X is minimal and c j ∈ X, by Observation 1 there exists a neighbor of c j in G that is not in X, and by definition of σ it follows that the literal corresponding to that neighbor of c j satisfies clause C j . Thus, σ is a satisfying assignment and the proof is complete.

Finally, note that the above reduction is also an NP-completeness reduction from Monotone Sat to Maximum Minimal Vertex Cover on bipartite graphs.

Conclusions and further research

Motivated by the existence of subquadratic kernels for the Maximum Minimal Vertex Cover problem parameterized by the solution size, we introduced a general framework to rule out certain types of kernels, which we called lop-kernels, for optimization problems. This "lop" assumption does not seem to be very restrictive, as the vast majority of known kernels are in fact lop-kernels [START_REF] Fedor | Theory of Parameterized Preprocessing[END_REF]. For instance, the classical kernels for Vertex Cover, such as those using the high-degree rule, the crown decomposition rule, or the Nemhauser-Trotter rule [START_REF] Fedor | Theory of Parameterized Preprocessing[END_REF], are lop-kernels. More involved kernels, such as those based on protrusion replacement [START_REF] Hans | Meta) Kernelization[END_REF], are also lop-kernels. However, we discussed in Section 5 an example of a polynomial kernel for a vertex-minimization problem, namely Tree Deletion Set [START_REF] Archontia | Tree Deletion Set has a polynomial kernel but no OPT O(1) approximation[END_REF], which is not a lop-kernel. We still do not know of a similar example that is a vertex-maximization problem.

For several technical reasons, we think that the framework of lop-kernels seems to be more suited for maximization problems. In this direction, we showed that a direct application of our general result for vertex-maximization problems (Corollary 11) yields kernelization lower bounds for MMVC (Corollary 26) and MMFVS (Corollary 27), matching the sizes of the best known kernels for these problems. We also presented consequences of our results for the Maximum Independent Set problem restricted to K t -free graphs (Corollary 30) and conjectured (Conjecture 29) that, for every fixed graph H, the Maximum Independent Set problem restricted to H-free graphs admits a polynomial lop-kernel. For (vertex-)minimization problems, the only application that we were able to find concerns the Tree Deletion Set problem (Corollary 28).

We believe that our results could be applied to other vertex-maximization problems, in particular to the "max-min" version of other vertex-minimization problems, as they seem to be quite hard to approximate. It would be interesting to find other examples of vertexminimization problems, other than Tree Deletion Set, where our results could be applied.

Here, the natural candidates seem to be the "min-max" version of vertex-maximization problems, which seem to have been almost unexplored so far.

Our general results for maximization (Theorem 13) and minimization (Theorem 24) problems take into account an upper bound function u(n) = O(n a ) that upper-bounds the size of optimal solutions of the considered problems. All our applications presented in Section 5 correspond to vertex problems, that is, to the case a = 1. We leave for further research to find applications of our results for problems with superlinear upper bound functions, such as edge problems, for which a = 2.

Our results are also able to derive lower bounds on the multiplicative constants of the existing kernels (cf. for instance the second item of Corollary 11 and Corollary 22). We still do not have any relevant application of this type for a concrete problem. For instance, if we apply Corollary 22 to the Vertex Cover problem, relying on the non-existence of a (2 -ε)-approximation under the Unique Games Conjecture [START_REF] Khot | Vertex cover might be hard to approximate to within 2-ε[END_REF], we rule out the existence of a lop-kernel with (1 -ε)k vertices, which is not particularly interesting.

We presented (Section 7) subquadratic kernels for Maximum Minimal Vertex Cover on H-free graphs for some graphs H satisfying the (constructive) Erdős-Hajnal property, such as the bull, the complete graphs, or the paw. It would be interesting to obtain subquadratic kernels for other graphs H satisfying the Erdős-Hajnal property, such as C 4 , the diamond, P 5 , or C 5 . Note that, from [START_REF] Gyárfás | Reflections on a Problem of Erdős and Hajnal[END_REF], C 4 and the diamond satisfy the constructive Erdős-Hajnal property with constant δ ≥ 1/3. Note also that the graphs constructed in the reduction of Theorem 42 are {C 5 , diamond}-free, as they are bipartite, hence MMVC is NP-hard on this class, in contrast to the fact (Corollary 41) that MMVC can be solved in linear time on {P 5 , diamond}-free graphs. To the best of our knowledge, the complexity on P 5 -free graphs is open, as well as on K 1,t graphs for t ≥ 3 (see Lemma 38). It is worth mentioning that P 5 -free graphs have unbounded cliquewidth, because co-bipartite graphs, which are P 5 -free, have unbounded cliquewidth.

As defined in Section 2, for a graph G let mmvc(G) be the maximum size of a minimal vertex cover of G. Boria et al. [START_REF] Boria | On the max min vertex cover problem[END_REF] proved that if G is an n-vertex graph without isolated vertices, then mmvc(G) ≥ n 1/2 . Note that this immediately yields a quadratic kernel for MMVC: if k ≤ n 1/2 we answer "yes", otherwise n ≤ k 2 . By the same argument, if C is a graph class such that every n-vertex graph G ∈ C without isolated vertices satisfies mmvc(G) ≥ n 1/2+ε , for some ε > 0, then MMVC restricted to C admits a (subquadratic) kernel with at most k 2 1+2ε vertices. It might be possible that this is the case for some of the H-free graph classes for which we provided subquadratic kernels in Section 7: we were not able to find any counterexample, that is, a family of n-vertex H-free graphs G for which mmvc(G) = Θ(n 1/2 ). In particular, the case of triangle-free graphs seems particularly interesting. Haviland [START_REF] Haviland | Independent domination in triangle-free graphs[END_REF] and Goddard and Lyle [START_REF] Goddard | Independent dominating sets in triangle-free graphs[END_REF] established upper bounds on the size of a minimum independent dominating set (that is, the complement of a minimal vertex cover) of triangle-free graphs. It follows from their results [START_REF] Goddard | Independent dominating sets in triangle-free graphs[END_REF][START_REF] Haviland | Independent domination in triangle-free graphs[END_REF] that there exist n-vertex triangle-free graphs G with mmvc(G) = Θ(n 2/3 • log n), hence if such a constant ε > 0 as discussed above exists for triangle-free graphs, necessarily ε ≤ 2 3 -1 2 = 1 6 . Therefore, the smallest kernel that we may obtain in this way on triangle-free graphs would have k 2 1+2ε ≤ k 3/2 vertices, which matches the size of the kernel that we obtained in Theorem 34 for the particular case t = 3, disregarding lower-order terms and multiplicative constants. Finding such a constant ε > 0 on H-free graphs for small graphs H, in particular on triangle-free graphs, looks like a challenging problem, having interesting connections with the Ramsey numbers [START_REF] Goddard | Independent dominating sets in triangle-free graphs[END_REF][START_REF] Haviland | Independent domination in triangle-free graphs[END_REF].

  For every solution s of I there exists a solution s of I with val Π (I , s ) ≥ val Π (I, s) -(k -k ). (b) For every solution s of I with val Π (I, s) ≥ k, there exists a solution s of I with val Π (I , s ) ≥ val Π (I, s) -(k -k ). (c) If there exists a solution s of I with val Π (I, s) ≥ k, then there exists a solution s of I with val Π (I , s ) ≥ k .

  and s and u are polynomial-time computable. Suppose that Π has u as upper bound function and that it admits a lop-kernel of size s, according to the same size function | • | associated with Π. 1. If ac > 1, then Π admits a polynomial-time value-approximation algorithm with ratio O(n ac-1 c

Corollary 14 . 1 . 1 a-r ). 2 .

 14112 Let Π be a well-behaved maximization problem with a non-decreasing and polynomial-time computable upper bound function u(n) = O(n a ) for a ∈ R + . In what follows, the size of the instance, denoted by n, and the size of the kernel are defined according to the same size function | • | associated with Π. For every real number r ∈ (0, 1), if Π does not admit a polynomial-time value-approximation algorithm with ratio O(n r ), then Π parameterized by the solution size does not admit a lop-kernel of size O(k Suppose that u(n) ≤ αn a for some α ∈ R + . For every real number β > 1, if Π does not admit a polynomial-time value-approximation algorithm with ratio β, then Π parameterized by the solution size does not admit a lop-kernel of size β k c for any real numbers β , c such that ac ≤ 1 and αβ a 2 ac + 3 ≤ β. Moreover, if the non-existence of approximation algorithms only holds for constructive approximation algorithms, then the lower bound only holds for constructive lop-kernels.

  (a) For every solution s of I there exists a solution s of I with val Π (I, s) ≤ val Π (I , s ) + (k -k ). (b) For every solution s of I with val Π (I , s ) ≤ k , there exists a solution s of I with val Π (I, s) ≤ val Π (I , s ) + (k -k ). (c) If there exists a solution s of I with val Π (I , s ) ≤ k , then there exists a solution s of I with val Π (I, s) ≤ k.

1 .

 1 NP, c > 1 and β ≥ 1 be real numbers, and f : N → N be a computable function. If Π admits an f -dual-approximation algorithm where f (k) = O(k c ), then Π admits a polynomial-time value-approximation algorithm with ratio O(n c-1 c

  13, follows immediately by pipelining Lemma 19 and Lemma 23. Namely, starting with the hypothesis of Theorem 24, we first apply Lemma 19 and then Lemma 23 with d = ac and λ = αβ a . Theorem 24. Let Π be a well-behaved minimization problem, a, c ∈ R + , u : N → N, and s : N → N be functions such that u(n) = O(n a ), s(k) = O(k c ), u is non-decreasing, and s and u are polynomial-time computable. Suppose that Π has u as upper bound function and that it admits a lop-kernel of size s, according to the same size function | • | associated with Π.

Corollary 28 .

 28 Tree Deletion Set parameterized by the solution size does not admit a polynomial lop-kernel, unless P = NP.

2

 2

1 CNFigure 1 2 C

 112 Figure 1 Configuration considered in the proof of Claim 33 and a vertex z ∈ x∈S 2 C

  ) still hold, but now we have a much simpler version of Equation (3): if C ∈ C is a clique then, since G is K t -free, necessarily |C| ≤ t -1,which together with the fact that ∆(G) ≤ k -1 yield for every clique C ∈ C, it holds |N S (C)| = (t -1)(k -1).

  δ2 δ1+|V (H1)|•δ2 . The same applies to the constructive version of the Erdős-Hajnal property.

Theorem 37 .

 37 The Maximum Minimal Vertex Cover problem parameterized by k restricted to paw-free graphs admits a kernel with at most c(k -1) 5/3 + k -1 vertices, where c = 2 2 2/3 -1 < 3.41. Proof. Given an instance (G, k) of Maximum Minimal Vertex Cover, where G is a paw-free graph, we again partition V (G) = X S, where X is a minimal vertex cover of G with |X| ≤ k -1, and we use Lemma 31 to partition X into two collections C and I of cliques and independent sets, respectively, with |C| + |I| ≤ d • |X| 2/3 , where d = 1 2 2/3 -1 . Equations (1) and (2) still hold, and we can again obtain in a simpler way an appropriate version of Equation (3). Indeed, let C ∈ C be a clique, and our goal is to bound |N S (C)|. If |C| = 1 then by the fact that ∆(G) ≤ k -1 we get that |N S (C)| ≤ k -1, so assume that |C| ≥ 2. Suppose for the sake of contradiction that there exists a vertex v ∈ N S (C) such that |N C (v)| ≤ |C| -2. Let w ∈ N C (v) and let z 1 , z 2 be two vertices in C \ N C (v). Then the vertices v, w, z 1 , z 2 induce a paw, contradicting the hypothesis that G is paw-free. Therefore, for every vertex v ∈ N S (C) it holds that |N C (v)| ≥ |C| -1. Hence, the number of edges in G between C and N S (C) is at least |N S (C)| • (|C| -1) and, since ∆(G) ≤ k -1, at most |C| • (k -1). Using that |C| ≥ 2, it follows that for every clique C ∈ C, it holds |N S (C)| ≤ |C| |C| -1 • (k -1) ≤ 2(k -1).

Figure 2

 2 Figure 2 (a) Illustration of the graph G built from the formula φ in the proof of Theorem 42. (b) A minimal vertex cover X of G is shown with larger red vertices.

  proved that if two graphs H 1 and H 2 satisfy Erdős-Hajnal property and H is obtained from H 1 by substituting H 2 , then H satisfies the Erdős-Hajnal property as well. More precisely, by following the details in the proof of [3, Theorem 2.1], we can derive that if H 1 and H 2 satisfy Erdős-Hajnal property with constants δ 1 and δ 2 , respectively, then H satisfies the Erdős-Hajnal property with constant δ =

  2-δt + k -1 vertices, where δ 3 = 1 4 and δ t = 4 t+17 for t ≥ 4, and c t = As in the proof of Theorem 32, given an instance (G, k) of Maximum Minimal Vertex Cover, where G is a t-bull-free graph, we partition V (G) = X S, where X is a minimal vertex cover of G with |X| ≤ k -1, and we use Lemma 31 to partition X into two collections C and I of cliques and independent sets, respectively, with |C| + |I| ≤ d t • |X| 1-δt , where δ 3 = 1 4 and δ t = 4 t+17 for t ≥ 4, and d t = 1 2 (1-δ t ) -1 for every t ≥ 3. Equations (1) and (2) still hold for every integer t ≥ 3, but now we need slightly more involved arguments to obtain an appropriate version of Equation (3) for every t ≥ 3.To this end, suppose that C ∈ C is a clique. We partition N S (C) = S 1 S (C) such that the neighborhoods of its vertices pairwise leave at least t -2 uncovered vertices in the clique C. We let S 2 C = N S (C) \ S 1 C . The set S 1 C satisfies exactly the same crucial property as for the case t = 3 (seeClaim 33). For every integer t ≥ 3, the vertices in S1 C can be ordered x 1 , . . . , x p so that N C (x i ) ⊆ N C (x j ) whenever i ≤ j.Proof. In order to prove the claim, it is sufficient to prove that, for any two vertices x, y ∈ S 1 C , either N C (x) ⊆ N C (y) or N C (y) ⊆ N C (x). Suppose for the sake of contradiction that there exist two vertices u∈ N C (x) \ N C (y) and w ∈ N C (y) \ N C (x). By definition of the set S 1 C , there exist t -2 vertices w 1 , . . . , w t-2 ∈ C \ (N C (x) ∪ N C (y)). But then the vertices x, y, u, v, w 1 , . . . , w t-2 induce a t-bull, contradicting the hypothesis that G is t-bull-free.Claim 36 implies in particular that, unlessS 1 C = ∅, there exists a vertex u ∈ x∈S 1 C N C (x). Since u has degree at most k -1 in G, and each vertex x ∈ S 1 C is adjacent to u, it follows that |S 1 C | ≤ k -1.Let us now focus on the set S 2C . The definition of the set S 1 C together with Claim 36 imply that there exist at least t -2 vertices z 1 , . . . , z t-2 ∈ C \ y∈S 1

	t-1 2 (1-δ t ) -1 . C be an inclusion-wise maximal set of vertices in N S (C) such that for any two (not S 2 C as follows. Let S 1 necessarily distinct) vertices x, y ∈ S 1 C , |N C (x) ∪ N C (y)| ≤ |C| -(t -2). That is, S 1 C is a Proof. C N C (y). Consider now maximal set in N Claim 36. C an arbitrary vertex x ∈ S 2 C . Since x could not be added to S 1 C , there exists a vertex y ∈ S 1

C such that |N C (x) ∪ N C (y)| ≥ |C| -(t -1). But since z 1 , . . . , z t-2 ∈ C \ y∈S 1 C

This definition was used in the conference version of this paper[START_REF] Araújo | A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover[END_REF].

Acknowledgement. We would like to thank Michael Lampis (resp. Magnus Wahlström, Venkatesh Raman) for pointing us to reference [31] (resp. reference [38], references [9,49]).

, CAPES-PrInt 88887.466468/2019-00 and CAPES-STIC-AmSud 88881.569474/2020-01. Victor Campos: FUNCAP -PNE-011200061.01.00/16. Ignasi Sau: DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), ELIT (ANR-20-CE48-0008-01), and French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).

Corollary 22. Let Π be a vertex-minimization problem whose decision version is in NP.

1. For every real number r ∈ (0, 1), if Π does not admit a polynomial-time value-approximation algorithm with ratio O(n r ) on n-vertex graphs, then Π parameterized by the solution size does not admit a lop-kernel with O(k 1 1-r ) vertices.

2.

For every real number β > 1, if Π does not admit a polynomial-time value-approximation algorithm with ratio β, then Π parameterized by the solution size does not admit a lop-kernel with (β -1 -ε)k vertices for any real number ε > 0. Moreover, if the non-existence of approximation algorithms only holds for constructive approximation algorithms, then the lower bound only holds for constructive lop-kernels.

Connection between lop-kernels and approximation algorithms for well-behaved minimization problems

The following lemma and theorem are a more general version of Lemma 20 and Theorem 21, respectively, for well-behaved minimization problems. The next lemma should be compared to Lemma 12, and note that the obtained approximation ratios in the second item of both lemmas are different.

Lemma 23.

Let Π be a well-behaved minimization problem, a ∈ R + , u : N → N, and f : N → N be functions such that u(n) = O(n a ), u is polynomial-time computable, and f is computable. Suppose that Π has u as upper bound function u and that it admits an f -dual-approximation. ), where n is the size of the input.

2.

If f (k) = λk d +k for some real numbers d ≤ 1 and λ > 0, then Π admits a polynomial-time value-approximation algorithm with ratio λ + 1.

Moreover, if the dual-approximation algorithm is constructive, then the corresponding approximation algorithm is also constructive.

Proof. Let A be an f -dual-approximation algorithm for Π. For both cases in the statement of the lemma, we proceed to construct a polynomial-time approximation algorithm for Π with the claimed ratio.

Given an instance I of Π, we find k 0 ∈ {0, . . . , u(n)} (recall that n = |I|) defined as the smallest positive integer k such that algorithm A returns that opt Π (G) ≤ f (k). Note that k 0 can be found in polynomial time, as |I| is polynomial-time computable and its value n is polynomially upper-bounded in the classical bit-size of the instance, and that u(n) can be computed in polynomial time as well. Note that k 0 always exists, as we cannot have opt Π (I) > u(n). If k 0 = 0, then as by hypothesis Π satisfies property C min , we can verify in polynomial time whether opt Π (I) = 0 and, if it is the case, we provide an optimal solution s with val Π (I, s) = 0. Otherwise, we have opt Π (I) ≥ 1, and A returns f (k 0 ), or a solution s such that val Π (I, s) ≤ f (k 0 ) if the dual-approximation algorithm is constructive. In the first case (that is, if f (k) = O(k d )), as opt Π (I) ≥ 1, we have a ratio f (0), implying the claimed ratio. In the second case (that is, if f (k) = λk d + k), f (0) = 0, so we even have an optimal solution.

Let us now assume that k 0 ≥ 1, and recall that opt Π (I) ≥ k 0 . We distinguish the two cases claimed in the statement of the lemma.