# «Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

As another example, consider the case of Bounded-Degree Deletion. In the known reduction from Vertex Cover to this problem [KD79], d new edges are attached to every vertex of G (see Figure 3.1b). Removing any vertex cover of G from G reduces the maximum degree to d. Vice versa, any set that reduces the maximum degree in G to d can be transformed into a vertex cover of G of at most the same size.

Next consider the more general case in which the minimal graphs that violate Π are connected. Generalizing the above two examples we obtain G by replacing every edge of the Vertex Cover-instance G by a copy of a ﬁxed connected graph F violating Π.

We refer to F as a “forbidden” graph since no graph satisfying Π can contain F as a subgraph. Thus, any deletion set in G has to pick at least one vertex from every copy of F. Projecting the deletion set back onto the graph G yields a vertex cover of size no more than the deletion set. This way we can guarantee the soundness of the reduction – if G has a deletion set of size at most k then G has a vertex cover of size at most k.

For the completeness of the reduction, we would like to ensure that removing a vertex cover S of G from G leaves a graph G \ S satisfying Π. This is not automatically the case because G \ S may contain components of the form depicted in Figure 3.2a, where the bullets are vertices of G and the hashed vertices are part of the vertex cover S (and are therefore not part of G \ S) but the center vertex is not. Such a component could contain a copy of F, in which case G \ S would not satisfy Π. However, by attaching the copies of F in an appropriate way we can make sure that the connected components

** Figure 3.2.**

: Connected component C that might remain after removing a vertex cover S of G from G, centered around a vertex c that has degree 3 in G and does not belong to S. (a) Naïve construction. (b) Final construction.

of G \ S are all “simpler” than F. Picking F to be a “simplest” connected graph that violates Π then does the job as long as all minimal graphs violating Π are connected.

More generally, consider a graph F violating Π whose most complex connected component C is as simple as possible among all graphs violating Π. If F has no other connected component of the same complexity as C, then the above construction still works, using a copy of C to replace every edge in G and including a copy of F \ C for every vertex of G.

In the most general case, where minimal graphs violating Π can have multiple components of the same complexity, we use a slightly diﬀerent construction that involves multiple copies of G. The graph F now becomes a “simplest” graph for which the number of disjoint copies of F that satisﬁes Π is bounded. The reduction is no longer parameter preserving in general, but the parameter k for G is still linearly bounded by the parameter k for G. The latter ensures that the lower bound for Π-Vertex Deletion is as strong as for Vertex Cover modulo a constant factor.

The simplicity measure we use is the same as the one of Lewis and Yannakakis [LY80] but the construction is a bit diﬀerent: their construction blows up the parameter k to Θ(nk), but a straightforward modiﬁcation reduces k to Θ(k 2 ). We further reduce k to Θ(k) using a matching argument.

** Lemma 3.5.**

Let Π be a graph property that is inherited by subgraphs, and is satisﬁed by inﬁnitely many but not all graphs. There is a ≤p -reduction from Vertex Cover to m Π-Vertex Deletion that maps instances with parameter k to instances with parameter O(k).

Proof. We start by spelling out the simplicity measure for graphs. We ﬁrst consider a connected graph C. For any vertex s of C, we deﬁne the character of C relative to s as the sequence χ = (χi )i∈N where χi denotes the number of connected components of C \ {s} that have exactly i vertices. We compare two characters χ and η using the colexicographical order, i.e., χ η if there exists a positive integer i such that χj = ηj for all integers j i and χi ηi. The corresponding relation ≤ deﬁnes a well-order on the set of characters, that is, a total order in which every nonempty subset has a

** **

**3. Communicating Instances of Hard Problems**

smallest element. We deﬁne the character of C as a smallest character of C relative to s over all vertices s of C.

For an arbitrary graph G we deﬁne its signature as a mapping σ from the set of all characters to N, where σ(χ) equals the number of connected components of G with character χ. We compare two signatures σ and τ using the colexicographical order induced by the order on characters, i.e., σ τ if there exists a character χ such that σ(η) = τ (η) for all characters η χ and σ(χ) τ (χ). The corresponding relation ≤ deﬁnes a well-order on the set of signatures.

Our simplicity measure on graphs is induced by the ≤-relation on their signatures.

