FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 8 | 9 || 11 |

«A Tractable hypergraph properties for constraint satisfaction and conjunctive queries1 D´niel Marx, Computer and Automation Research Institute, ...»

-- [ Page 10 ] --

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:40 D. Marx To bound the edge depth of the embedding φ, consider an edge e. The total weight of the paths intersecting e is at most 1 and a path with weight w is used in the image of at most 2(q/ ) · w vertices. Each path intersects e in at most 2 vertices (as we can assume that the paths appearing in the flows are minimal), thus a path with weight w contributes at most 4(q/ ) · w to the depth of e. Thus the edge depth of φ is at most √ 3 1 4(q/ ) = O(m/(λ k)) = O(m/(λ 2 conλ (H) 4 )).

6.3. Connection with adaptive width As an easy consequence of the embedding result Corollary 6.2, we can show that large

submodular width implies large adaptive width:

Lemma 6.9.

For every hypergraph H, adw(H) = Ω(emb(H)).

Proof. Suppose that emb(H) α. This means that there is an integer mα such that every graph with m ≥ mα edges has an embedding into H with edge depth m/α. It is wellknown that there are arbitrarily large sparse graphs whose treewidth is linear in the number of vertices (for example, bounded-degree expanders, see e.g., [Grohe and Marx 2009]): for some universal constant β, there is a graph G with m ≥ mα edges and treewidth at least βm. Thus there is an embedding φ from G to H with edge depth at most q ≤ m/α. Let d(v) be the depth of vertex v in the embedding and let us define µ(v) := d(v)/q. From the definition of edge depth, it is clear that µ is a fractional independent set. Suppose that there is a tree decomposition (T, Bv∈V (T ) ) of H having µ-width w. This tree decomposition can be turned into a tree decomposition (T, Bv∈V (T ) ) of G: for every Bt ⊆ V (H), let Bt := {u ∈ V (G) | φ(u) ∩ Bt = ∅} contain those vertices of G whose images intersect Bt.

Now µ(Bt ) ≤ w means that v∈Bt d(v) ≤ qw, which implies that |Bt | ≤ qw. Thus the width of (T, Bv∈V (T ) ) is less than qw, which means that w has to be at least βm/q = Ω(α), the required lower bound on the adaptive width of H.

Combining Theorem 5.1 and Lemma 6.9 gives:

Corollary 6.10. For every hypergraph H, subw(H) = O(adw(H)4 ).


We prove the main hardness result of the paper in this section:

Theorem 7.1.

Let H be a recursively enumerable class of hypergraphs with unbounded submodular width. If there is an algorithm A and a function f such that A solves every 1/4 instance I of CSP(H) with hypergraph H ∈ H in time f (H) · I o(subw(H) ), then the Exponential Time Hypothesis fails.

In particular, Theorem 7.1 implies that CSP(H) for such a H is not fixed-parameter


Corollary 7.2. If H is a recursively enumerable class of hypergraphs with unbounded submodular width, then CSP(H) is not fixed-parameter tractable, unless the Exponential Time Hypothesis fails.

The Exponential Time Hypothesis (ETH) states that there is no 2o(n) time algorithm for n-variable 3SAT. The Sparsification Lemma of Impagliazzo et al. [2001] shows that ETH is equivalent to the assumption that there is no algorithm for 3SAT whose running time is subexponential in the number of clauses. This result will be crucial for our hardness proof, as our reduction from 3SAT is sensitive to the number of clauses.

Theorem 7.3 (Impagliazzo et al.

[2001]). If there is a 2o(m) time algorithm for mclause 3SAT, then there is a 2o(n) time algorithm for n-variable 3SAT.

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:41 To prove Theorem 7.1, we show that a subexponential-time algorithm for 3SAT exists if CSP(H) can be solved “too fast” for some H with unbounded submodular width. We use the characterization of submodular width from Section 5 and the embedding results of Section 6 to reduce 3SAT to CSP(H) by embedding the incidence graph of a 3SAT formula into a hypergraph H ∈ H. The basic idea of the proof is that if the 3SAT formula has m clauses and the edge depth of the embedding is m/r, then we can gain a factor r in the exponent of the running time. If submodular width is unbounded in H, then we can make this gap r between the number of clauses and the edge depth arbitrary large, and hence the exponent can be arbitrarily smaller than the number of clauses, i.e., the algorithm is subexponential in the number of clauses.

