FREE ELECTRONIC LIBRARY - Abstracts, online materials

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

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

-- [ Page 7 ] --

Let directed graph D be the orientation of the primal graph of H such that if vi and vj are adjacent and i j, then there is a directed edge −→ in D. Figure 3 shows a directed v− j iv

–  –  –

Fig. 4. Proof of Claim 2: Two examples of directed paths where every vertex has the same class κ (and h := 2−κ ). The shaded lines show the offsets of the vertices.

path in D. If P is a directed path in D, then the width of P is the length of the interval v∈P ι(v) (note that by Claim 1, this union is indeed an interval). The following claim

bounds the maximum possible width of a directed path:

Claim 2. If P is a directed path D starting at v, then the width of P is at most 16x(v).

Proof. We first prove that if every vertex of P has the same class κ(v), then the width of P is at most 4 · 2−κ(v). Since the class is nondecreasing along the path, we can partition the path into subpaths such that every vertex in a subpath has the same class and the classes are distinct on the different subpaths. The width of P is at most the sum of the widths of the subpaths, which is at most i≥κ(v) 4 · 2−i = 8 · 2−κ(v) ≤ 16x(v).

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

A:28 D. Marx Suppose now that every vertex of P has the same class κ(v) as the first vertex v and let h := 2−κ(v). As the offset is nondecreasing, path P can be partitioned into two parts: a subpath P1 containing vertices with offset less than h, followed by a subpath P2 containing vertices with offset at least h (one of P1 and P2 can be empty). See Figure 4 for examples.

We show that each of P1 and P2 has width at most 2h, which implies that the width of P is at most 4h. Observe that if u ∈ P1 and ι(u) contains a point i · 2h − h for some integer i, then, considering x(u) ≤ h and the bounds on the offset of u, this is only possible if ι(u) = [i · 2h − h, i · 2h], i.e., i · 2h − h is the left endpoint of ι(u). Thus if I1 = u∈P1 ι(u) contains i · 2h − h, then it is the left endpoint of I1. Therefore, I1 can contain i · 2h − h for at most one value of i, which immediately implies that the length of I1 is at most 2h.

We argue similarly for P2. If u ∈ P2, then ι(u) can contain the point i · 2h only if ι(u) = [i · 2h, i · 2h + h]. Thus if I2 = u∈P2 ι(u) contains i · 2h, then it is the left endpoint of I2. We get that I2 can contain i · 2h for at most one value of i, which immediately implies that the width of I2 is at most 2h. This concludes the proof of Claim 2.

Let c(v) := ∂bπ (v).

–  –  –

Proof. Let us examine the contribution of an edge e ∈ E(H) with value s(e) to the sum.

For every vertex v ∈ e, edge e increases the value x(v) by at most s(e) (the contribution may be less than s(e), since we defined x(v) to be at most 1). Thus the total contribution of edge e is at most

–  –  –

where the first inequality follows Prop. 5.2(5); the last equality follows form Prop. 5.2(3);

the last inequality follows from the fact that b is edge dominated. Therefore, v∈V (H) x(v)c(v) ≤ e∈E(H) s(e) ≤ w, proving Claim 3.

Let S be a set of vertices. We define S to be the “inneighbor closure” of S, that is, the set of all vertices from which a vertex of S is reachable on a directed path in D (in particular, this means that S ⊆ S).

–  –  –

Let S(t) be the set of all vertices v ∈ V (H) for which t ∈ ι(v). Observe that for every 0 ≤ t ≤ 1, the set S(t) (and hence S(t)) separates X from Y. We use an averaging argument to show that there is a 0 ≤ t ≤ 1 for which bπ (S(t)) is O(w). As b∗ (S(t)) ≤ bπ (S(t)) by definition, the set S(t) satisfies the requirement of the lemma.

If we are able to show that 0 bπ (S(t))dt = O(w), then the existence of the required t clearly follows. Let Iv (t) = 1 if v ∈ S(t) and let Iv (t) = 0 otherwise. If Iv (t) = 1, then there is a path P in D from v to a member of S(t). By Claim 2, the width of this path is at most

–  –  –

