FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |   ...   | 16 |

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

-- [ Page 9 ] --

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 different 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 find 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 suffices 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 first 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 define 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 finishes 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 different 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 define 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 find 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 finding 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 different 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.

–  –  –

Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |   ...   | 16 |

Similar works:

«Ann. Naturhist. Mus. Wien 109 A 1–17 Wien, September 2007 Pseudoctenis cornelii nov. spec. (cycadalean foliage) from the Carnian (Upper Triassic) of Lunz, Lower Austria By Christian POTT1, Hans KERP1 and Michael KRINGS2 (With 1 textfigure and 3 plates) Manuskript submitted on April 12th 2006, the revised manuscript on June 7th 2006 Zusammenfassung Die Gattung Pseudoctenis (Cycadeenbeblätterung) ist ein charakteristisches Element rhätischer (oberste Trias) und jurassischer Floren in Europa....»

«MAGYAR FOGÁSZATI BIBLIOGRÁFIA (BIBLIOGRAPHIA ODONTOLOGICA HUNG ARICA) Összeállította: Dr. HUSZÁR GYÖRGY (Budapest) A bibliográfia célja rendszerbe foglalva összegyűjteni, felsorolni a szellemi alkotásokat. Szakbibliográfia a neve az egy tudomány­ ágat feldolgozó könyvészetnek. Az első orvosi szakbibliográfiában helyet kaptak már a fogászati művek is. Baldinger: „Neues Maga­ zin f. Aerzte-ben (Leipzig 1775) találjuk az első fogorvosi biblio­ gráfiát. Ploucquet...»

«Understanding the Annulment Process The Tribunal Diocese of Arlington Diocese of Arlington The Tribunal 200 North Glebe Road – Suite 524 Arlington, Virginia 22203 (703) 841-2555 FAX: (703) 841-0693 Dear Friends: The separation from a spouse is always a difficult time. The loss of a spouse through divorce always results in pain over the separation and causes anxiety over the future. The Church makes many efforts to offer the separated and divorced support to cope with the present and prepare...»

«ATINER CONFERENCE PAPER SERIES No: LNG2014-1176 Athens Institute for Education and Research ATINER ATINER's Conference Paper Series LIT2014-1537 Globalization and Multiculturalism: Defining the New Universalism in Selected Texts of Samuel Selvon, V. S. Naipaul and Anita Desai Sarah Anyang Agbor Associate Professor University of Yaounde I Cameroon ATINER CONFERENCE PAPER SERIES No: LIT2014-1537 An Introduction to ATINER's Conference Paper Series ATINER started to publish this conference papers...»

«УДК 616.89 Редакционная коллегия: Т.П.Клюшник, Л.И.Абрамова, В.Г.Каледа Официальные Actavis спонсоры: Pfizer Спонсоры–1: Bristol-Myers Squibb EVER Neuro Pharma Gedeon Richter Janssen-Cilag Lundbeck Sandoz Sun Спонсоры–2: Egis Eli Lilly GlaxoSmithKline MedAvante Servier Официальный провайдер Школы Агентство Медицинских молодых учёных...»

«‘Forgotten and failed’ Sexual exploitation is one of the most complex forms of child abuse, not least because many of the children and young people involved do not initially recognise or acknowledge that they are being abused. Much progress has been made in recognising that children who are often referred to as being ‘abused through prostitution’ are children in need; but the sexual exploitation of children takes different forms, and many of the children involved are not visibly ‘on...»

«ABSTRACTS 2009 SONDERHEFT JEL-No: F55, K10, N44 Gregor Schusterschitz Institutions of the EU in the Treaty of Lisbon and after the European Council of December 2008 The reform of the institutions of the EU has always been at the core of any EU treaty reform. It is the aim of the Treaty of Lisbon to introduce the necessary changes that were already foreseen in the ill-fated Constitutional Treaty (with some adjustments). The Treaty of Lisbon introduces the European Council as an official organ...»

«May 20, 2013 Final Independent External Peer Review Report Willamette River Floodplain Restoration Study, Lower Coast and Middle Forks Subbasins, Oregon Prepared by Battelle Memorial Institute Prepared for Department of the Army U.S. Army Corps of Engineers Ecosystem Restoration Planning Center of Expertise for the St. Paul District Contract No. W912HQ-10-D-0002 Task Order: 0037 Willamette River IEPR Final IEPR Report Final Independent External Peer Review Report Willamette River Floodplain...»

«28.02.1995 Gericht OGH Entscheidungsdatum 28.02.1995 Geschäftszahl 11Os1/95 Kopf Der Oberste Gerichtshof hat am 28.Februar 1995 durch den Senatspräsidenten des Obersten Gerichtshofes Dr.Lachner als Vorsitzenden und durch die Hofräte des Obersten Gerichtshofes Prof.Dr.Hager, Dr.Schindler, Dr.Mayrhofer und Dr.Schmucker als weitere Richter, in Gegenwart der Richteramtsanwärterin Mag.Braunwieser als Schriftführerin, in der Strafsache gegen Matthäus A***** und einen anderen wegen des...»

«Reduced Model for Flow Simulation in the Burner Region of Lime Shaft Kilns Dissertation zur Erlangung des akademischen Grades Doktoringenieur (Dr.-Ing.) vorgelegt von M.Sc. Zhiguo Xu geb. am 04.02.1978 in Heze, Shandong, China genehmigt durch die Fakult¨t f¨r Verfahrensund Systemtechnik au der Otto-von-Guericke-Universit¨t Magdeburg a Gutachter: Prof. Dr.-Ing. E. Specht, Universit¨t Magdeburg a Prof. Dr.-Ing. D. Thevenin, Universit¨t Magdeburg a eingereicht am 01.03.2007...»

«Bulletin des séances du Grand Conseil du Canton du Valais Session prorogée de novembre 1954 Jâ /Ol Grand Conseil Session prorogée de novembre 1954 Séance du 2 4 janvier 1955 Présidence : M. le député Antoine Barras, président. A l'ouverture, M. le Président Barras prononce l'allocution suivante : « J'ai l'honneur de déclarer ouverte la session prorogée de janvier 1955. Depuis la dernière session de novembre, plusieurs événements sont venus assombrir cette fin d'année 1954....»


<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.