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

We use Lemma 1.1 to prove that the kernel size of O(k d ) in Theorem 1.4 is asymptotically optimal under the hypothesis coNP ⊆ NP/poly. For the reduction, we use gadgets with few vertices that coordinate the availability of groups of vertices. For example, we may have two sets U1, U2 of vertices and our gadget makes sure that in every perfect packing of the graph one set is fully covered by the gadget while the other group has to be covered by hyperedges of the graph external to the gadget. Ultimately, this enables us to choose between diﬀerent instances in the OR-problem. The precise formulation of the gadget is as follows.

** Lemma 3.6.**

Let d ≥ 3, m ≥ 1, and s ≥ 1 be integers. In time polynomial in d, m, s, we can compute a d-uniform hypergraph S with O(dsm) vertices and pairwise disjoint sets U1 (S),..., Um (S) ⊂ V (S) of size s each, such that the following conditions hold.

(i) (Completeness) For each i, S − Ui has a perfect matching.

(ii) (Soundness) If S is a subgraph of some G and the vertices of S −(U1 ∪· · ·∪Um ) are only contained in edges of S, then every perfect matching of G contains a perfect matching of S − Ui for some i.

(iii) The underlying graph of S (the graph obtained by replacing the d-hyperedges of S by d-cliques) does not contain a clique of size d + 1 and it contains i Ui as an independent set.

In addition to the completeness and the soundness properties that make the gadget work the way we want, we also have a structural property (iii), which we need later when we transfer our results to Kd -matching. We defer the proof of Lemma 3.6 to the end of this section and use it now to prove the following.

** Lemma 3.7.**

Let d ≥ 3 be an integer.

There is a ≤p -reduction from OR(d-Set Matching) to d-Set Matching that maps m t-tuples of instances of bitlength s each to instances on t1/d · poly(s) vertices whose underlying graph does not contain a clique of size d + 1.

Proof. Let G1,..., Gt be instances of d-Set Matching, i.e., d-uniform hypergraphs of size s each. Finding perfect matchings in d-partite d-uniform hypergraphs is NP-hard for d ≥ 3, so we can assume w.l.o.g. that the Gi ’s are d-partite and each part of the partition contains exactly s/d vertices. The goal is to ﬁnd out whether some Gi contains a perfect matching. We reduce this question to an instance G on few vertices.

The vertex set of G consists of d·t1/d groups of n/d vertices each, i.e., V (G) = a,b Va,b for a ∈ [d] and b ∈ [t1/d ]. Then we can write the input graphs as Gb using an index vector b = (b1,..., bd ) ∈ [t1/d ]d. For each graph Gb we add edges to G in the following ˙ ˙ way: We identify the vertex set of Gb with V1,b1 ∪... ∪ Vd,bd, and we let G contain all the edges of Gb. Since each Gb is d-partite, the same is true for G at this stage of the construction. Now we modify G such that each perfect matching of G only ever uses edges originating from at most one graph Gb. For this it suﬃces to add a gadget for every a ∈ [d] that blocks all but exactly one group Va,b in every perfect matching. For each

** **

**3. Communicating Instances of Hard Problems**

a ∈ [d], we add a copy Sa of S(Va,1,..., Va,m ) from Lemma 3.6 to G, where m = t1/d.

Clearly, |V (G)| ≤ O(st1/d ). Furthermore, the underlying graph of G does not contain a clique of size d + 1 as the graph restricted to a,b Va,b is d-partite and the gadgets do not contain cliques of size d + 1 in their underlying graph.

Now we verify the correctness of the reduction. If some Gb has a perfect matching then the completeness property of Sa ensures that Sa − Va,ba has a perfect matching for all a ∈ [d]. Together with the perfect matching of Gb this gives a perfect matching of G.

For the soundness, assume M is a perfect matching of G. Then each Sa is guaranteed to have a ba such that M contains a perfect matching of Sa − Va,ba. Since Va,ba is an independent set in Sa, M uses only edges of Gb to cover the Va,ba. In particular, Gb has a perfect matching.

Our kernel lower bound for d-Set Matching, now follows immediately by combining the above with Lemma 1.1.

** Theorem 1.5 (restated).**

Let d ≥ 3 be an integer and a positive real. If coNP ⊆ NP/poly, there it no protocol of cost O(k d− ) for Perfect d-Set Matching.

Proof of Lemma 3.6 We use cycles as building blocks in the gadget constructions. A loose cycle of length in a d-uniform hypergraph is a sequence C = v1, e1, v2, e2,..., v, e with the property that ei ∩ei+1 = {vi+1 } and ei ∩ej = ∅ if i ∈ {j −1, j, j +1}. The indices are always understood modulo. The vertices v1,..., v are the connection vertices, whereas all other vertices are free vertices of the cycle. Our ﬁrst lemma, which allows us to coordinate two sets of vertices.

