FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 16 |

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

-- [ Page 7 ] --

Thus, (G, s) ∈ d-Clique if and only if (ϕ1,..., ϕt ) ∈ OR(3-Sat). Since G and s are computable in time polynomial in the bitlength of (ϕ1,..., ϕt ) and |V (G)| ≤ 3|V (P )| ≤ O s · max(s, t1/d+o(1) ), we have established the ≤p -reductions claimed in Lemma 3.2.

m Proof based on AP-free sets This section contains the original proof of Lemma 3.2 that appeared in [DvM10]. It is based on high-density subsets of the integers that do not contain arithmetic progressions of length three.

The reduction works by first applying a standard translation of the t individual 3Sat-instances ϕ1,..., ϕt, say of size s, into equivalent d-Clique-instances consisting of d-uniform hypergraphs G1,..., Gt on 3s vertices each, such that Gi has a clique of size s if and only if ϕi is satisfiable. All that is left then is to turn these t instances into a single instance of d-Clique which is positive if and only if at least one of the t instances is. If we take G as the disjoint union of the Gi ’s, then G is a d-uniform hypergraph that has a clique of size s if and only if at least one of the Gi ’s has a clique of size s.

However, this G contains n = 3s · t vertices, which is too many for our purposes. In order to do better, we need to pack the graphs Gi more tightly while maintaining the properties required of the reduction. The following almost-optimal packing of cliques is

3. Communicating Instances of Hard Problems the critical ingredient in the construction and allows us to achieve the almost-optimal lower bounds given in Theorem 1.2.

Lemma 3.3 (Packing Lemma).

For any integers p ≥ d ≥ 2 and t 0 there exists an p-partite d-uniform hypergraph P on O p · max(p, t1/d+o(1) ) vertices such that (i) the hyperedges of P partition into t cliques K1,..., Kt on p vertices each, and (ii) P contains no cliques on p vertices other than the Ki ’s.

Furthermore, for any fixed d, the hypergraph P and the Ki ’s can be constructed in time polynomial in p and t.

Condition (i) in Lemma 3.3 formalizes the notion of a packing. The part that P contains the t cliques Ki ensures the completeness of the reduction, i.e., that G has a clique of size p := s if at least one of the Gi ’s does. The part that the Ki ’s are edge-disjoint and condition (ii) guarantee the soundness of the reduction, i.e., that G has a clique of size s only if at least one of the Gi ’s does.

We defer the proof of Lemma 3.3 to §4. Using it as sketched above we obtain an alternative reduction for Lemma 3.2.

Proof (of Lemma 3.2). Let ϕ1,..., ϕt be the t instances of 3-Sat. Without loss of generality, assume that each formula has exactly p = s clauses, each consisting of a sequence of 3 literals. Let P and K1,..., Kt be the hypergraphs provided by Lemma 3.3.

Along the lines of the standard reduction from 3-Sat to 2-Clique by Karp [Kar72], we first translate the 3-CNF formulas ϕi into d-uniform hypergraphs Gi on the vertex sets V (Ki ) × [3]. For each i, we identify the elements of V (Ki ) × [3] with (positions of) literals of ϕi : The first component selects a clause from ϕi and the second component selects a literal from the clause. We let Gi be the d-uniform hypergraph with as edges all subsets e ⊆ V (Ki ) × [3] of size d such that no two elements of e correspond to the same clause ϕi or represent complementary literals. Note that each such e induces a satisfying assignment of the conjunction of the d clauses touched by e, and that Gi has a clique of size s if and only if ϕi is satisfiable.

Let G be the union of the Gi ’s, that is, the graph with V (G) = i∈[t] V (Gi ) ⊆ V (P ) × [3] and E(G) = i∈[t] E(Gi ). If ϕi has a satisfying assignment, then Gi has a clique of size s and so has G. For the other direction, let K be a clique of size s in G. The projection K of K onto the first component is a clique of size s in P. By property (ii) of Lemma 3.3, K = Ki for some i ∈ [t]. Moreover, by property (i) of Lemma 3.3, the projections of E(Gi ) and E(Gj ) for j = i are disjoint. It follows that K is a clique of size s in Gi, and therefore ϕi is satisfiable.

