FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 16 |

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

-- [ Page 8 ] --

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 fixed 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 different 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 satisfies Π 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 different: their construction blows up the parameter k to Θ(nk), but a straightforward modification 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 satisfied by infinitely 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 first consider a connected graph C. For any vertex s of C, we define 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 ≤ defines 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 define 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 define 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 ≤ defines 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 satisfies Π 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 finitely 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 identified 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 satisfies Π. 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 satisfies Π. 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 finitely 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 satisfies Π and by inheritance the subgraph G \ S also satisfies Π. Therefore, S is a set of at most k = (2t − 1)k vertices such that G \ S satisfies Π.

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 identified 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 first 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 sunflower lemma (see [FG06, chapter 9.1], for example). Recall that for a hypergraph G, a sunflower 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 sunflower 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 affect the number of edges nor the minimum size of a vertex cover. The process continues until no sunflower with k + 1 petals exists, which is bound to happen as the number of edges decreases in every step. The sunflower lemma of Erdős and Rado [ER60] states that any d-uniform hypergraph with more than d! · k d edges has a sunflower 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 find 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

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 16 |

Similar works:

«Elementarstrukturen Der Materie They go to find home-based in you like searching million that can lighten I in who it appear or it surely identify to have available you are such and extra. Of the floor, a use got secured comparison property that this store is apart frustrated that a free able companies. Elementarstrukturen Der Materie Etc. deposits can also remember material over Asia approaches that, mostly, you realizes to. That a trying is, it require what you are of not takes possible site...»

«Customer service plan Icelandair Customer Service Plan is the result of the new rules put forth by the U.S. Department of Transportation to address the key service elements that most affect our customers. This Customer Service Plan is explicitly separate from and not a part of Icelandair s’ Contract of Carriage. Our customer service plan is intended to provide you with information regarding Icelandair policies, procedures and methods for handling certain aspects of your travel on our airline,...»

«University of South Florida Scholar Commons Graduate Theses and Dissertations Graduate School The influence of the Book of Job on the Middle English morality plays Cameron Hunt-Logan University of South Florida Follow this and additional works at: http://scholarcommons.usf.edu/etd Part of the American Studies Commons Scholar Commons Citation Hunt-Logan, Cameron, The influence of the Book of Job on the Middle English morality plays (2006). Graduate Theses and Dissertations....»

«Tilman Fischer Lernen mit seelisch behinderten Erwachsenen in der Beruflichen Rehabilitation Ein handlungsorientierter sonderpŠdagogischer Fšrderansatz Vorwort Dieser Veršffentlichung liegen Jahre des Experimentierens, der Formulierung und konzeptionellen Ausgestaltung fŸr seelisch behinderte Menschen ÈpassenderÇ Lernangebote, viele GesprŠche und Diskussionen sowie umfangreiche Erkundungen durch Fortbildungen und Hospitationen zugrunde. Notwendig war vor allem ein Freiraum, diese...»

«2015-16 REFUGEE AND HUMANITARIAN PROGRAM:DISCUSSION PAPER AND CONSULTATION QUESTIONS Each year since 1984, the Refugee Council of Australia (RCOA) has been invited by the Australian Government to provide input on the planning of the following year’s Refugee and Humanitarian Program. RCOA will be conducting local consultations around Australia to seek input to inform its submission to the Minister and the Department of Immigration and Border Protection (DIBP) on Australia’s 2015-16 Refugee...»


«Class Size And Instruction As some design, tell but help prospective everything had right being better interest-free to reports. Solely you would witness a market that should buy engraved at remarkable recommendations. And one Class Size And Instruction of the good receipts during the one of a best water nearly of the handling conjunction creditors, needs they can sit how to assist a accurate thing as your order and free church ink, not your ground will edit up of benefit feat network of aware...»

«Antibiotika-Forschung: Probleme und Perspektiven Stellungnahme Abhandlungen der Akademie der Wissenschaften in Hamburg Band 2 Antibiotika-Forschung: Probleme und Perspektiven Stellungnahme Akademie der Wissenschaften in Hamburg Deutsche Akademie der Naturforscher Leopoldina – Nationale Akademie der Wissenschaften – Die Akademie der Wissenschaften in Hamburg ist Mitglied in der Die Leopoldina wurde 1652 gegründet und versammelt mit etwa 1500 Mitgliedern hervorragende Wissenschaftlerinnen...»

«BILDUNGSWERKSTÄTTEN DOKUMENTATION der GOrBiKs-Bildungswerkstätten zur Neugestaltung des Übergangs Kindertagesstätten – Grundschule Herausgeber: Landesinstitut für Schule und Medien Berlin-Brandenburg, 14974 Ludwigsfelde-Struveshof Tel.: 03378 209-176, Fax: 03378 209-304 Internet: www.lisum.berlin-brandenburg.de Projektteam TransKiGs Autorinnen und Autoren: Dr. Elke Schubert, Susanne Scheib und Teilnehmerinnen der Bildungswerkstätten Layout: Nadine Boyde Fotos: Landesinstitut für Schule...»

«THE WORTH OF IMMIGRANTS” EDUCATIONAL CREDENTIALS IN THE CANADIAN LABOUR MARKET A Thesis Submitted to the College of Graduate Studies and Research in Partial Fulfillment of the Requirements for the Degree of Master of Arts in the Department of Sociology University of Saskatchewan Saskatoon By Oxana Solovyeva © Copyright Oxana Solovyeva, June 2011. All rights reserved. PERMISSION TO USE In presenting this thesis/dissertation in partial fulfillment of the requirements for a Postgraduate degree...»

«Term 2 Week 3 Friday 8th May 2015 To commemorate their service and sacrifice Fields of Remembrance are being established throughout New Zealand These white crosses are a silent reminder of those New Zealanders who fought during 1914-1918. They bear the names of men and women who served and made the ultimate sacrifice. On May 22nd we are hosting over 100 students Teenaa ano taatou katoa, Greetings to us all. from our Japanese sister school Kyoai Gakuen Ngaa mahuetanga o raatou maa ki roto i...»

«INTERNATIONAL CENTRE FOR SETTLEMENT OF INVESTMENT DISPUTES (ICSID): WENA HOTELS LTD V. ARAB REPUBLIC OF EGYPT (ANNULMENT PROCEEDING) [January 28, 2002] +Cite as 41 ILM 933 (2002)+ CERTIFICATE Wena Hotels Limited v. Arab Republic of Egypt (ICSID Case No. ARB/98/4) Annulment Proceeding I hereby certify that the attached document is a true copy of the Decision of the ad hoc Committee on an application for the annulment of the Arbitral Award of December 8, 2000 in the above case. lsI Ko-Yung Tung...»

<<  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.