** Lemma 3.8.**

Let d ≥ 3 and s ≥ 1 be integers. Let C = v1, e1, v2, e2,..., v2s, e2s be a loose cycle of d-hyperedges as depicted in Figure 3.3. We deﬁne U1 (C) = i even ei \ {vi, vi+1 } and U2 (C) = i odd ei \ {vi, vi+1 }. Then (i) (Completeness) C − U1 and C − U2 have a perfect matching.

(ii) (Soundness) If C is a subgraph of some G and the vertices of C − (U1 ∪ U2 ) are only contained in edges of C, then every perfect matching of G contains a perfect matching of C − Ui for some i.

Proof. For the completeness, {e2i+1 } forms a perfect matching of C −U1 and {e2i } forms a perfect matching of C − U2. For the soundness, the only way to cover a vertex vi of C is to pick one of its two incident hyperedges. Since C is an even cycle, the two ways of doing this for all such vertices in a consistent way are as in the completeness step.

We use the above gadget with two choices to construct the gadget in Lemma 3.6, which forces perfect matchings to choose properly between m sets of vertices.

Proof (of Lemma 3.6). We construct a coordination gadget S as depicted in Figure 3.4

**as follows:**

** Figure 3.3.**

: Left: An even cycle gadget with d = 3, s = 3, U1 = {1, 3, 5}, and U2 = {2, 4, 6}. Black vertices are free vertices, and gray vertices are connection vertices that are not supposed to be adjacent to any other vertex of the outside graph. Right: Pictorial abbreviation of the graph on the left. By Lemma 3.8, any perfect matching blocks exactly the vertices in one of the halves using edges of the gadget.

1. We start with s disjoint odd cycles: loose cycles C1,..., Cs of length 2m + 1 each.

We denote the vertices in these cycles with ci,j and the edges with Ci,j, i.e.,

4. For j ∈ [2m+1], enumerate the vertices vj,1,..., vj,(d−2)s of U2 (Fj ) = V (Fj )∩F \C arbitrarily. For each k ∈ [(d−2)s], add a set Ak containing m+1 sets {u1,..., ud−1 } of (d − 1) fresh vertices, and for all j we add the edges {u1,..., ud−1, vj,k } to S.

This ﬁnishes the construction of S. First we show (iii). For this we consider the underlying graph and assume for contradiction that T is a clique of size d + 1. By the way S was constructed, and in particular by (3.1), each hyperedge of S intersects at most one set of free vertices that belongs to some cycle edge, so any two vertices from distinct sets of free vertices must be non-adjacent in the underlying hypergraph. To reach a contradiction, we distinguish two cases.

Case 1: T contains a vertex v ∈ Ak for some k. Since v’s only neighbors are d − 2

3. Communicating Instances of Hard Problems

other vertices of Ak and the vertices vj,k, T contains vj,k and vj,k for j = j. However, these vertices are not adjacent since they belong to diﬀerent even cycles.

Case 2: T contains only vertices of the cycles. Then T must contain a connection vertex v of one of the cycles since any free vertex is adjacent to at most d − 3 other free vertices. The vertex v is adjacent to exactly 2d − 2 vertices, and so T contains a free vertex w in the edge before v and w in the edge after v in the respective cycle. By the above, w and w are not adjacent.

This shows that the underlying graph does not contain a (d+1)-clique. For the second part, we observe that i∈[m] Ui is the set of connection vertices at even positions of the odd cycles, so they are pairwise non-adjacent.

For the completeness, we construct a perfect matching of S − Uj0 (S) for each j0 ∈ [m].

We deﬁne the set of indices

** J = 2j0 + 2j j = 0,..., m. (3.2)**

We use the completeness of the even cycle gadgets and take a perfect matching of Fj that covers U1 (Fj ) for all j ∈ J, and one that covers U2 (Fj ) for the m other choices j ∈ [2m + 1] \ J. This is consistent since the even cycles are disjoint. In each odd cycle Ci, we pick the edges Ci,j into the matching for j ∈ [2m + 1] \ J. This is consistent because these edges do not contain a vertex of Uj0 (S) or of U1 (Fj ) for j ∈ J, and we never take two consecutive edges. Furthermore, we have covered all vertices of C − Uj0 (S). Indeed, the only vertices not yet covered are the U2 (Fj ) = {vj,1,..., vj,(d−2)s } for j ∈ J and the vertices of the Ak. For each k ∈ [(d − 2)s] and j ∈ J, we cover the vertex vj,k using a saturation edge with some (d − 1)-group of Ak. This is possible since each Ak contains exactly |J| = m+1 groups. Now all vertices of S −Uj0 are covered by a perfect matching.

For the soundness, the claim is that any perfect matching of G has some j0 such

** **