The following simple lemma from [Marx 2010b] gives a transformation that turns a 3SAT instance into a binary CSP instance. We include the proof for completeness.

Lemma 7.4.

Given an instance of 3SAT with n variables and m clauses, it is possible to construct in polynomial time an equivalent CSP instance with n + m variables, 3m binary constraints, and domain size 3.

Proof. Let φ be a 3SAT formula with n variables and m clauses. We construct an instance of CSP as follows. The CSP instance contains a variable xi (1 ≤ i ≤ n) corresponding to the i-th variable of φ and a variable yj (1 ≤ j ≤ m) corresponding to the j-th clause of φ. Let D = {1, 2, 3} be the domain. We try to describe a satisfying assignment of φ with these n + m variables. The intended meaning of the variables is the following. If the value of variable xi is 1 (resp., 2), then this represents that the i-th variable of φ is true (resp., false). If the value of variable yj is, then this represents that the j-th clause of φ is satisfied by its -th literal. To ensure consistency, we add 3m constraints. Let 1 ≤ j ≤ m and 1 ≤ ≤ 3, and assume that the -th literal of the j-th clause is a positive occurrence of the i-th variable. In this case, we add the binary constraint (xi = 1 ∨ yj = ): either xi is true or some other literal satisfies the clause. Similarly, if the -th literal of the j-th clause is a negated occurrence of the i-th variable, then we add the binary constraint (xi = 2 ∨ yj = ).

It is easy to verify that if φ is satisfiable, then we can assign values to the variables of the CSP instance such that every constraint is satisfied, and conversely, if the CSP instance has a solution, then φ is satisfiable.

Next we show that an embedding from graph G to hypergraph H can be used to simulate a binary CSP instance I1 having primal graph G by a CSP instance I2 whose hypergraph is H. The domain size and the size of the constraint relations of I2 can grow very large in this transformation: the edge depth of the embedding determines how large this increase is.

Lemma 7.5.

Let I1 = (V1, D1, C1 ) be a binary CSP instance with primal graph G and let φ be an embedding of G into a hypergraph H with edge depth q. Given I1, H, and the embedding φ, it is possible to construct (in time polynomial in the size of the output) an equivalent CSP instance I2 = (V2, D2, C2 ) with hypergraph H where the size of every constraint relation is at most |D1 |q.

Proof. For every v ∈ V (H), let Uv := {u ∈ V (G) | v ∈ φ(u)} be the set of vertices in G whose images contain v, and for every e ∈ E(H), let Ue := v∈e Uv. Observe that for every e ∈ E(H), we have |Ue | ≤ v∈e |Uv | ≤ q, since the edge depth of φ is q. Let D2 be the set of integers between 1 and |D1 |q. For every v ∈ V (H), the number of assignments from Uv to D1 is clearly |D1 ||Uv | ≤ |D1 |q. Let us fix a bijection hv between these assignments on Uv and the set {1,..., |D1 ||Uv | } ⊆ D2.

The set C2 of constraints of I2 are constructed as follows. For each e ∈ E(H), there is a constraint se, Re in C2, where se is an |e|-tuple containing an arbitrary ordering of the elements of e. The relation Re is defined the following way. Suppose that vi is

–  –  –

where the last inequality follows from the fact that φ has edge depth at most q.

To prove that I1 and I2 are equivalent, assume first that I1 has a solution f1 : V1 → D1.

For every v ∈ V2, let us define f2 (v) := hv (prUv f2 ), that is, the integer between 1 and |D1 ||Uv | corresponding to the projection of assignment f2 to Uv. It is easy to see that f2 is a solution of I2.

