{'fraction_non_alphanumeric': 0.05223372753857755, 'fraction_numerical': 0.008589137591730887, 'mean_word_length': 3.8459893048128344, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Search-Space Reduction via Essential Vertices

We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, our focus is on finding a non-empty vertex set that belongs to an optimal solution. This decreases the size of the remaining part of the solution which still has to be found, and therefore shrinks the search space of fixed-parameter tractable algorithms for parameterizations based on the solution size. We introduce the notion of a c-essential vertex as one that is contained in all c-approximate solutions. For several classic combinatorial problems such as Odd Cycle Transversal and Directed Feedback Vertex Set, we show that under mild conditions a polynomial-time preprocessing algorithm can find a subset of an optimal solution that contains all 2-essential vertices, by exploiting packing/covering duality. This leads to FPT algorithms to solve these problems where the exponential term in the running time depends only on the number of non-essential vertices in the solution.


Introduction
Background and motivation Due to the enormous potential of preprocessing to speed up the algorithmic solution to combinatorial problems [1,2,3,46,47], a large body of work in theoretical computer science is devoted to understanding its power and limitations. Using the notion of kernelization [6,21,23,27,36,32] from parameterized complexity [13,16] it is possible to formulate a guarantee on the size of the instance after preprocessing based on the parameter of the original instance. Under this model, a good preprocessing algorithm is a kernelization algorithm: given a parameterized instance (x, k), it outputs an equivalent instance (x , k ) of the same decision problem such that |x | + k ≤ f (k) for some function f that bounds the size of the kernel. Research into kernelization led to deep algorithmic insights, including connections to protrusions and finite-state properties [7], well-quasi ordering [24], and matroids [33]; these positive results were complemented by impossibility results [14,17,33] delineating the boundaries of tractability. Results on kernelization led to profound insights into the limitations of polynomial-time data compression for NP-hard problems. However, as recently advocated [15], the definition of kernelization only gives guarantees on the size of the instance after preprocessing, which does not directly correspond to the running time of subsequently applied algorithms. If the preprocessed instance is not solved by brute force, but via a fixed-parameter tractable algorithm whose running time is of the form f (k) · n O(1) , then the exponential dependence in the running time is on the value of the parameter k, which is not guaranteed to decrease via kernelization. In fact, if P = N P then no polynomial-time preprocessing algorithm can guarantee to always decrease the parameter of an NP-hard fixed-parameter tractable problem, as iterating the preprocessing algorithm would lead to its solution in polynomial time. In this work, we develop a new analysis of preprocessing aimed at reducing the search space of the follow-up algorithm. We apply this framework to combinatorial optimization problems on graphs, whose goal is to find a minimum vertex-subset satisfying certain properties. The main idea behind the framework is to define formally what it means for a vertex to be essential for making reasonable solutions to the problem, and to prove that an efficient preprocessing algorithm can detect a subset of an optimal solution that contains all such essential vertices.
Before stating our results, we introduce and motivate the model. We consider vertexsubset minimization problems on (possibly directed) graphs, in which the goal is to find a minimum vertex subset having a certain property. Examples of the problems we study include Vertex Cover, Odd Cycle Transversal, and Dominating Set. The analysis of such minimization problems, parameterized by the size of the solution, has played an important role in the literature (cf. [10,18,29,41,43]). Our starting point is the thesis that a good preprocessing algorithm should reduce the search space. Since many graph problems are known to be fixed-parameter tractable when parameterized by the size of the solution, we can reduce the search space of these FPT algorithms by finding one or more vertices which are part of an optimal solution, thereby decreasing the size of the solution still to be found in the reduced instance (i.e. the parameter value).
Since in general no polynomial-time algorithm can guarantee to identify at least one vertex that belongs to an optimal solution, the guarantee of the effectiveness of the preprocessing algorithm should be stated in a more subtle way. When solving problems by hand, one sometimes finds that certain vertices v are easily identified to belong to an optimal solution, as avoiding them would force the solution to contain a prohibitively large number of alternative vertices and therefore be suboptimal. Can an efficient preprocessing algorithm identify those vertices that cannot be avoided when making an optimal solution? Since many NP-hard problems remain hard even when there is a unique solution [45], this turns out to be too much to ask as it would allow instances with unique solutions to be solved in polynomial time, which leads to N P = RP . We therefore have to relax the requirements on the preprocessing guarantee slightly, as follows. For an instance of a vertex-subset minimization problem Π on a graph G, we denote the minimum size of a solution on G by OPT Π (G). For a fixed c ∈ R ≥1 , we say a vertex v ∈ V (G) is c-essential for Π on G if all feasible solutions S ⊆ V (G) for Π whose total size is at most c · OPT Π (G) contain v. Based on this notion, we can ask ourselves: can an efficient preprocessing algorithm identify part of an optimal solution if there is at least one c-essential vertex?
Phrased in this way, the algorithmic task becomes more tractable. For example, for the Vertex Cover problem, selecting all vertices that receive the value 1 in an optimal half-integral solution to the LP-relaxation results in a set S which is contained in some optimal solution (by the Nemhauser-Trotter theorem [40], cf [13, §2.5]), and at the same time includes all 2-essential vertices: any vertex v / ∈ S only has neighbors of value 1 2 and 1, which implies that the set X of vertices other than v whose value in the LP relaxation is at least 1 2 , forms a feasible solution which avoids v. Its cardinality is at most twice the cost of the LP relaxation and therefore X is a 2-approximation. Hence S contains all 2-essential vertices.
This example shows that a preprocessing step that detects c-essential vertices without any additional information is sometimes possible. However, to be able to extend the scope of our results also to problems which do not have polynomial-time constant-factor approximations, we slightly relax the requirements on the preprocessing algorithm as follows. Let Π be a minimization problem on graphs whose solutions are vertex subsets and let c ∈ R ≥1 . c-Essential detection for Π Input: A graph G and integer k. Task: Find a vertex set S ⊆ V (G) such that: then there is an optimal solution in G containing all of S, and G2 if OPT Π (G) = k, then S contains all c-essential vertices.
In this model, the preprocessing task is facilitated by supplying an additional integer k in the input. The correctness properties of the output S are formulated in terms of k. If OPT Π (G) ≤ k, then the set S is required to be part of an optimal solution. The upper bound on OPT Π (G) is useful to the algorithm: whenever the algorithm establishes that avoiding v would incur a cost of more than k, it is safe to add v to S. If OPT Π (G) = k, then the algorithm should guarantee that S contains all c-essential vertices. Knowing a lower bound on OPT Π (G) is useful to the algorithm in case it can establish that any optimal solution containing v can be transformed into one avoiding v whose cost is (c − 1) · k larger, which yields a c-approximation if (c − 1) · k ≤ (c − 1) OPT Π (G). Hence vertices for which such a replacement exists are not c-essential and may safely be left out of S.

Results
We present polynomial-time algorithms for c-Essential detection for Π for a range of vertex-deletion problems Π and small values of c; typically c ∈ {2, 3}. Example applications include Vertex Cover and Feedback Vertex Set, and also Chordal Vertex Deletion (for which no O(1)-approximation is known), Odd Cycle Transversal (for which no O(1)-approximation exists, assuming the Unique Games Conjecture [31,48]), and even Directed Odd Cycle Transversal (which is W [1]-hard parameterized by solution size [38]).
The model of c-Essential detection for Π is chosen such that the detection algorithms whose correctness is formulated with respect to the value of k, can be used as a preprocessing step to optimally solve vertex-subset problems without any knowledge of the optimum. Let E Π c (G) denote the set of c-essential vertices in G, which is well-defined since all optimal solutions contain all c-essential vertices. By using a preprocessing step that detects a superset of the c-essential vertices in the solution, we can effectively improve the running-time guarantee for FPT algorithms parameterized by solution size from f (OPT Π (G)) · |V (G) 1) . This leads to the following results.
| is the number of vertices in an optimal solution which are not c-essential.
Hence the running time for solving these problems does not depend on the total size of an optimal solution, only on the part of the solution that does not consist of c-essential vertices. The theorem effectively shows that by employing c-Essential detection for Π as a preprocessing step, the size of the search space no longer depends on the total solution size but only on its non-essential vertices.
We also prove limitations to this approach. Assuming FPT = W [1], for Dominating Set, Perfect Deletion (in which the goal is to obtain a perfect graph by vertex deletions) and Wheel-Free Deletion, there is no polynomial-time algorithm for c-Essential detection for any c ∈ R ≥1 . In fact, we can even rule out such algorithms running in time f (k)·|V (G)| O(1) . Table 1 For each problem Π, there is a polynomial-time algorithm for c-Essential detection for the stated value of c. Combined with the state of the art algorithm for the natural parameterization, this leads to an algorithm solving the problem in time  [9] These results are based on FPT-inapproximability results for Dominating Set [43] and existing reductions [28,35] to the mentioned vertex-deletion problems.