(we used Claim 4 in the first equality and Claim 3 in the last inequality).

Although it is not used in this paper, we can prove the converse of Theorem 5.7 in a very simple way.

Theorem 5.8.

Let H be a hypergraph, and let X, Y ⊆ V (H) be two sets of vertices.

Suppose that for every edge-dominated monotone submodular function b on H with b(∅) = 0, there is an (X, Y )-separator S with b(S) ≤ w. Then there is a fractional (X, Y )-separator of weight at most w.

Proof. If there is no fractional (X, Y )-separator of weight at most w, then by LP duality, there is an (X, Y )-flow F of value greater than w. Let b(Z) be defined as the total weight of the paths in F intersecting Z; it is easy to see that f is a monotone submodular function, and since F is a flow, b(e) ≤ 1 for every e ∈ E(H). Thus by assumption, there is an (X, Y )separator S with b(S) ≤ w. However, every X − Y path of F intersects (X, Y )-separator S, which implies b(S) w, a contradiction.

The problem of finding a small separator in the sense of Theorem 5.7 might seem related to submodular function minimization at a first look. We close this section by pointing out that finding an (A, B)-separator S with b(S) small for a given submodular function b is not an instance of submodular function minimization, and hence the well-known algorithms (see [Iwata 2008; Iwata et al. 2001; Schrijver 2000]) cannot be used for this problem. If a submodular function g(X) describes the weight of the boundary of X, then finding a small (A, B)-separator is equivalent to minimizing g(X) subject to A ⊆ X, X ∩ B = ∅, which can be expressed as an instance of submodular function minimization (and hence solvable in polynomial time). In our case, however, b(S) is the weight of S itself, which means that we have to minimize g(S) subject to S being an (A, B)-separator and this latter constraint cannot be expressed in the framework of submodular function minimization. A possible workaround is to define δ(X) as the neighborhood of X (the set of vertices outside X adjacent to X) and b (X) := b(δ(S)); now minimizing b (X) subject to A ⊆ X ∪ δ(X), X ∩ B = ∅ is the same as finding an (X, Y )-separator S minimizing b(S). However, the function b is not necessarily a submodular function in general. Therefore, transforming b to b this way does not lead to a polynomial-time algorithm using submodular function minimization. In fact, it is quite easy to show that finding an (A, B)-separator S with b(S) minimum possible can be an NP-hard problem even if b is a submodular function of very simple form.

Theorem 5.9.

Given a graph G, subsets of vertices X, Y, and collection S of subsets of vertices, it is NP-hard to find an (X, Y )-separator that intersects the minimum number of members of S.

Proof. The proof is by reduction from 3-coloring. Let H be a graph with n vertices and m edges; we identify the vertices of H with the integers from 1 to n. We construct a graph G consisting of 3n + 2 vertices, vertex sets X, Y, and a collection S of 6m sets such that there is an (X, Y )-separator S in G intersecting at most 3m members of S if and only if H is 3-colorable.

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

A:30 D. Marx The graph G consists of two vertices x, y, and for every 1 ≤ i ≤ n, a path xvi,1 vi,2 vi,3 y of length 4 connecting x and y. The collection S is constructed such that for every edge ij ∈ E(H) and 1 ≤ a, b ≤ 3, a = b, there is a corresponding set {vi,a, vj,b, x, y}. Let X := {x} and Y := {y}. Observe that the set {vi,a, vj,b } intersects exactly 3 sets of S if a = b and exactly 4 sets of S if a = b.

Let c : V (H) → {1, 2, 3} be a 3-coloring of H. The set S = {vi,c(i) | 1 ≤ i ≤ n} is clearly an (X, Y )-separator. For every ij ∈ E(H), separator S intersects only 3 of the 6 sets {vi,a, vi,b, x, y}. Therefore, S intersects exactly 3m members of S.

Consider now an (X, Y )-separator S intersecting at most 3m members of S. Since every member of S contains both x and y, it follows that x, y ∈ S. Thus S has to contain at least one internal vertex of every path xvi,1 vi,2 vi,3 y. For every 1 ≤ i ≤ n, let us fix a vertex vi,c(i) ∈ S. We claim that c is a 3-coloring of H. For every ij ∈ E(H), S intersects at least 3 of the sets {vi,a, vi,b, x, y}, and intersects 4 of them if c(i) = c(j). Thus the assumption that S intersects at most 3m members of S immediately implies that c is a proper 3-coloring.