Assume now that I2 has a solution f2 : V2 → D2. For every v ∈ V (H), let fv := h−1 (f2 (v)) v be the assignment from Uv to D1 that corresponds to f2 (v) (note that by construction, f2 (v) is at most |D1 ||Uv |, hence h−1 (f2 (v)) is well-defined). We claim that these assignments are v compatible: if u ∈ Uv ∩ Uv for some u ∈ V (G) and v, v ∈ V (H), then fv (u) = fv (u).

Recall that φ(u) is a connected set in H, hence there is a path between v and v in φ(u).

We prove the claim by induction on the distance between v and v in φ(u). If the distance is 0, that is, v = v, then the statement is trivial. Suppose now that the distance of v and v is d 0. This means that v has a neighbor z ∈ φ(u) such that the distance of z and v is d − 1. Therefore, fz (u) = fv (u) by the induction hypothesis. Since v and z are adjacent in H, there is an edge E ∈ E(H) containing both v and z. From the way I2 is defined, this means that fv and fz are compatible and fv (u) = fz (u) = fv (u) follows, proving the claim. Thus the assignments {fv | v ∈ V (H)} are compatible and these assignments together define an assignment f1 : V (G) → D. We claim that f1 is a solution of I1. Let c = (u1, u2 ), R be an arbitrary constraint of I1. Since u1 u2 ∈ E(G), sets φ(u1 ) and φ(u2 ) touch, thus there is an edge e ∈ E(H) that contains a vertex v1 ∈ φ(u1 ) and a vertex v2 ∈ φ(u2 ) (or, in other words, u1 ∈ Uv1 and u2 ∈ Uv2 ). The definition of ce in I2 ensures that f1 restricted to Uv1 ∪ Uv2 satisfies every constraint of I1 whose scope is contained in Uv1 ∪ Uv2 ; in particular, f1 satisfies constraint c.

Now we are ready to prove Theorem 7.1, the main result of the section. We show that if there is a class H of hypergraphs with unbounded submodular width such that CSP(H) is FPT, then this algorithm can be used to solve 3SAT in subexponential time. The main ingredients are the embedding result of Theorem 6.1, and Lemmas 7.4 and 7.5 above on reduction to CSP. Furthermore, we need a way of choosing an appropriate hypergraph from the set H. As discussed earlier, the larger the submodular width of the hypergraph is, the more we gain in the running time. However, we should not spend too much time on constructing the hypergraph and on finding an embedding. Therefore, we use the same technique as in [Marx 2010b]: we enumerate a certain number of hypergraphs and we try all of them simultaneously. The number of hypergraphs enumerated depends on the size of the 3SAT instance. This will be done in such a way that guarantees that we do not spend

–  –  –

= f2 (H, λ) · mO(1) · 3cλ m/ι(k) for an appropriate function f2 (H, λ) depending only on H and λ.

Algorithm B for 3SAT proceeds as follows. Let us fix an arbitrary computable enumeration H1, H2,... of the hypergraphs in H. Given an m-clause 3SAT formula I, algorithm B spends the first m steps on enumerating these hypergraphs; let H be the last hypergraph produced by this enumeration (we assume that m is sufficiently large that ≥ 1). Next we start simulating the algorithms A[I, H1 ], A[I, H2 ],..., A[I, H ] in parallel. When one of the simulations stops and returns an answer, then we stop all the simulations and return the answer. It is clear that algorithm B will correctly decide the satisfiability of I.

We claim that there is a universal constant d such that for every s, there is an ms such that for every m ms, the running time of B is at most (m · 2m/s )d on an m-clause formula.

Clearly, this means that the running time of B is 2o(m).

For any positive integer s, let ks be the smallest positive integer such that ι(ks ) ≥ s (as ι is unbounded, this is well defined). Let is be the smallest positive integer such that subw(His ) ≥ ks (as H has unbounded submodular width, this is also well defined). Set ms sufficiently large that ms ≥ f2 (His, λ) and the fixed enumeration of H reaches His in less then ms steps. This means that if we run B on a 3SAT formula I with m ≥ ms clauses, then ≥ is and hence A[I, His ] will be one of the simulations started by B. The simulation of A[I, His ] terminates in f2 (His, λ)mO(1) · 3cλ m/ι(subw(His )) ≤ m · mO(1) · 3cλ m/s steps. Taking into account that we simulate ≤ m algorithms in parallel and all the simulations are stopped not later than the termination of A[I, His ], the running time of B can Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:44 D. Marx be bounded polynomially by the running time of A[I, His ]. Therefore, there is a constant d such that the running time of B is at most (m · 2m/s )d, as required.