We choose a graph F with the smallest signature among all graphs for which the number of disjoint copies that satisfy Π is bounded. Note that F exists because not all graphs satisfy Π. Let t be the positive integer such that the disjoint union of t − 1 copies of F satisﬁes Π but t disjoint copies do not. Let C denote a connected component of F with largest character and let s ∈ V (C) be a witness for that character. Let L be the subgraph of C spanned by s and the vertices of a largest connected component of C \{s}, and let L be the subgraph of C spanned by s and the vertices of C \ L. Note that L contains at least one other vertex than s. Otherwise, F would consist of isolated vertices only and only ﬁnitely many graphs would satisfy Π. Let r be an arbitrary vertex of L \ {s}.

We are now in position to describe the reduction transforming an instance (G, k) of Vertex Cover into an instance (G, k ) of Π-Vertex Deletion such that G has a vertex cover of size k if and only if k vertices can be deleted from G to make the residual graph satisfy Π. For the construction of G we start with 2t − 1 disjoint copies G1,..., G2t−1 of G. We replace every edge e of Gi by a copy Le of the component L such that the endpoints of e are identiﬁed with s and r in an arbitrary way; the vertices of Le outside of e are new. Furthermore, we attach to every vertex v ∈ V (G) a graph Rv that consists of a copy of L and disjoint copies of F \ C; here we identify v with the vertex s of L and create all other vertices of Rv new. See Figure 3.1c. In the remainder, we show that the reduction works when we set k = (2t − 1)k.

For the soundness of the reduction, let S be a set of k vertices in G such that G \ S satisﬁes Π. Let S denote the projection of S onto V (G1 ) ∪ · · · ∪ V (G2t−1 ), where the projection of a vertex u ∈ V (G ) is one of the vertices of e (chosen arbitrarily) in case u ∈ V (Le ) \ e and the vertex v in case u ∈ V (Rv ). We claim that S is at most 2t − 2 vertices away from being a vertex cover of G1 ∪· · ·∪G2t−1. Let M be a maximal matching in (G1 ∪ · · · ∪ G2t−1 ) \ S. If M contains at least t edges, then S avoids at least t disjoint subgraphs Le ∪ Ru ∪ Rv for e = (u, v). In particular, G \ S contains t copies of F as subgraphs, which contradicts the fact that G \ S satisﬁes Π. Thus, M contains at most t − 1 edges. Adding V (M ) to S, we thus get a vertex cover of G1 ∪ · · · ∪ G2t−1 of size at most (2t − 1)k + 2t − 2. By averaging, there is an i with |S ∩ V (Gi )| ≤ k + 1 − 2t−1 = k.

Hence G has a vertex cover of size at most k.

For the completeness of the reduction, let S be a vertex cover of G of size at most k.

Let S consist of the 2t − 1 copies of S in the graphs G1,..., G2t−1. Clearly, |S | ≤ (2t − 1)k. Let H be obtained from G \ S by removing duplicate isomorphic copies of connected components. Note that G \ S is a subgraph of ﬁnitely many disjoint copies

** **

**3.4. Covering Problems**

of H. Thus, if we can show that H has a strictly smaller signature than F, then any number of disjoint copies of H satisﬁes Π and by inheritance the subgraph G \ S also satisﬁes Π. Therefore, S is a set of at most k = (2t − 1)k vertices such that G \ S satisﬁes Π.

It remains to argue that H has a strictly smaller signature than F. In order to do so we consider the connected components of H, and we distinguish four types: (1) components isomorphic to components of F \ C, (2) components isomorphic to components of L \ {s, r}, (3) components isomorphic to components of L \ {s}, and (4) components as in Figure 3.2b consisting of a single copy of L and one or more copies of L \ {s} and L \ {r} in which all remaining copies of s and r have been identiﬁed with the vertex c. We show that for each of the connected components of types (2), (3), and (4), the character is strictly less than for C. Since C is the connected component of F with the largest character and H has no duplicate isomorphic connected components, this implies that no connected component of H has a character larger than C, and that the number of connected components of H with the same character as C is strictly less than in F.

Therefore, the signature of H is strictly less than the one of F.

Let us ﬁrst consider a connected component C of H of type (4). Consider removing the vertex c in Figure 3.2b. Since L \ {s} is a largest connected component of C \ {s}, no connected component of C \ {c} can have more vertices than L \ {s}. Moreover, the only components in C \ {c} that can have |V (L \ {s})| vertices must come from the part L \ {s}. Since C = L ∪ L, this means that C \ {s} has one more connected component with |V (L \ {s})| vertices than C \ {c}. Thus, the character of C relative to c, and a fortiori the character of C, is strictly less than the character of C.