5.3. Obtaining a highly connected set The following lemma is the same as the main result of Section 5 (Theorem 5.1) we are trying to prove, with the exception that b-width is replaced by b∗ -width. By Prop 5.2(2), b∗ (S) ≥ b(S) for every set S ⊆ V (H), thus b∗ -width is not less than b-width. Therefore, the following is actually a stronger statement and immediately implies Theorem 5.1.

Lemma 5.10.

For every sufficiently small constant λ 0, the following holds. Let b be an edge-dominated monotone submodular function of H with b(∅) = 0. If the b∗ -width of H is greater than 3 (w + 1), then conλ (H) ≥ w.

Proof. Suppose that λ 1/c, where c is the universal constant of Lemma 5.7 hidden by the big-O notation. Suppose that conλ (H) w, that is, there is no fractional independent set µ and (µ, λ)-connected set W with µ(W ) ≥ w. We show that H has a tree decomposition

of b∗ -width at most 2 (w + 1), or more precisely, we show the following stronger statement:

For every subhypergraph H of H and every W0 ⊆ V (H ) with b∗ (W0 ) ≤ w + 1, there is a tree decomposition of H having b∗ -width at most 2 (w + 1) such that W0 is contained in one of the bags.

We prove this statement by induction on |V (H )|. If b∗ (V (H )) ≤ 2 (w + 1), then a decomposition consisting of a single bag proves the statement. Otherwise, let W be a superset of W0 such that w ≤ b∗ (W ) ≤ w + 1; let us choose a W that is inclusionwise maximal with respect to this property. Observe that there has to be at least one such set: from the fact that b∗ (v) ≤ 1 for every vertex v and from Prop. 5.2(6), we know that adding a vertex increases b∗ (W ) by at most 1. Since b∗ (V (H )) ≥ 2 (w + 1), by adding vertices to W0 in an ∗ arbitrary order, we eventually find a set W with b (W ) ≥ w, and the first such set satisfies b∗ (W ) ≤ w + 1 as well.

Let π be an ordering of V (H ) such that bπ (W ) = b∗ (W ). As in Lemma 5.3, let us define the fractional independent set µ by µ(v) := ∂bπ,W (v) if v ∈ W and µ(v) = 0 otherwise.

Clearly, we have µ(W ) = bπ (W ) = b∗ (W ) ≥ w.

By assumption, W is not (µ, λ)-connected, hence there are disjoint sets A, B ⊆ W and a fractional (A, B)-separator of weight less than λ · min{µ(A), µ(B)}. Thus by Theorem 5.7, there is an (A, B)-separator S ⊆ V (H ) with b∗ (S) c · λ · min{µ(A), µ(B)} min{µ(A), µ(B)} ≤ µ(W )/2 ≤ (w + 1)/2 (the second inequality follows from the fact that A and B are disjoint subsets of W ). Let C1,..., Cr be the connected components of H \ S;

by Lemma 5.6, b∗ ((Ci ∩ W ) ∪ S) µ(W ) = bπ (W ) = b∗ (W ) ≤ w + 1 for every 1 ≤ i ≤ r.

As b∗ (V (H )) ≥ 3 (w + 1) and b∗ (S) ≤ (w + 1)/2, it is not possible that S = V (H ), hence r 0. It is not possible that r = 1 either: (C1 ∩ W ) ∪ S is a proper superset of W with Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:31 b∗ -value strictly less than b∗ (W ) ≤ w + 1, and (as b∗ (V (H )) ≥ 2 (w + 1)) we could find a set between (C1 ∩ W ) ∪ S and V (H ) contradicting the maximality of the choice of W.

Thus r ≥ 2, which means that each hypergraph Hi := H [Ci ∪ S] has strictly fewer vertices than H for every 1 ≤ i ≤ r.