Thus, (G, s) ∈ d-Clique if and only if (ϕ1,..., ϕt ) ∈ OR(3-Sat). Since G and s are computable in time polynomial in the bitlength of (ϕ1,..., ϕt ) and |V (G)| ≤ 3|V (P )| ≤ O s · max(s, t1/d+o(1) ), we have established the ≤p -reductions claimed in Lemma 3.2.


–  –  –

3.3. Satisfiability Theorem 1.1, our tight oracle communication lower bound for d-Sat parameterized by the number of variables of the formula, immediately follows from Theorem 1.2 and the next lemma.

–  –  –

Proof. Let (G, k) be an n-vertex instance of d-Vertex Cover. The following d-CNF

formula on variables xv for v ∈ V (G) has as satisfying assignments precisely the characteristic vectors of vertex covers of G:

–  –  –

Using at most O(n) new variables, we construct a 3-CNF formula ψ that is satisfied by all assignments in which at most k distinct xv are set to true. Then ϕ ∧ ψ is satisfiable if and only if G has a vertex cover of size at most k.

For the construction of ψ, we use a Boolean circuit of constant fan-in that has at most O(n) gates and checks whether at most k of the n input variables are set to true.

Such circuits can be constructed for any symmetric function in time polynomial in n when given oracle access to the function [Weg87, Theorem 4.1]. Once we have that circuit, we construct ψ in a standard way by introducing a new variable for each gate, and letting ψ be the conjunction of clauses that express the correct behavior of each of the gates, and the clause stipulating that the output gate is set.

Proof (of Theorem 1.1). Suppose there exists an oracle communication protocol of cost O(nd− ) for n-variable instances of d-Sat. We combine the reduction from Lemma 3.4 with the former and obtain an protocol of cost O(nd− ) for n-vertex instances of dVertex Cover. By Theorem 1.2, this implies that coNP ⊆ NP/poly.

The following corollary to Theorem 1.1 embodies the consequences for sparsification, kernelization, and lossy compression.

Corollary 3.1. Let d ≥ 3 be an integer. If coNP ⊆ NP/poly, there is no polynomialtime reduction from d-Sat to any problem that makes at most O(nb ) queries and only queries strings of bitlength O(nc ), where b and c are any nonnegative reals with b+c d.

In particular, under the hypothesis that coNP ⊆ NP/poly, Corollary 3.1 implies that ≤p -reductions cannot reduce the density of n-variable d-Sat instances to O(nc ) clauses m for any constant c below the trivial c = d. This is in contrast to the subexponential-time level: The sparsification lemma of [IPZ01] gives a reduction which, on input an n-variable d-CNF formula and a rational 0, runs in time 2 n · poly(n) and makes 2 n nonadaptive queries, each of which are d-CNF formulas with at most f (d, ) · n clauses. The best known bound on the sparsification constant f (d, ) is (d/ )3d [CIP06]. The sparsification

3. Communicating Instances of Hard Problems

lemma implies that sparse instances of d-Sat are hard under subexponential-time reductions while Corollary 3.1 suggests that such a result is impossible under ≤p -reductions.

m Interpretations of Corollary 3.1 in terms of kernelization and lossy compression follow along the same lines.

Another consequence of Theorem 1.1 deals with the size of probabilistically checkable proofs for satisfiability. Recall that Dinur [Din07] constructed such PCPs of size O(s · poly log s), where s denotes the bitlength of the formula. Based on a connection due to Harnik and Naor [HN06] between PCPs and lossy compression, Fortnow and Santhanam [FS08] showed that satisfiability of Boolean formulas does not have PCPs of size bounded by a polynomial in the number of variables only, unless coNP ⊆ NP/poly.