Remark 7.6.

Recall that if φ is an embedding of G into H, then the depth of an edge e ∈ E(H) is dφ (e) = v∈V (G) |φ(v) ∩ e|. A variant of this definition would be to define the depth of e as dφ (e) = |{v ∈ V (G) | φ(v)∩e = ∅}|, i.e., if φ(v) intersects e, then v contributes only 1 to the depth of e, not |φ(v) ∩ e| as in the original definition. Let us call this variant weak edge depth, it is clear that the weak edge depth of an embedding is at most the edge depth of the embedding.

Lemma 7.5 can be made stronger by requiring only that the weak edge depth is at most q.

Indeed, the only place where we use the bound on edge depth is in Inequality (4). However, the size of the relation Re can be bounded by the number of possible assignments on Ue in instance I1. If weak edge depth is at most q, then |Ue | ≤ q, and the |D1 |q bound on the size of Re follows.

Remark 7.7.

Pages:     | 1 |   ...   | 8 | 9 || 11 |

Similar works:

«Culture and the Evolution of the Human Social Instincts R. Boyd (UCLA) and P. J. Richerson (University of California, Davis) Forthcoming in: Roots of Human Sociality, S. Levinson and N. Enfield, eds., Berg, Oxford. Human societies are extraordinarily cooperative compared to those of most other animals. In the vast majority of species, individuals live solitary lives, meeting to only to mate and, sometimes, raise their young. In social species, cooperation is limited to relatives and (maybe)...»

«SPAY014—July 2003 White Paper Enhancing Cable Modem TCP Performance Lior Storfer Cable Broadband Communications Group, Texas Instruments Abstract Industry standard Data Over Cable Service Interface Specification (DOCSIS™) cable modems provide end users with an always-on, broadband connection to the Internet. Most applications delivered via that high-speed connection are transmitted via transmission control protocol (TCP). The interaction that takes place between TCP and the DOCSIS-defined...»

«ALFRED KRÖNER VERLAG Leseprobe Einleitung Wege zu den Phöniziern »Diesem Volk, das sich gehaßt fühlte, lagen sein Geld und seine Götter am Herzen, und seine Vaterlandsliebe wurde durch die Art seiner Regierung genährt.« So äußerte sich, vor bald 150 Jahren, Gustave Flaubert in seinem Historienroman Salammbô über die Karthager – und bediente damit großzügig das gängige Klischee vom levantinischen Händler: In jedem Phönizier und Punier wohne eine Krämerseele, ergeben dem Luxus...»

«This document is scheduled to be published in the Federal Register on 09/19/2016 and available online at https://federalregister.gov/d/2016-22498, and on FDsys.gov 6560-50-P ENVIRONMENTAL PROTECTION AGENCY [EPA-HQ-OW-2016-0404; FRL-9952-57-OW] Proposed Collection; Comment Request; Proposed Information Collection Request for the National Study of Nutrient Removal and Secondary Technologies: Publicly Owned Treatment Works (POTW) Screener Questionnaire AGENCY: Environmental Protection Agency...»

«SUSTAINABLE FISHERIES MANAGEMENT PROJECT (SFMP) Gender Needs Assessment Report JUNE 2015 This publication is available electronically on the Coastal Resources Center’s website at http://www.crc.uri.edu/projects_page/ghanasfmp/ For more information on the Ghana Sustainable Fisheries Management Project, contact: USAID/Ghana Sustainable Fisheries Management Project Coastal Resources Center Graduate School of Oceanography University of Rhode Island 220 South Ferry Rd. Narragansett, RI 02882 USA...»