**3.5. Packing Problems**

that Uj0 is not covered in the matching by edges of S, whereas all other vertices of S are. Let M be a perfect matching of G. The soundness of the even cycle gadgets guarantees that exactly one of U1 (Fj ) and U2 (Fj ) are covered with edges of Fj. Let J be the set of indices j for which U1 (Fj ) and not U2 (Fj ) is covered by the edges of Fj. The only way that M can cover the vertices U2 (Fj ) for j ∈ J is by using |U2 (Fj )| = (d − 2)s edges with the Ak ’s. Since there are only |Ak | = m + 1 such edges available for any given k, we have |J| = |Ak | = m + 1. The only way that M can cover the free vertices of Ci,j for j ∈ [2m + 1] \ J is by picking Ci,j into M. Since M does not contain consecutive edges of Ci and J contains m + 1 elements of [2m + 1], this means that J must be of the form (3.2) for some j0. Hence Uj (S) for j = j0 is covered in M by edges of the odd cycles and no vertex of Uj0 is covered in M by edges of S.

Kernel Lower Bounds for Graph Matching Problems For a graph H, the H-matching problem is to ﬁnd a maximal number of vertex-disjoint copies of H in a given graph G. This problem is NP-complete whenever H contains a connected component with more than two vertices [KH78] and is in P otherwise.

Clique Packing We prove Theorem 1.6, that Kd -Matching for d ≥ 4 does not have kernels of size O(k d−1− ) unless coNP ⊆ NP/poly. For this, we devise a parameter-preserving reduction from the problem of ﬁnding a perfect matching in a (d − 1)-uniform hypergraph whose underlying graph does not contain a d-clique.

Proof. Let G be a (d − 1)-uniform hypergraph on n vertices without d-clique in its underlying graph. For each edge e of G, we add a new vertex ve and transform e ∪ {ve } into a d-clique in G. We claim that G has a matching of size k := n/(d − 1) if and only if G has a Kd -matching of size k. The completeness is clear since any given matching of G can be turned into a Kd -matching of G by taking the respective d-clique for every (d − 1)-hyperedge. For the soundness, let G contain a Kd -matching of size k. Note that any d-clique of G uses exactly one vertex ve since the underlying graph of G does not contain any d-cliques and since no two ve ’s are adjacent. Thus every d-clique of G is of the form e ∪ {ve }, which gives rise to a matching of G of size k.

This combined with Lemma 1.1 and Lemma 3.7 implies Theorem 1.6 General Graph Matching Problems We prove Theorem 1.7, that H-factor does not have kernels of size O(k 2− ) unless coNP ⊆ NP/poly, whenever H is a connected graph with at least three vertices. In particular, this implies the missing case d = 3 of Kd -Matching.

3. Communicating Instances of Hard Problems Figure 3.5.: Hyperedge gadgets for diﬀerent H-matching problems. The outermost,

**black vertices are the vertices of the simulated hyperedge and the gray vertices are not supposed to be adjacent to any other vertex of the graph. Left:**

Triangle matching. Middle: 3-Path matching. Right: The general case; each circle represents a copy of H.

We use the coordination gadget of Lemma 3.6 in a reduction from a suitable ORproblem to H-Matching. To do so, we translate the coordination gadget for Perfect d-Set Matching to H-factor, which we achieve by replacing hyperedges with the following hyperedge-gadgets of [KH78].

** Lemma 3.10.**

Let H be a connected graph on d ≥ 3 vertices. There is a graph e = e(v1,..., vd ) that contains {v1,..., vd } as an independent set such that, for all S ⊆ {v1,..., vd }, the graph e − S has an H-factor if and only if |S| = 0 or |S| = d.

Proof. Let v be a vertex of H. We construct e as in Figure 3.5. We start with one central copy of H. For each vertex u ∈ [d] = V (H), we create a new copy Hu of H and denote its copy of v by vu. Finally, we add an edge between u ∈ H and w ∈ (Hu − vu ) if vu w is an edge of Hu.

For the claim, assume that 0 |S| d. Then |V (e − S)| is not an integer multiple of d = |V (H)| and there can be no H-factor in e − S. For the other direction, assume that |S| = 0. Then the subgraphs Hu for u ∈ [d] and H are d + 1 pairwise disjoint copies of H in e and form an H-factor of e. In the case |S| = d, we observe that the d subgraphs (Hu − vu ) ∪ {u} form an H-factor of e − S = e − {v1,..., vd }.

For the proof of the H-Packing kernel lower bounds, we need the Packing Lemma, Lemma 3.3. The chromatic number χ(H) is the minimum number of colors required in a proper vertex-coloring of H. The proof of [KH78] shows that H-Factor is NP-complete even in case we are looking for an H-factor in χ(H)-partite graphs. We are going to make use of that in the following reduction.