Plugging in our lower bound for d-Sat into their argument shows that d-Sat does not have q-query PCPs of size O(nd/q− ) unless coNP ⊆ NP/poly. Since q ≥ 3 this bound is not tight. Using a different argument and exploiting the fact that Theorem 1.1 also holds for conondeterministic protocols, we can close the gap between the upper and lower bound.

Corollary 3.2. Let d ≥ 3 be an integer and a positive real. If coNP ⊆ NP/poly, then d-Sat does not have probabilistically checkable proofs of bitlength O(nd− ) where n denotes the number of variables of the input formula.

Proof. Suppose that d-Sat has PCPs of size s = O(nc ) that make q nonadaptive queries, where c and q are constants. We claim that this implies a conondeterministic multivalued mapping reduction from d-Sat to q-Sat that maps formulas on n variables to instances of bitlength O(nc log n) in the following sense: There exists a nondeterministic polynomial-time Turing machine M which outputs a q-CNF formula on each computation path (where the formula may depend on the input and the computation path) such that (i) if the input is in d-SAT then every output is in q-SAT, and (ii) otherwise at least one output is not in q-SAT. For c d, Theorem 1.1 then shows that coNP ⊆ NP/poly.

All that remains is to argue the claim. For a given formula ϕ on n variables, introduce s new variables y, namely one for each bit position in a candidate PCP of size s. If the PCP system reads at most q bits of the proof, each condition the PCP system checks can be expressed efficiently as a q-CNF. By picking a condition according to the distribution of the PCP system and a clause of the corresponding q-CNF formula uniformly at random, we obtain a polynomial-time randomized procedure that produces a q-clause on the variables y with the property that if ϕ is satisfiable, then all q-clauses produced are simultaneously satisfiable, and otherwise less than a constant fraction ρ 1 is. By averaging, the latter implies that for every collection of candidate PCPs of size s for an unsatisfiable input ϕ, there exists a produced q-clause that is violated by more than a fraction 1 − ρ of the collection. Since there are 2s candidate PCPs of size s in total, this means that there is a set of s/ log(1/ρ) produced q-clauses that cannot be satisfied by any PCP of size s. The reduction nondeterministically guesses s/ log(1/ρ) many q-clauses that are produced by the PCP system on input ϕ, and outputs their conjunction. The conjunction has bitlength O(nc log n), is always satisfiable if ϕ is, and is not satisfiable on at least one computation path otherwise.

–  –  –

It is straightforward to obtain applications similar to Corollaries 3.1 and 3.2 for dVertex Cover and other problems.

3.4. Covering Problems Combinatorial covering problems are problems in which we are given a graph and a pattern, and we want to find few vertices that cover each occurrence of the pattern in the graph. Put differently, we want to know whether it is possible to delete k vertices from the graph such that no copies of the respective pattern remain. Clearly d-Vertex Cover is of that kind, since we want to find k vertices whose removal leaves a graph without edges. A natural parameter for d-Vertex Cover and covering problems in general is the size k of the deletion set. We investigate the consequences of Theorem 1.2 for this parameterization of covering problems, first for the case d = 2, i.e., for standard graphs, and then for d-uniform hypergraphs for general d.

Result for Standard Graphs We consider the following generalization of the vertex cover problem. Recall that a graph property is a predicate on graphs that is invariant under graph isomorphism.

Definition 3.1 (Vertex Deletion). Fix a graph property Π. The Π-Vertex Deletion problem is to decide, for a given graph G and integer k, whether there exists a subset S of at most k vertices such that G \ S satisfies Π.

We say that a graph property Π is inherited by subgraphs if, whenever a graph G satisfies Π, every subgraph of G also satisfies Π. The following natural graph problems are special cases of Π-Vertex Deletion for a graph property Π that is inherited by subgraphs.

• Vertex Cover: Can we delete k vertices to destroy all edges?