Techniques
The main work lies in the algorithms for c-Essential detection, which are all based on covering/packing duality for forbidden induced subgraphs to certain graph classes, or variations thereof in terms of (integer) solutions to certain linear programs and their (integer) duals. To understand the relation between detecting essential vertices and covering/packing duality, consider the Odd Cycle Transversal problem (OCT). Following the argumentation for the classic Erdős-Pósa theorem [19], in general there is no constant c such that any graph either has an odd cycle transversal of size c · k, or a packing of k vertex-disjoint odd cycles. However, we show that a linear packing/covering relation holds in the following slightly different setting. If G − v is bipartite (so all odd cycles of G intersect v), then the minimum size of an OCT avoiding v equals the maximum cardinality of a packing of odd cycles which pairwise intersect only at v. We can leverage this statement to prove that any vertex v which is not at the center of a flower (see Definition 3.1) of more than OPT oct (G) odd cycles, is not 2-essential: for any optimal solution X containing v, the graph G := G − (X \ {v}) becomes bipartite after removal of v and by assumption does not contain a packing of more than OPT oct (G) odd cycles pairwise intersecting at v. So by covering/packing duality on G , it has an OCT X of size at most OPT oct (G) avoiding v, so that (X \ {v}) ∪ X is a 2-approximation in G which avoids v, showing that v is not 2-essential. Since v is clearly contained in an optimal solution whenever there is a flower of more than OPT oct (G) odd cycles centered at v, this yields a method for c-Essential detection when using a known reduction [25] to Maximum Matching to test for a flower of odd cycles.
Organization After presenting preliminaries in Section 2, we give algorithms to detect essential vertices based on covering/packing duality in Section 3 and based on integrality gaps in Section 4. In Section 5 we show how these detection subroutines can be used to improve the parameter dependence of FPT algorithms parameterized by solution size. The lower bounds are presented in Section 6. The investigation of c-essential vertices has close connections to the area of perturbation stability, which we briefly explore in Section 7. We conclude in Section 8.

Preliminaries
We consider finite simple graphs, some of which are directed. We use standard notation for graph algorithms; any terms not defined here can be found in the textbook by Cygan et al. [13]. We consider vertex-deletion problems on graphs. For a graph class C, a C-modulator in a graph G is a vertex set S ⊆ V (G) such that G − S ∈ C. The minimum size of a C-modulator in G is denoted OPT C (G). The corresponding minimization problem is defined as follows.

C-Deletion
Input: A graph G. Task: Find a minimum-size vertex-subset S ⊆ V (G) such that G − S ∈ C.
Throughout this paper we consider hereditary graph classes C. These can be characterized by a (possibly infinite) set of forbidden induced subgraphs denoted forb(C). The C-Deletion problem is equivalent to finding a minimum set S ⊆ V (G) such that no induced subgraph of G − S is isomorphic to a graph in forb(C). We say that such a set S hits all graphs from forb(C) in G. For these classes the vertex set V (G) is a trivial C-modulator (since the empty graph is in all hereditary classes), which ensures that the task of finding a smallest modulator is always well-defined.
A graph is perfect if for every induced subgraph the size of a largest clique is equivalent to its chromatic number. Equivalently, a graph is perfect if it has no induced cycle of odd length at least five or its edge complement (cf. [26]). A graph is chordal if it has no induced cycle of length at least four. A graph is bipartite if its vertex set can be partitioned into two independent sets, or equivalently, it does not contain an odd-length cycle. Given a graph G and a set T ⊆ V (G), a T -path is a path with at least one edge with both endpoints contained in T . A T -path is odd if it has an odd number of edges. For u, v ∈ V (G), a (u, v)-separator is a set S ⊆ V (G) \ {u, v} that disconnects u from v. If G is a directed graph, then in G − S there is no directed path from u to v instead.