The claim that connected components of types (2) and (3) have characters strictly less than C follows from the corresponding claim for type (4) since (2) and (3) are subgraphs of a graph of type (4) and taking subgraphs cannot result in larger characters.

We point out that the proof of Lewis and Yannakakis [LY80] only needs inheritance by induced subgraphs. The only step in the proof of Lemma 3.5 that requires the stronger property of inheritance by subgraphs is the matching argument. That step is vacuous when t = 1, e.g., when all minimal graphs violating Π are connected. The stronger property is also not necessary when the vertex s is not adjacent to all vertices of L (and we choose r as one of the non-adjacent vertices). In such cases our proof can do with inheritance by induced subgraphs.

Proof (of Theorem 1.3). Suppose that Π-Vertex Deletion parameterized by the size of the deletion set has a cost O(k 2− ) protocol. By combining the ≤p -reduction from m Lemma 3.5 with that protocol, we obtain a cost O(k 2− ) protocol for Vertex Cover parameterized by the size of the vertex cover. Since k ≤ n, the case d = 2 of Theorem 1.2 then implies that coNP ⊆ NP/poly.

** Theorem 1.3 applies, among others, to Feedback Vertex Set, another problem whose kernelization has received considerable attention in parameterized complexity.**

** Theorem 1.3 implies that Feedback Vertex Set does not have kernels consisting of O(k 2− ) edges unless coNP ⊆ NP/poly.**

This result is tight – a kernel with O(k 2 ) edges

** **

**3. Communicating Instances of Hard Problems**

follows from recent work by Thomassé [Tho09]. He constructs a kernel with at most 4k 2 vertices and maximum degree at most 4k. For such an instance to be positive, the number of edges can be no larger than 8k 2. Indeed, suppose that S is a feedback vertex set of G of size at most k. Then the graph induced by V (G) \ S is a forest and has at most 4k 2 edges. All other edges of G are incident to a vertex of S. As the maximum degree is no larger than 4k, at most 4k 2 edges are incident to S. Summing up, G has at most 8k 2 edges. Thus, if G has more than 8k 2 edges, we can reduce to a trivial negative instance; otherwise, we reduce to G. This results in a kernel with O(k 2 ) edges.

**Extension to Hypergraphs**

We now turn to vertex cover and related problems on d-uniform hypergraphs. Since k ≤ n, Theorem 1.2 implies that d-Vertex Cover does not have kernels with O(k d− ) edges unless coNP ⊆ NP/poly. We point out that kernels with O(k d ) edges exist for d-Vertex Cover. This follows from a generalization of Buss’ high-degree rule (see the introduction) and a folklore application of the sunﬂower lemma (see [FG06, chapter 9.1], for example). Recall that for a hypergraph G, a sunﬂower with heart h ⊆ V (G) and p petals is a set of distinct edges whose pairwise intersection is exactly h. The kernelization proceeds by repeatedly picking a sunﬂower with at least k + 1 petals, removing the involved edges, and adding the heart as a new edge to the graph. Note that in this process, edges of size less than d may be added to G. To get back a duniform graph, one can complete those edges with fresh vertices, which doesn’t aﬀect the number of edges nor the minimum size of a vertex cover. The process continues until no sunﬂower with k + 1 petals exists, which is bound to happen as the number of edges decreases in every step. The sunﬂower lemma of Erdős and Rado [ER60] states that any d-uniform hypergraph with more than d! · k d edges has a sunﬂower with k + 1 petals.

Thus, the hypergraph that remains at the end has at most d · d! · k d = O(k d ) edges, and has a vertex cover of size at most k if and only if the original hypergraph does.

Regarding extensions of Theorem 1.3 to d-uniform hypergraphs for d 2, we cannot expect to rule out protocols of cost O(k d− ) for all hypergraph properties Π that are inherited by subgraphs and for which the deletion problem is nontrivial. This is because the property Π could only depend on the primal graph underlying the hypergraph, for which protocols of cost O(k 2 ) are known in some cases.

3.5. Packing Problems Kernelization of the Set Matching Problem The d-Set Matching problem is to ﬁnd a maximum collection of hyperedges in a d-uniform hypergraph such that any two hyperedges are disjoint. For d = 2, this is the maximum matching problem and polynomial-time solvable. The restriction of this problem to d-partite hypergraphs is the d-dimensional matching problem and NPhard [Kar72] for d ≥ 3.

<

** **

**3.5. Packing Problems**