• Feedback Vertex Set: Can we delete k vertices to destroy all cycles?

• Bounded-Degree Deletion: Can we delete k vertices to get a maximum degree of d?

• Non-Planar Deletion: Can we delete k vertices to make the graph planar?

• Can we delete k vertices to make the graph embeddable into some surface?

• Can we delete k vertices to make the graph exclude any fixed set of minors?

As mentioned in the introduction, if only finitely many graphs satisfy Π or if all graphs satisfy Π, Π-Vertex Deletion is trivially decidable in polynomial time. For all other graph properties Π that are inherited by subgraphs, Theorem 1.3 implies that Π-Vertex Deletion does not have kernels with O(k 2− ) edges unless coNP ⊆ NP/poly.

3. Communicating Instances of Hard Problems

–  –  –

Figure 3.1.

: Replacement of an edge e = {u, v} in the transformation from G to G in the proof of Lemma 3.5. (a) Feedback Vertex Set. (b) Bounded-Degree Deletion. (c) The general case.

We now prove Theorem 1.3 by constructing a ≤p -reduction from Vertex Cover m to Π-Vertex Deletion that blows up the size of the deletion set by no more than a constant factor. In order to develop some intuition, we first consider the standard reduction from Vertex Cover to Feedback Vertex Set [Kar72]. The reduction replaces every edge e of a Vertex Cover-instance G by a cycle of length three using an additional new vertex, as depicted in Figure 3.1a. Let us denote the resulting graph by G. Since every cycle in G contains two vertices that are adjacent in G, every vertex cover of G hits every cycle of G and therefore is a feedback vertex set of G. Conversely, every feedback vertex set of G contains a vertex of every triangle we created, and can therefore be turned into a vertex cover of G of at most the same size. Thus, G has a vertex cover of size k if and only if G has a feedback vertex set of size k.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 16 |

Similar works:

«VOL. 1 ISSUE 5 OCTOBER 2014 ISSN 2349-5650 LITERARY QUEST An International, Peer-Reviewed, Open Access, Monthly, Online Journal of English Language and Literature Indian English Short Story: A Reassessment Dr. Md. Equebal Hussain Associate Professor & Head, Department of English, M.S. College, Motihari, Bihar, India. Abstract Notwithstanding the ancient Indian tradition of story-telling as reflected in Katha Sarit Sagar, the Brihad Katha Manjari or the Panchtantra and the Jatak Tales, the short...»

«Disclaimer: This is a machine generated PDF of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace original scanned PDF. Neither Cengage Learning nor its licensors make any representations or warranties with respect to the machine generated PDF. The PDF is automatically generated AS IS and AS AVAILABLE and are not retained in our systems. CENGAGE LEARNING AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS...»

«New York City Guide 2015 Jericho Public Library Jericho Public Library One Merry Lane Jericho, NY 11753 (516) 935-6790 www.jericholibrary.org New York City 2015 This guide has been prepared by your public library as a service to the community. We hope that residents will find it useful. The information included is accurate as of May 2015. Phone numbers have been furnished so that you have the option of calling ahead and confirming the data we have provided. Changes occur constantly. The...»

«A Faithful Mirror Reflections On The College Board And Education In America Wanting the Porsche nasc Estate Nebraska India Gantt is the online agent to use product that standing monthly and guest check for this Washington and united area local bank name engines. Analysis family earnings will result discussed and scout the transactions to rather be and optimize years. Over all this crating because the rate it would grab able mistake or higher. Receive to ask as conventional amount of a important...»

«Engagierte Jugend – lebendige Gesellschaft Expertise zum Carl Bertelsmann-Preis 2007 Richard M. Lerner, Amy E. Alberts und Deborah L. Bobek | Seite 2 Engagierte Jugend – lebendige Gesellschaft Möglichkeiten zur Stärkung von Demokratie und sozialer Gerechtigkeit durch positive Jugendentwicklung Aus dem Amerikanischen von Dr. Janina Gatzky Autoren: Richard M. Lerner, Amy E. Alberts, und Deborah L. Bobek Institute for Applied Research in Youth Development Tufts University Medford, MA 02113...»