Positive results via Packing Covering
In this section we provide polynomial-time algorithms for c-Essential detection for Π for various problems Π. The case for the Vertex Cover problem was given in Section 1.
The results in this section are all based on packing/covering duality (cf. [12], [44, §73]). Towards this end, we generalize the notion of flowers, which played a key role in kernelization for Feedback Vertex Set [8]. While flowers were originally formulated as systems of cycles (forbidden structures for Feedback Vertex Set) pairwise intersecting in a single common vertex, we generalize the notion to near-packings of arbitrary structures here.
We show a general theorem for finding 2-essential vertices for C-deletion if a maximum (v,forb(C))-flower can be computed in polynomial-time. It applies to those classes C where graphs with G − v ∈ C obey a min-max relation between C-modulators avoiding v and packings of forbidden induced subgraphs intersecting only at v.

Theorem 3.2. Let C be a hereditary graph class such that, for any graph G and ver-
Then there is a polynomial-time algorithm that solves 2-Essential detection for C-Deletion.
Proof. Apply algorithm A to each vertex v ∈ V (G) and let S be the set of vertices for which it finds that Γ forb(C) (G, v) > k. We argue that Properties G1 and G2 are satisfied. If OPT C (G) ≤ k, then every vertex in S is contained in every optimal solution for G since a size-k solution cannot hit a flower of k + 1 petals from forb(C) without using v. Therefore Property G1 is satisfied. Next suppose that OPT C (G) = k and let X be an optimal solution. We argue that each vertex v / ∈ S is not 2-essential. Clearly this holds for any vertex v / ∈ X, so suppose that v ∈ X. Note that for every vertex v / Observe that (X \ {v}) ∪ X is a C-modulator in G of size at most 2k that avoids v and therefore v is not 2-essential.
is the largest integer k such that the outcome of Gallai's theorem applied with the integer k − 1 is a family of k pairwise vertex-disjoint T -paths in G − v. For the first precondition of Theorem 3.2, we argue that when G − v is acyclic, the maximum number of petals in a (v,forb(C))-flower is equivalent to the minimum cardinality of a set S that hits all cycles through v. By noting that any cycle through v in G corresponds to a path between two neighbors in a connected component of G − v which is a tree, the claim above directly implies the desired result. It follows there is a polynomial-time algorithm for 2-Essential detection for FVS by Theorem 3.2.
The DFVS problem corresponds to C-Deletion where C is the set of directed acyclic graphs and forb(C) is the set of directed cycles. The preconditions of Theorem 3.2 follow from known results, see for instance the work of Fleischer et al. [22], we repeat it for completeness. Consider any directed graph D and vertex v ∈ V (D). Obtain a graph D by splitting v into v i and v o . Attach every incoming arc of v to v i and every outgoing arc By Menger's theorem, its size is equivalent to the maximum number of internally vertex-disjoint paths from v i to v o . Since Note that then S is a C-modulator avoiding v of size Γ forb(C) (D, v). By Theorem 3.2 it follows that there is a polynomial-time algorithm for 2-Essential detection for DFVS.

Odd cycle transversal
Next, we consider Odd Cycle Transversal (OCT), which corresponds to C-Deletion where C is the class of bipartite graphs and forb(C) is consists of all odd cycles. In order to apply Theorem 3.2 to OCT, we first argue that the class of bipartite graphs satisfies the preconditions. The proof is similar to that of Geelen et al. [25,Lemma 11] who reduce the problem of packing odd cycles containing v to a matching problem. We note that, although their result can be used to obtain a 3-essential detection algorithm, we will show (Lemma 3.8) how to efficiently detect 2-essential vertices as well. If the graph resulting from their construction has a large matching, then there is a large (v,forb(C))-flower. If on the other hand there is no large matching, then the Tutte-Berge formula is used to obtain a set of size 2k that hits all the odd cycles passing through v. We show that if the graph G − v is bipartite instead, then this second argument can be improved to obtain a hitting set of size k by noting that the lack of a large matching implies that there is a small vertex cover due to Kőnig's theorem. This is below, using the viewpoint that odd cycles in G correspond