By the induction hypothesis, each Hi has a tree decomposition Ti having b∗ -width at most 3 (w + 1) such that Wi := (Ci ∩ W ) ∪ S is contained in one of the bags. Let Bi be the bag of Ti containing Wi. We build a tree decomposition T of H by joining together the tree decompositions T1,..., Tr : let B0 := W0 ∪ S be a new bag that is adjacent to bags B1,..., Br. It can be easily verified that T is indeed a tree decomposition of H. Furthermore, by Prop. 5.2(6), b∗ (B0 ) ≤ b∗ (W0 ) + b∗ (S) w + 1 + (w + 1)/2 = 2 (w + 1) and by the ∗ 3 assumptions on T1,..., Tr, every other bag has b value at most 2 (w + 1).


The main result of this section is showing that the existence of highly connected sets implies that the hypergraph has large embedding power. Recall from Section 2 that W is a (µ, λ)connected set for some λ 0 and fractional independent set µ if for every disjoint X, Y ⊆ W, the minimum weight of a fractional (X, Y )-separator is at least λ · {µ(X), µ(Y )}. We denote by conλ (H) the maximum value of µ(W ) taken over every fractional independent set µ and (µ, λ)-connected set W. Recall also that the edge depth of an embedding φ of G into H is the maximum of v∈V (G) |φ(v) ∩ e|, taken over every e ∈ E(H).

Theorem 6.1.

For every sufficiently small λ 0 and hypergraph H, there is a constant mH,λ such that every graph G with m ≥ mH,λ edges has an embedding into H with edge depth O(m/(λ 2 conλ (H))). Furthermore, there is an algorithm that, given G, H, and λ, produces such an embedding in time f (H, λ)nO(1).

In other words, Theorem 6.1 gives a lower bound on the embedding power of H:

Corollary 6.2. For every sufficiently small λ 0 and hypergraph H, emb(H) = Ω(λ conλ (H)).

Theorem 6.1 is stated in algorithmic form, since the reduction in the hardness result of Section 7 needs to find such embeddings.

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

Similar works:

«FEDERAL RESERVE BANK OF SAN FRANCISCO WORKING PAPER SERIES Innovations in Mortgage Markets and Increased Spending on Housing Mark S. Doms Federal Reserve Bank of San Francisco John Krainer Federal Reserve Bank of San Francisco July 2007 Working Paper 2007-05 http://www.frbsf.org/publications/economics/papers/2007/wp07-05bk.pdf The views in this paper are solely the responsibility of the authors and should not be interpreted as reflecting the views of the Federal Reserve Bank of San Francisco or...»

«TOWN OF TEWKSBURY Anthony Ippolito, Chairman CONSERVATION COMMISSION Carolina Linder, Vice-Chair 999 Whipple Road Steve Deackoff, Clerk Dennis Sheehan Tewksbury, MA 01876 Jonathan Parker Meeting Minutes May 13, 2015 The meeting was called to order by Anthony Ippolito, Chairman at 7:00 p.m. at the Pike House. In attendance were Carolina Linder, Steve Deackoff (late arrival), Dennis Sheehan, and Jonathan Parker. Also in attendance was Kyle Boyd, Conservation Agent, and Melissa Johnson, Recording...»

«K-TAB® (potassium chloride extended-release tablets, USP) DESCRIPTION K-TAB (potassium chloride extended-release tablets) is a solid oral dosage form of potassium chloride containing 8 mEq, 10 mEq and 20 mEq of potassium chloride, USP, equivalent to 600 mg, 750 mg and 1500 mg of potassium, respectively, in a film-coated (not enteric-coated), wax matrix tablet. These formulations are intended to slow the release of potassium so that the likelihood of a high localized concentration of potassium...»

«OVERSEER®: ACCURACY, PRECISION, ERROR AND UNCERTAINTY Mark Shepherd, David Wheeler, Diana Selbie, Laura Buckthought & Mike Freeman AgResearch Ltd, Ruakura Campus, Hamilton Summary When debating the performance of models such as Overseer‟s ability to estimate whole-farm nutrient losses, four terms are often used almost interchangeably: accuracy, precision, error and uncertainty. However, the terms are not interchangeable and it is important to consider the implications of the commonly used...»