«IFM-GEOMAR REPORT RV Poseidon POS389 & POS393 & RV Maria S. Merian MSM15/5 TOPO-MED Topographic, structural and seismotectonic consequences of plate re-organization in the Gulf of Cadiz and Alboran Sea – POS389: Valletta, Malta – Malaga, Spain 06.–17.08.2009 POS393: Malaga, Spain – Faro, Portugal 14.–24.01.2010 MSM15/5: Valletta, Malta Rostock, Germany 17.–29.07.2010 Berichte aus dem Leibniz-Institut für Meereswissenschaften an der Christian-Albrechts-Universität zu Kiel Nr. 45...»

«Hausbesetzungen und Repression Ein kleiner Ratgeber für die Praxis „When they kick out your front door, how you're gonna go with your hands on your head or on the trigger of your gun.“ The Clash – Guns of Brixton Rote Hilfe Ortsgruppe Potsdam 1 von 20 Impressum Herausgegeben von der Roten Hilfe e.V. Ortsgruppe Potsdam; mit freundlicher Genehmigung einiger Textinhalte und Layout durch die Ortsgruppe Frankfurt/Main August 2013 V.i.S.d.P. H.Lange PF 3255 37022 Göttingen Bilder haben wir...»


«Der Senat 17. März 2016 Stellungnahme zum Leibniz-Institut für Gemüseund Zierpflanzenbau, Großbeeren / Erfurt e.V. (IGZ) Inhaltsverzeichnis 1. Beurteilung und Empfehlungen 2. Zur Stellungnahme des IGZ 3. Förderempfehlung Anlage A: Darstellung Anlage B: Bewertungsbericht Anlage C: Stellungnahme der Einrichtung zum Bewertungsbericht Stellungnahme zum IGZ Die Einrichtungen der Forschung und der wissenschaftlichen Infrastruktur, die sich in Vorbemerkung der Leibniz-Gemeinschaft...»

«TÖRTÉNELEM DOKTORI PROGRAM KUTATÁSI FÜZETEK Pordán Ildikó László Károly beszámolója Kossuth amerikai útjáról A Kutatási Füzetek a Janus Pannonius Tudományegyetem Európa és Magyarország a 19-20. században című történelem doktori (Ph.D.) programjának sorozata. Szerkesztők Ormos Mária Harsányi Iván Flodung János Soós Gábor Janus Pannonius Tudományegyetem Pécs, 1996 TARTALOM László Károly és naplója Kossuth Amerikában László Károly naplója Kossuth...»

«BAY OF BENGAL PROGRAMME BOBP/WP/85 Post-Harvest Fisheries Overseas Development Administration The processing and marketing of Anchovy in the Kanniyakumari District of South India Scope for development by T W Bostock Post-Harvest Adviser, BOBP/ODA, Madras M H Kalavathy Consultant Sociologist, BOBP/ODA, Madras R Vijaynidhi Consultant Marketing Adviser, KDFSF, Nagercoil The Bay of Bengal Programme’s Post-Harvest Fisheries Project in collaboration with Kanyakumari District Fishermen’s Sangams...»

«ISSN 1605-7678 РОССИЙСКАЯ АКАДЕМИЯ НАУК ТРУДЫ РУССКОГО ЭНТОМОЛОГИЧЕСКОГО ОБЩЕСТВА Том 83(2) К.Г. Михайлов  Bibliographia Araneologica Rossica 1770–2011 Санкт-Петербург Труды Русского энтомологического общества. Т. 83(2): Михайлов К.Г. Bibliographia Araneologica Rossica 1770-2011. С.-Петербург, 2012. 229 с. Proceedings of the Russian Entomological...»

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