«TIGERS BE STILL By Kim Rosenstock PRODUCED BY THE PUBLIC THEATRE JANUARY, 2014 A Study Guide By Martin Andrucki Charles A. Dana Professor of Theater Bates College THE AUTHOR. Kim Rosenstock studied playwriting at Yale Drama School. In addition to Tigers Be Still, she is the author of Fly by Night, a musical. She has also written for the hit television comedy series, New Girl. About Tigers Be Still she has said, “I guess I am interested in depicting what I call ‘the void’—the dark place...»

«Eigendom von het We$tvlacms Ekonomisch Studiebureau Brugge Reeks / Boek ADVANCES IN F IS H E R IE S OF MAHARASHTRA C H IEF M IN IST E R M AHARASHTRA FISH— A VERY VALUABLE FOOD J A M glad to know that the Fisheries in Maharashtra are *making good progress and recent advances are being printed in this brochure. Fish is a very valuable food at all times but particularly now when we are passing through a period o f food-shortages. I f therefore fisheries, which have great possibilities, are...»

«SUPREME COURT OF THE STATE OF NEW YORK — NEW YORK COUNTY PRESENT: Hon. Arthur F. Engoron PART 37 Justice PETER ROSADO, 157674/13 INDEX NO. Plaintiff, 11/7/13 MOTION DATE MOTION SEQ. NO.-vDECISION AND ORDER DAILY NEWS, L.P., Defendant. The following papers, numbered 1 to 3, were read on this motion, pursuant to CPLR 3211(a)(1) and (7), to dismiss. ▌PAPERS NUMBERED Moving Papers ▌ 1 ▌ Opposition Papers ▌ 2 ▌ Reply Papers ▌ 3 Upon the foregoing papers, the instant motion is granted...»

«MEMBERS OF TURKISH DELEGATION TO TURKEY –EU JOINT PARLIAMENTARY COMMITTEE Updated: 09.09.2009 MEMBERS OF TURKISH DELEGATION TO TURKEY-EU JOINT PARLIAMENTARY COMMITTEE Members Party Constituency Mr. Yaşar YAKIŞ Co-Chairman AK Parti (JDP) Düzce Mr. Lütfi ELVAN Vice Co-Chairman AK Parti (JDP) Karaman Mr. Onur ÖYMEN Vice Co-Chairman CHP (RPP) Bursa Ms. Fazilet DAĞCI ÇIĞLIK Vice Co-Chairman AK Parti(JDP) Erzurum Mr. Osman ÇAKIR Vice Co-Chairman MHP (NMP) Samsun Mr. Burhan KAYATÜRK Member...»

«9 Poetic Pedantry or Pastoral Passion: Olney Hymns and John Newton's Old Testament Hermeneutic Daniel Szczesniak Introduction Hymns authored by John Newton have permeated nearly every hymnal since his only foray into hymnody, Olney Hymns, which he authored along with William Cowper, appeared in 1779. Hailed as ‘one of the most substantial achievements of eighteenth-century hymnology’,1 Newton’s texts from Olney Hymns, such as “Glorious things of Thee are spoken”, “How sweet the name...»

«Loughborough University Institutional Repository The eect of authority on the persuasiveness of mathematical arguments This item was submitted to Loughborough University's Institutional Repository by the/an author. INGLIS, M. and MEJIA-RAMOS, J.P. 2009. The eect of authority Citation: on the persuasiveness of mathematical arguments. Cognition and Instruction, 27 (1), pp. 25-50.Additional Information: • This is an electronic version of an article published in the journal, Cognition and...»

«1 Phytoplankton and heterotrophic respiration in the surface layer of the ocean John Marra1 and Richard T. Barber2 Lamont-Doherty Earth Observatory of Columbia University, Palisades, NY 10964 USA/ Duke University Nicholas School of the Environment and Earth Sciences, Beaufort, NC 28516 USA Abstract We suggest a way to estimate phytoplankton respiration separately from heterotrophic respiration. The analysis is based on three previous observations: (1) that carbon loss in the plankton overnight...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

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.