«Uncovering Horizontal Spillovers: When Foreign and Domestic Firms Share Common Local Input Suppliers Hiau Looi Keey February 2010 Abstract Based on a sample of Bangladeshi garment producers, this paper links the within.rm productivity gains of domestic.rms to the increased presence of those FDI.rms that share their local input suppliers, a.nding that is consistent with horizontal spillovers from FDI. At sample mean, horizontal spillovers can explain one third of the within.rm productivity...»

«Democratic Schools Edited by Michael W. Apple and James A. Beane • Foreword • Chapter 1. The Case for Democratic Schools— by James A. Beane and Michael W. Apple • Chapter 2. Central Park East Secondary School: The Hard Part Is Making It Happen— by Meier Deborah and Paul Schwartz • Chapter 3. Beyond the Shop: Reinventing Vocational Education— by Larry Rosenstock and Adria Steinberg • Chapter 4. La Escuela Fratney: A Journey Toward Democracy— by Bob Peterson • Chapter 5. The...»

«Sports in the Christian Life Sports, physical exercise, and recreational activity contribute to our development as spiritual beings composed of body and soul. Today as sports take on an increasingly large role in popular culture internationally, they are becoming a new field for twenty-first century Christian mission. Christian Reflection Prayer A Series in Faith and Ethics Scripture Reading: 1 Corinthians 9:24-27 Responsive Reading: God, we cannot race through this journey alone. We need each...»

«Session 2: Challenges and Risks to Development in Asia Parallel Group 2B: Topic Paper 2 Financial Vulnerability in Asia Stephany Griffith-Jones and Ricardo Gottschalk March 2006 The views and opinions of authors expressed in this paper do not necessarily state or reflect those of DFID or the Asia 2015 organisers. © Institute of Development Studies and Overseas Development Institute. Financial Vulnerability in Asia1 1. Introduction Currently, much of Asia is growing at a very impressive rate,...»

«Courant Research Centre ‘Poverty, Equity and Growth in Developing and Transition Countries: Statistical Methods and Empirical Analysis’ Georg-August-Universität Göttingen (founded in 1737) Discussion Papers No. 88 What do we really know? Metrics for food insecurity and undernutrition Hartwig de Haen, Stephan Klasen, Matin Qaim August 2011 Wilhelm-Weber-Str. 2 ⋅ 37073 Goettingen ⋅ Germany Phone: +49-(0)551-3914066 ⋅ Fax: +49-(0)551-3914059 Email: crc-peg@uni-goettingen.de Web:...»

«Security or Privacy, Must We Choose? (Position Paper) Mike Burmester,* Yvo Desmedt,* Rebecca Wright,** Alec Yasinsac* *Department of Computer Science **AT&T Labs Research Florida State University 180 Park Avenue Tallahassee, FL 32306-4530 Florham Park, NJ 07932 Abstract Hardly a day passes without reports of new threats in or about the Internet. Denial of service, worms, viruses, spam, and divulged credit card information highlight the major security threats. At the same time, we are bombarded...»

«Highfields, Garth Farm, Garth Road, Llandudno Junction, Conwy, LL31 9JF Tel : 0845 644 1964 Fax : 0845 644 1965 Company Vehicle Solutions Ltd Complaints Procedure 1. Purpose To ensure all staff are able to recognise, investigate record and resolve complaints fairly, effectively, consistently and promptly.2. Scope.2.1. Rules and requirements of the Financial Conduct Authority (FCA) 2.2. All our customers and/or their agents.3. References. 3.1. FCA Sourcebook DISP 3.2. Complaints Register 3.3....»

«Электронный информационный журнал «НОВЫЕ ИССЛЕДОВАНИя ТУВЫ» №4 2012 www.tuva.asia Проба пера brItISh druIdry ANd turKIC ShAmANISm IN CONtext Of pAgAN relIgION N. Okutan (turkey) Abstract: Article represents Celtic Druidry and Turkic Shamanism together within the phenomenon of paganism. Although both of these belief systems are under the impression of monotheistic religions such as Islam and Christianity today, they are still...»

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