Lemma 3.5. For any undirected graph G and set T ⊆ V (G), a maximum packing of odd T -paths can be computed in polynomial time. Moreover, if G is bipartite then the cardinality of a maximum packing of odd T -paths is equal to the minimum size of a vertex set which intersects all odd T -paths.
Proof. We reduce to matching as in [25,Lemma 11]. Construct a graph H as follows. For Note that the graph H consists of the disjoint union of G and a copy of G − T , with an added edge between v ∈ V (G) \ T and its copy v . Geelen et al. [25] mention that there is a 1-1 correspondence between odd T -paths in G and certain augmenting paths in H. For completeness we give a self-contained argument.
is an odd T -path and we can update P accordingly. Construct a matching M in H as follows. For alternating between original vertices and copy vertices. This is possible as P is of odd length. For any vertex in u ∈ V (G) \ T that is not contained in an odd T -path, we add uu to M . Observe that at least 2|V (G) \ T | + 2k vertices are matched, therefore |M | ≥ |V (G) \ T | + k as desired.
(⇐) Let M be a matching of size |V (G) \ T | + k. If M contains both uv and u v for u, v ∈ V (G) \ T , then update M by removing them and inserting uu and vv instead. If for v ∈ V (G) \ T only one of v and v is matched, and it is not matched to its copy, then match it to its copy instead. Afterwards let E : , add vv to M if it is not in already. Note that all vertices of H − T are matched. It follows that at least 2k vertices in T are matched by M and they have degree 1 in G [E ]. Observe that G[E ] is a collection of paths and cycles with all degree-1 vertices in T . We get that there are k T -paths in G that are of odd length by construction (every even numbered edge in G[E ] originated from the copy part of H). Note that we can find them in polynomial time.
Since a maximum matching can be computed in polynomial time, by the claim above we get that a maximum packing of vertex-disjoint odd T -paths can be computed in polynomial time. Next we prove the second part of the statement.
Proof. Observe that since G is bipartite, the graph H is bipartite as well. By Kőnig's theorem [44,Theorem 16 Note that for each u ∈ V (G) \ T , at least one of u ∈ X or u ∈ X must hold to cover the edge uu , thereby already accounting for |V (G) \ T | vertices of the cover. It follows that |S| ≤ k. We argue that S hits all odd-length T -paths in G.
For the sake of contradiction suppose there is some odd . By construction of S, the vertex cover X has exactly one of v i and v i for each i ∈ [2 ]. Observe that for it to be a vertex cover, X must contain vertices of P \ {t 1 , t 2 } and their copies in an alternating fashion since for each But this contradicts that X is a vertex cover as v 2 t 2 is not covered. We conclude that S hits all odd-length T -paths in G.
By Claim 3.6, a maximum packing of k of vertex-disjoint odd T -paths in G implies a matching in H of size |V (G) \ T | + k. By Claim 3.7, we can create a set of size at most k that intersects all odd T -paths in the bipartite graph G. Clearly such a set has size at least k. It follows that if G is bipartite, then the cardinality of a maximum packing of odd T -paths is equal to the minimum size of a vertex set which intersects all odd T -paths. (For completeness, we remark that this last property can also be derived from Menger's theorem: in a bipartite graph with bipartition into A ∪ B, a T -path is odd if and only if its endpoints belong to different partite sets, so a maximum packing of odd T -paths is equivalent to a maximum set of vertex-disjoint paths between A ∩ T and B ∩ T .) By observing that odd T -paths in G − v directly correspond to flowers with odd cycles pairwise intersecting at v in G, Lemma 3.5 and Theorem 3.2 imply the following.

Directed odd cycle transversal
The DOCT problem corresponds to C-deletion where forb(C) consists of all directed cycles of odd length. Using Menger's theorem on an auxiliary graph, we can detect 3-essential vertices for this problem. First, suppose that Proof. Each (v , v )-path P i in D corresponds to a directed odd walk P i in D, which contains a directed odd cycle. To see the second point, note that the paths in D are vertex-disjoint and since we created two copies of each vertex, it follows that each vertex of V (D) \ {v} intersects at most two vertex sets of P.
By the claim above, any solution to DOCT avoiding v ∈ Q has size at least k + 1. It follows that each vertex in Q belongs to every optimal solution and therefore Property G1 is satisfied. Next, suppose that OPT DOCT (G) = k. We argue that Q contains all 3-essential vertices. Consider an optimal solution X a vertex v / ∈ Q. If v / ∈ X, then clearly v is not 3-essential and there is nothing to show, so suppose that Since any odd cycle containing v corresponds to a (v , v )-path in D , and since S v is a (v , v )-separator in D , it follows that (X \ {v}) ∪ X is a solution of size at most k − 1 + 2k + 1 = 3k that avoids v. It follows that v is not 3-essential, therefore Q contains all 3-essential vertices and Property G2 is satisfied.
We cannot use the approach based on computing a maximum (v, F)-flower for the Chordal Deletion problem; a simple reduction 1 from Disjoint Paths [42] shows that it is NP-hard to compute a maximum (v, F)-flower when F is the set of chordless cycles of length at least four. In the next section, we will therefore use an approach based on the linear-programming relaxation to deal with Chordal Deletion.

Positive results via Linear Programming
Consider the following natural linear program for C-Deletion for hereditary graph classes C.
The LP corresponding to an input graph G is defined on the variables (x u ) u∈V (G) , as follows.

C-Deletion LP
Objective: minimize u∈V (G) x u . Subject to: In the corresponding integer program, the constraint 0 ≤ x u ≤ 1 is replaced by x u ∈ {0, 1}. We say that a minimization LP has integrality gap at most c for some c ∈ R if the cost of an integer optimum is at most c times the cost of a fractional optimum. In general, the number of constraints in the C-Deletion LP can be exponential in the size of the graph. Using the ellipsoid method (cf. [44]), this can be handled using a separation oracle: a polynomial-time algorithm that, given an assignment to the variables, outputs a violated constraint if one exists. It is well-known (cf. [44,Thm. 5.10]) that linear programs with an exponential number of constraints can be solved in polynomial time using a polynomial-time separation oracle. To detect essential vertices, the integrality gap of a slightly extended LP will be crucial. We define the v-Avoiding C-Deletion LP for a graph G and distinguished vertex v ∈ V (G) as the C-Deletion LP with the additional constraint that x v = 0. Hence its integral solutions correspond to C-modulators avoiding v. Proof. Given G and k, the detection algorithm initializes an empty vertex set S and proceeds as follows. For each v ∈ V (G), it solves the v-Avoiding C-Deletion LP on G in polynomial time using the ellipsoid method via the polynomial-time separation oracle. If the linear program has cost more than k, we add v to S. After having considered all vertices v ∈ V (G), the resulting set S is given as the output.
To see that the output satisfies Property G1, assume that OPT C (G) ≤ k and consider some optimal C-modulator X of size at most k. If v / ∈ X then X induces an integer feasible solution to the C-Deletion LP that satisfies the additional constraint x v = 0, so that the cost of the v-Avoiding C-Deletion LP is at most k and therefore v / ∈ S. By contraposition, all vertices of S are indeed contained in some minimum C-modulator, namely X.
To see that the algorithm also satisfies Property G2, assume OPT C (G) = k and let X be a minimum C-modulator of size k. We prove that S contains all (c + 1)-essential vertices. Consider an arbitrary v / ∈ S; we will argue it is not (c + 1)-essential by exhibiting a (c + 1)-approximate modulator avoiding v. Since v / ∈ S, the v-Avoiding C-Deletion LP has a (fractional) solution x = (x u ) u∈V (G) of cost at most k. If v / ∈ X then v was not (c + 1)-essential, and there is nothing to show. So assume v ∈ X.
Restricting the assignment x to the vertices of the graph G := G − (X \ {v}) yields a feasible solution x for the v-Avoiding C-Deletion LP on G , whose cost is at most that of x and therefore at most k. Note that G − v equals G − X and therefore belongs to C. So by the precondition to the theorem, the integrality gap for v-Avoiding C-Deletion on G is at most c. Hence the solution x can be rounded to an integral solution X on G of cost at most c · k and v / ∈ X due to the constraint x v = 0. Since G − ((X \ {v}) ∪ X ) = G − X ∈ C, it follows that (X \ {v}) ∪ X is a C-modulator of size at most c · k + k = (c + 1)k avoiding v, which is therefore a (c+1)-approximation. Hence v is not (c+1)-essential whenever v / ∈ S.
Using known results on covering versus packing for chordless cycles in near-chordal graphs, the approach above can be used to detect essential vertices for Chordal Deletion. For the class of chordal graphs, the corresponding set of forbidden induced subgraphs is the class hole of all holes, i.e., induced chordless cycles of length at least four. Using this covering/packing statement, we can bound the relevant integrality gap and thereby detect essential vertices for Chordal Deletion.

Lemma 4.3. There is a polynomial-time algorithm for 13-Essential detection for Chordal Deletion.
Proof. We first argue that the integrality gap for v-Avoiding Chordal Deletion is bounded by 12 when G−v is chordal. By Lemma 4.2, there is a value of p such that G contains both a (v, hole)-flower {C 1 , . . . , C p } with p-petals and a v-avoiding chordal modulator S of size at most 12p. Due to the constraint x v = 0, any fractional solution to the linear program has a cost of at least p, since u∈Ci x u ≥ 1 while x v = 0 and the holes only intersect at v. At the same time, an integral solution has cost at most 12p as S is such a solution. Hence the integrality gap is at most 12.
To invoke Theorem 4.1, it suffices to argue that there is a polynomial-time separation oracle for the linear program. Such a separation oracle is known (cf. [30, §10.1]); we repeat it here for completeness. To test whether an assignment x = (x u ) u∈V (G) satisfies all constraints, it suffices to do the following. For each u ∈ V (G) we find the minimum total weight of any hole involving u, as follows. For each pair of distinct non-adjacent p, q ∈ N G (u) we use Dijkstra's algorithm to find the minimum weight W of a path P from p to q in the graph G − (N G [u] \ {p, q}) where the values of x are used as the vertex weights. There is a hole of weight less than 1 through (p, u, q) if and only if W + x u < 1. Moreover, if W + x u < 1 then by extending path P with the vertex u we find a hole whose total weight is less than 1 and therefore a violated constraint. The fact that we remove all vertices of N G [u] other than p and q ensures that the cycle we get in this way is induced, while the non-adjacency of p and q ensures it has at least four vertices. Hence after iterating over all choices of u, p, q we either find a violated constraint or conclude that the assignment is feasible. This shows that Theorem 4.1 is applicable and concludes the proof.

Consequences for Parameterized Algorithms
In this section we show how the algorithms for c-Essential detection from the previous section can be used to solve C-Deletion for various classes C, despite the fact that the detection algorithms only work when certain guarantees on k are met. The main theorem connecting the detection problem to solving C-Deletion is the following.

Theorem 5.1. Let A be an algorithm that, given a graph G and an integer k, runs in time f (k) · |V (G)| O(1) for some non-decreasing function f and returns a minimum-size C-modulator if there is one of size at most k. Let B be a polynomial-time algorithm for c-Essential detection for C-Deletion. Then there is an algorithm that, given a graph G, outputs a minimum-size
Proof. First we describe the algorithm as follows. For each 0 ≤ k ≤ |V (G)|, let S k be the result of running B on (G, k), let G k := G − S k , and let b k := k − |S k |.
Letting L be the list of all triples (G k , S k , b k ) sorted in increasing order by their third component b k , proceed as follows. For each (G k , S k , b k ) ∈ L, run A on (G k , b k ) to find a minimum C-modulator S A of size at most b k , if one exists. If |S A | = b k , then output S A ∪ S k as a minimum C-modulator in G.
To analyze the algorithm, we first argue it always outputs a solution. For the call with k * = OPT C (G), both conditions of the detection problem are met. Hence by Property G1 the set S k * is contained in a minimum modulator in G, so that OPT C (G − S k * ) = OPT C (G) − |S k * | = k * − |S k * |. Therefore graph G k * = G − S k * has a modulator of size at most b k * = OPT C (G − S k * ) and none which are smaller, so that A correctly outputs a modulator of size b k * . In turn, this causes the overall algorithm to terminate with a solution.
Having established that the algorithm outputs a solution, we proceed to show that it outputs a minimum-size modulator whenever it outputs a solution (which may be in an earlier iteration than for k * = OPT C (G)). Let k be the value of k that is reached when the algorithm outputs a solution S A ∪ S k . Then we know: To see that the algorithm is correct, notice that, since OPT C (G) ≤ k , the set S k is contained in some minimum-size modulator for G (Property G1 of B).
is a feasible modulator of size OPT C (G) and therefore optimal. Now we prove the desired running-time bound. First of all, notice that we can determine the list L in polynomial time by running B once for each value of k (which is at most |V (G)|). By how we sorted L, we compute A(G k , b k ) only when b k ≤ b k * , as we argued above that if the algorithm has not already terminated, it does so after reaching k * = OPT C (G). Hence the calls to algorithm A are for values of the budget b k which satisfy b k ≤ b k * . We bound the latter, as follows.
Since k * = OPT C (G), the set S k * found by B is a superset of the set E c (G) of all of the c-essential vertices in G (Property G2). This means that we have  Table 1. Although the latter may be originally stated for the decision version, using self-reduction they can easily be adapted to output a minimum solution if there is one of size at most k.

Hardness results
Given the positive results we saw in Sections 3 and 4, it is natural to seek problems Π for which c-Essential detection for Π is intractable. Here we show that c-Essential detection for Dominating Set is intractable for any c ∈ O(1) and then use this as a starting point to prove similar results for Hitting Set, Perfect Deletion, and Wheel-free Deletion.
A dominating set is a vertex set whose closed neighborhood is the entire graph. The domination number of a graph is the size of a minimum dominating set. The starting point for our reductions is the following result which states that it is W [1]-hard to solve Dominating set parameterized by solution size even on instances which have 'solution-size gaps'.  (1) and distinguishes between the following two cases: Figure 1 Reducing R k of k−Dominating Set to c-Essential detection for Dominating Set. Each Gi is a copy of G and for j = i, Gi is a twin to Gj (denoted in the figure by squiggly lines: ∼) i.e. for each x ∈ V (G) and any two distinct copies xi and xj of x in Gi and Gj, xi is a true twin to xj. Each ai is an apex vertex to Gi (i.e. N (ai) = V (Gi)) and v * is an apex to the whole graph except a1, . . . , a k (i.e. N (v * ) = V (G0 G1 · · · G k )).
Completeness: G has a dominating set of size k. Soundness: Every dominating set of G is of size at least k · F (k).
All of our reductions in this section share a leitmotif. We start with a gap instance (G, k) of Dominating Set and map it to an instance G of c-Essential detection for Π (for appropriate Π) equipped with a distinguished vertex v * with the following property: (1) if G has domination number at most k, then no optimal solution in G contains v * ; (2) if G has domination number strictly greater than c · F (k) (for some appropriate F ), then v * is contained in every solution of size at most c · F (k) in G . Thus our hardness results will follow by combining reductions of this kind with Lemma 6.1.

Lemma 6.2. There is a polynomial-time algorithm R that, given a graph G and integer k, outputs a graph R(G, k) containing a distinguished vertex v * such that:
if G has dominating number at most k, then the domination number of R(G, k) is exactly k and every optimal dominating set avoids v * ; if G has domination number strictly greater than c · (k + 1) for some c ∈ R ≥1 , then R(G, k) has domination number k + 1 and the distinguished vertex v * is contained in all R(G, k)-dominating sets of size at most c · (k + 1).
Proof. The graph R(G, k) (see Figure 1) is defined formally as follows: For our notational convenience, notice that the graph R(G, k) contains k + 1 isomorphic copies of G denoted as G 0 , . . . , G k where each G i is defined as the induced subgraph Notice that R(G, k) has domination number at least k: since {a 1 , . . . , a k } is an independent set and the neighborhoods of each a i are disjoint in R(G, k), we have that any dominating set of R(G, k) is forced to pick at least one vertex from V (G i ) ∪ {a i } for each 1 ≤ i ≤ k. In particular, this means that every dominating set that contains v * must have cardinality at least k + 1 (since v * does not dominate a 1 , . . . , a k ). Now, to prove that R(G, k) has the desired properties, start by supposing that G has a dominating set {s 1 , . . . s } with at most k. We claim that, by 'spreading-out' this dominating set over G 1 , . . . , G (i.e. pick the copy of s i in G i for each i) we obtain a vertex-subset S of R(G, k) which dominates v *  , {a 1 , . . . , a } and every vertex of G 0 , . . . , G . The first two observations are immediate and the last follows since each G i is a 'twin' of G j in R(G, k): any vertex y in G is dominated by at least one vertex, s i of S and, by the construction of R (G, k), the copy of s i in G i dominates all of the copies y 0 , . . . , y of y in G 0 , . . . , G . It follows immediately from the definition of R(G, k) that S ∪ {a i : < i ≤ k} is a dominating set of R(G, k) of size k (which is smallest-possible by our previous arguments). Thus, by our previous discussion, all minimum-size dominating sets of R(G, k) avoid v * . Now suppose there exists a constant c ≥ 1 such that G has domination number greater than c · (k + 1). Take any dominating set S of R(G, k) not containing v * . Since G 0 is not adjacent to any one of the vertices a 1 , . . . , a k and v * ∈ S, every vertex of G 0 must be dominated by some vertex of G 0 · · · G k in R(G, k). Thus the obvious projection of S \{a 1 , . . . , a k , v * } onto G is a dominating set for G. Hence, if S avoids v * , then |S| > c·(k+1) by our assumption on the domination number of G. In other words, every dominating set of size at most c · (k + 1) must contain v * . This, combined with the fact that any dominating set of R(G, k) is forced to pick at least one vertex from V (G i ) ∪ {a i } for each 1 ≤ i ≤ k (as we observe earlier), implies that {v * , a 1 , . . . , a k } is a minimum-size dominating set of R(G, k) (where each a i dominates itself and v * dominates everything else) which has size k + 1. Lemma 6.1 combined with the reduction provided by Lemma 6.2 yields the following. Proof. Suppose such an algorithm A exists for c; we will use it with Lemma 6.1 to show FPT = W [1] for the function F (k) = c(k + 1).
Given an input (G, k) in which the goal is to distinguish between the completeness and soundness cases, the algorithm proceeds as follows. Using the reduction R of Lemma 6.2, consider the graph R(G, k) and let S be the output of an algorithm for c-Essential detection for Dominating Set on the pair (R(G, k), k + 1); note that the solution size for which we ask is k + 1 rather than k. Without loss of generality we may assume k ≥ 2, as the distinction can trivially be made otherwise. We will show that in the completeness case we have v * / ∈ S, while in the soundness case we have v * ∈ S, which allows us to distinguish between these cases by checking whether v * belongs to the output of A(R(G, k), k + 1).
For the completeness case, suppose G has domination number at most k. Then, by Lemma 6.2, so does R(G, k). This means that Property G1 holds for the call to A(R(G, k), k+ 1), so that there is some optimal solution S of size k which contains S and hence we have v * ∈ S by Lemma 6.2.
For the soundness case, suppose G has domination number at least k · F (k) = c(k + 1)k > c(k + 1) (we use k ≥ 2 here). Then by Lemma 6.2, graph R(G, k) has domination number k + 1 and v * is contained in all its dominating sets of size at most c(k + 1). In other words: v * is c-essential in R(G, k). Consequently, v * ∈ S by Property G2 since the argument k + 1 we supplied to A coincides with the optimum in R(G, k) in this case.
If A runs in FPT-time, then the overall procedure runs in FPT-time which implies FPT = W [1] by Lemma 6.1.
Consider the closed-neighborhood mapping S: i.e. the standard polynomial-time reduction from Dominating Set to Hitting Set which maps each graph G to the hypergraph The following observation captures the relation between dominating sets of G and hitting sets of S(G).

Observation 6.4. Let G be a graph and X ⊆ V (G). Then X is a dominating set of G if and only if X is a hitting set of S(G).
Note that, given the reduction R of Lemma 6.2, the composite mapping S • R relates c-essentiality to gaps in solution quality in much the same way as R did. Now consider the parameter-preserving polynomial-time parameterized reduction P (due to Heggernes et al.  (1) and (2)) to obtain a polynomial-time reduction from Dominating Set to the detection problem c-Essential detection for PerfDel with sufficient guarantees to be able to then infer the intractability of the latter problem using Lemma 6.1. Theorem 6.6. Unless FPT = W [1], there is no FPT-time algorithm for c-Essential detection for PerfDel parameterized by k for any c ≥ 1.
Proof. Fix any instance (G, k) with k ≥ 2 of Dominating Set which has domination number at most k or at least ck(k + 1) > c(k + 1). Then, by Observation 6.4, the hypergraph S (R(G, k)) has a distinguished vertex v * such that following properties are satisfied: C1 if G has domination number at most k, then S(R(G, k)) has hitting set number k and all of its minimum hitting sets avoid v * ; C2 if G has domination number strictly greater than c(k + 1), then S(R(G, k)) has hitting set number k + 1 and its distinguished vertex v * is contained in every solution of size at most c(k + 1).
Let Q be the set returned by any algorithm for c-Essential detection for PerfDel on input (P • S • R)(G, k), k + 1 . Notice that, by Lemma 6.5, in both Case C1 and Case C2 we have that the optimum for PerfDel on (P • S • R)(G, k) coincides with the optimum for HittingSet on S (R(G, k)).
With this observation in mind, consider Case C1. Here we have that Q is contained in an optimum solution Q of size k (by Property G1). However, by the second point in Lemma 6.5 (and since all size-k hitting sets of S(R(G, k)) avoid v * ) we deduce that any such Q (and hence Q) cannot contain v * (which is a vertex of S (R(G, k)) and hence also a vertex of (P • S • R)(G, k)).
For Case C2, consider any perfect deletion set X in (P • S • R)(G, k) of size at most c(k + 1). If we can show that X must always contain v * , then we are done since it would imply that v * is c-essential which, by Property G2 would allows us to decide whether G has domination number either k or greater than c(k + 1) simply by checking whether v * is in Q or not. So, seeking a contradiction, suppose v * ∈ X. By Property P1 of Lemma 2 and since each hyperedge S (R(G, k)) has size at least 2, we can find a subset Y of the vertices of S(R(G, k)) − v * of size at most |X| such that (P • S • R)(G, k) − Y is perfect. But then, by Property P2 of Lemma 6.5, we have that Y is a hitting set of size at most |X| = c(k + 1) ≤ ck(k + 1) in S(R(G, k)) which avoids v * . However, this is a contradiction since Observation 6.4 guarantees that v * is contained in every hitting set for S(R(G, k)) of size at most ck(k + 1).
In a similar vein to Heggernes et al.'s [28, Thm. 1] reduction P (Equation 2)) one can define a reduction L ( Figure 2) from Hitting Set to Wheel-free Edge-Deletion. This is due to Lokshtanov [35] and it is defined as follows. Given an instance (H, k) of Hitting Set, for each hyperedge e ∈ E(H) with e = {x 1 , . . . , x }, construct the wheel W e with 3 spokes and, picking some cyclic order of its rim-edges (i.e. the edges of the 3 -cycle in the wheel) denote them as e x1 , e 1 , e 1 , e x2 , e 2 , e 2 , . . . , e x , e , e .
We say that the edges e x1 , e x2 , . . . e x3 correspond to the vertices x 1 , x 2 , . . . , x respectively. Then, define the equivalence relation ∼ on the edges of the disjoint union of all such wheels so that any two edges that correspond to the same vertex become equivalent under ∼ (stating this formally, given any two distinct hyperedges e, f in H, for all vertices x ∈ e ∩ f , set e x ∼ f x ). Finally define L(H) (see Figure 2) to be the quotient Given Lokshtanov's parameter-preserving reduction [35] L from Hitting Set to Wheelfree Edge-Deletion, we can argue in similar vein to Theorem 6.6 to show the intractability of c-Essential detection for WheelDelE.
Since we have so far focused on vertex-deletion problems, rather than proving this for the edge-deletion case, we will focus on showing the intractability of c-Essential detection for WheelDel. To that end, we need the following slight modification of Lokshtanov's reduction. Given Figure 2 An example of the reduction L (we omit the centers of the two wheels above to improve readability). The edge marked with bold labels are those which correspond to vertices 1, 2 and 3 of the Set-Cover instance H.
Proof. By Lokshtanov's reduction [35], we have for all k that: H has a hitting set of size k if and only if L(H) has an edge-modulator to wheel-freeness F of size k such that every edge of F corresponds to a vertex in H. Note that, given any such F , we can turn this into a vertex-modulator for wheel-freeness (of the same size as F and whose elements also all correspond to vertices of H) on Λ(H) by mapping each edge in F to its subdividing vertex. Proof. Once again, starting with any instance (G, k) with k ≥ 2 of Dominating Set which has domination number either k or at least ck(k + 1), we apply the closed-neighborhood mapping S (Equation (1)) so that we may proceed by case distinction on the same cases C1 and C2 as we did in the proof of Theorem 6.6.
Notice that, for any vertex x in (Λ • S • R)(G, k) which does not correspond to any vertex of S(R(G, k)), x is contained in exactly one wheel of (Λ • S • R)(G, k). This, combined with Lemma 6.7, implies that the optimum for WheelDel on (Λ • S • R)(G, k) always coincides with the optimum for HittingSet on S (R(G, k)).
Let Q be the set returned by any algorithm for c-Essential detection for WheelDel on input (Λ • S • R)(G, k).
In Case C1, since (G, k) is a yes-instance, S(R(G, k)) has a minimum hitting set of size k and every such minimum hitting set avoids the distinguished vertex v * . Thus, by Lemma 6.7, we have that (Λ • S • R)(G, k) has wheel-free deletion number k and every witness X of this fact satisfies the following property: no vertex in X corresponds to v * in any wheel of (Λ • S • R)(G, k). Consequently, since the returned set Q satisfies Property G1, Q does not contain any edge corresponding to v * either.
In Case C2, since G has domination number strictly greater than ck(k + 1), S(R(G, k)) has hitting set number k + 1 and its distinguished vertex v * is contained in every solution of size at most c(k + 1). Now take any wheel-free deletion set X of size at most c(k + 1) = c·OPT (Λ•S •R)(G, k) (recall that the optimum for WheelDel on (Λ•S •R)(G, k) always coincides with the optimum for HittingSet on S(R(G, k))). Now, seeking a contradiction, suppose that no element of X corresponds to v * . Since any element x in X is contained in precisely one wheel whenever it does not correspond to any vertex of S (R(G, k)), we can find always find a modulator Y of size at most that of X whose elements all correspond to vertices of S (R(G, k)). Furthermore, since we can assume that G contains no isolated vertices, we can also assume that all hyperedges of S (R(G, k)) have size at least 2. Thus every wheel in (L • S • R)(G, k) has at least two vertices corresponding to vertices of S (R(G, k)) and hence we can further assume that no vertex in Y corresponds to v * (if it does, we can modify Y ). But then the vertices corresponding to those of Y form a hitting set of S(R(G, k)) which: has size at most |Y | ≤ |X| ≤ c(k + 1) and avoids v * , contradicting the fact that v * is contained in every solution of size at most c(k + 1) in S(R(G, k)). Thus we have that v * ∈ Q if and only if v * is c(k + 1)-essential in S(R(G, k)) which is enough to distinguish whether G has domination number at most k or at least ck(k + 1).

Connections to Perturbation Resilience
In the area of perturbation resilience [39] there is a notion of so-called c-perturbation resilient instances to optimization problems. Roughly, these are instances G in which there is a unique optimal solution S which far outperforms (by a factor of c) every other solution S in G. More formally, for a vertex-weighted graph minimization problem Π whose solution is a vertex-subset, we say that an instance (G, w : V (G) → N) with a unique optimal solution S is cperturbation resilient if for any perturbed weight function w satisfying w(v) ≤ w (v) ≤ c·w(v) for all v ∈ V (G), the instance (G, w (x)) has a unique optimal solution and furthermore this solution is S. (Of course, one can define an analogous notion for maximization problems as well and what follows in this section applies to both.) Classes of c-perturbation resilient instances have been shown to be 'islands of tractability' where many intractable problems become polynomial-time-solvable [39] and the suggestive intuition behind this fact is that perturbation resilient instances have unique optima which 'stand out' and are 'obvious' in some sense. Viewing stability through the lens of parameterized complexity, it is natural to ask whether one can quantify in an algorithmically useful way how distant an input is from being stable. The following proposition supports our claim that the non-essentiality (recall Theorem 5.1) is a good such measure since on (> c)-stable inputs, the c-non-essentiality is smallest possible (namely it is 0). Proposition 7.1. Given constants c > c ≥ 1, if G is a c -stable input to a graph optimization problem Π whose solutions are vertex-subsets, then E Π c (G) is the unique optimum of G.
Proof. Consider the unique optimum S for Π on G. If S is a c-approximation for Π on G, then we must have S = S (since otherwise G would not be c -stable). As a consequence we know that every vertex of S must be c-essential and hence we have S ⊆ E c (G) ⊆ S. Proposition 7.1 and Theorem 5.1 allow us to immediately deduce that any algorithm for c-Essential detection solves all (> c)-perturbation resilient instances exactly.
Corollary 7.2. Given a minimization problem Π, any algorithm for c-Essential detection for Π solves (> c)-stable instances exactly.

Conclusion
We introduced the notion of c-essential vertices for vertex-subset minimization problems on graphs, to formalize the idea that a vertex belongs to all reasonable solutions. Using a variety of approaches centered around the theme of covering/packing duality, we gave polynomialtime algorithms that detect a subset of an optimal solution containing all c-essential vertices, which decreased the search space of parameterized algorithms from exponential in the size of the solution, to exponential in the number of non-essential vertices in the solution.
Throughout the paper we have restricted ourselves to working with unweighted problems. However, many of the same ideas can be applied in the setting where each vertex has a positive integer weight of magnitude O(|V (G)| O(1) ) and we search for a minimum-weight solution. Since integral vertex weights can be simulated for many problems by making twin-copies of a vertex, our approach can be extended to Weighted Vertex Cover, Weighted Odd Cycle Transversal, and Weighted Chordal Deletion.
Our results shed a new light on which instances of NP-hard problems can be solved efficiently. FPT algorithms for parameterizations by solution size show that instances are easy when their optimal solutions are small. Theorem 1.1 refines this view: it shows that instances with large optimal solutions can still be easy, as long as only a small number of vertices in the optimum is not c-essential.
We remark that there is an alternative route to algorithms for c-Essential detection, which is applicable to C-Deletion problems which admit a constant-factor approximation. If there is a polynomial-time algorithm that, given a graph G and vertex v, outputs a c-approximation for the problem of finding a minimum-size C-modulator avoiding v, it can be used for c-Essential detection. A valid output S for the detection problem with input (G, k) is obtained by letting S contain all vertices for which the approximation algorithm outputs a v-avoiding modulator of size more than c · k. Using this approach (cf. [24]) one can solve max F ∈F |V (F )| O(1) -Essential detection for F-Minor-Free Deletion for any finite family F containing a planar graph. As the results for problems for which no constant-factor approximation exists are more interesting, we focused on those.
Our work opens up several questions for future work. Is the integrality gap for v-Avoiding Planar Vertex Deletion constant, when G−v is planar? Can O(1)-Essential detection for Planar Vertex Deletion be solved in polynomial time? Can 2-Essential detection for Chordal Deletion be solved in polynomial time? Can the constant c for which we can detect c-essential vertices be lowered below 2?
Considering a broader horizon, it would be interesting to investigate whether there are less restrictive notions than c-essentiality which can be used as the basis for guaranteed search-space reduction.