FREE ELECTRONIC LIBRARY - Abstracts, online materials

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

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

-- [ Page 9 ] --

Moderately connected pairs. Let us define µ such that µ(v) = 2µ0 (v) if v ∈ W and µ(v) = 0 otherwise. By Claim 1, µ is a fractional independent set. The set W is (µ0, λ)connected (recall that a subset of (µ0, λ)-connected is also (µ0, λ)-connected). However, W is not necessarily (µ, λ)-connected. In the next step, we find a large collection of pairs (Ai, Bi ) that violate (µ, λ)-connectivity. Informally, we can say that these pairs (Ai, Bi ) are “moderately connected”: denoting wi = min{µ(Ai ), µ(Bi )}, the minimum value of a fractional (Ai, Bi )-separator for such a pair is less than λwi (because the pair (Ai, Bi ) violates (µ, λ)-connectivity), but at least λwi /2 = λ min{µ0 (Ai ), µ0 (Bi )} (because W is (µ0, λ)-connected).

Claim 2. There are disjoint sets A1, B1,.

.., Ar, Br ⊆ W such that for every 1 ≤ i ≤ r there is a fractional (Ai, Bi )-separator with weight less than λwi for wi := min{µ(Ai ), µ(Bi )} and r w := i=1 wi ≥ T.

Proof. Let us greedily select a maximal collection of pairs (A1, B1 ),..., (Ar, Br ) with the property that there is a fractional (Ai, Bi )-separator with weight less than λwi for wi := min{µ(Ai ), µ(Bi )}. Note that every fractional separator has value at least 1 (as W is in a single component of H), thus λwi 1 holds, implying wi 1/λ 1. We can assume that µ(Ai ), µ(Bi ) ≤ wi + 1: if, say, µ(Ai ) µ(Bi ) + 1, then removing an arbitrary vertex of Ai decreases µ(Ai ) by at most one (as µ is a fractional independent set) without changing min{µ(Ai ), µ(Bi )}, hence there would be a smaller pair of sets with the required properties.

Therefore, we have 2wi ≤ µ(Ai ∪ Bi ) ≤ 2wi + 1 ≤ 3wi for every 1 ≤ i ≤ r.

r r Suppose for contradiction that w := i=1 wi T. Let W := W \ i=1 (Ai ∪ Bi ). As r r µ( i=1 (Ai ∪ Bi )) ≤ i=1 3wi = 3w 3T, we have µ(W ) µ(W ) − 3T = 2µ0 (W ) − 3T ≥ 2 conλ (H) − 2k − 3T ≥ conλ (H). Since the greedy selection stopped, there is no fractional (A, B )-separator of value less than λ · min{µ(A ), µ(B )} for any disjoint A, B ⊆ W, that is, W is (µ, λ)-connected with µ(W ) conλ (H), contradicting the definition of conλ (H).

Finding a multicommodity flow. Let (A1, B1 ),..., (Ar, Br ) be as in Claim 2. Since there is a fractional (Ai, Bi )-separator of value less than λwi, the maximum value of a µdemand multicommodity flow between pairs (A1, B1 ),..., (Ar, Br ) is less than λw. Let y be an optimum dual solution; we give a lower bound on the total weight of the edge variables.

–  –  –

Locating the cliques. Let y be an optimum dual solution for the maximum multicommodity flow problem with pairs (A1, B1 ),..., (Ar, Br ) and let flow F be the sum of the flows obtained from an optimum primal solution.

Claim 4. There are k pairwise-disjoint cliques K1,.

.., Kk and a set of k subflows f1,..., fk of F, each of them having value at least 1/2, such that every path appearing in fi intersects Ki and is disjoint from Kj for every j = i.

Proof. Let F (0) = F and for i = 1, 2,..., let F (i) be the flow obtained from F (0) by removing f1,..., fi. Let c(e, F (i) ) be the total weight of the paths in F (i) intersecting edge e and let Ci = e∈E(H) y(e)c(e, F (i) ). By complementary slackness, c(e, F (0) ) = 1 for each e ∈ E(H) with y(e) 0 and hence C0 = e∈E(H) y(e) ≥ 2k.

Let us select ei to be an edge such that c(ei, F (i−1) ) is maximum possible and let Ki :=

i−1 ei \ j=1 ej. Let the flow fi contain all the paths of F (i−1) intersecting ei. Observe that the paths appearing in fi do not intersect e1,..., ei−1 (otherwise they would be in one of f1,..., fi−1 and hence they would no longer be in F (i−1) ), thus clique Ki intersects every path in fi.

For every u − v path P appearing in F (0), we get e∈E(H),e∩P =∅ y(e) + y(u) + y(v) = 1 from complementary slackness: if the primal variable corresponding to P is nonzero, then the corresponding dual constraint is tight. In particular, this means that the total weight of the edges intersecting such a path P is at most 1 in y. As F (i−1) is a subflow of F (0), this is also true for every path P in F (i−1). This means that when we remove a path of weight γ from F (i−1) to obtain F (i), then the total weight of the edges e for which c(e, F (i−1) ) decreases by γ is at most 1, i.e., Ci−1 decreases by at most γ. As only the paths intersecting ei are removed from F (i−1) and the total weight of the paths intersecting ei is at most 1, we get that Ci ≥ Ci−1 − 1 and hence Ci ≥ C0 − k ≥ C0 /2 for i ≤ k. Since C0 = e∈E(H) y(e) and Ci = e∈E(H) y(e)c(e, F (i) ) ≥ C0 /2, it follows that there has to be at least one edge e with c(e, F (i) ) ≥ 1/2. Thus in each step, we can select an edge ei such that that the total

–  –  –

Claim 5. There is a fractional independent set µ such that U is a (µ, λ/6)-connected set with µ (Ki ) ≥ 1/2 for every 1 ≤ i ≤ r.

Proof. Each path P in fi is a path with endpoints in W and intersecting Ki. Let us truncate each path P in fi such that its first endpoint is still in W and its second endpoint is in Ki ; let fi be the (W, Ki )-flow obtained by truncating every path in fi. Note that fi is still a flow and the sum F of f1,..., fk is a (W, U )-flow. Let µ1 = µ and let µ2 (v) be the total weight of the paths in F with second endpoint v. It is clear that µ2 is a fractional independent set, µ2 (Ki ) ≥ 1/2, and F is a (µ1, µ2 )-demand (W, U )-flow with value µ2 (U ).

Thus by Lemma 6.4, U is a (µ2, λ/6)-connected set with the required properties.

The set U, the partition (K1,..., Kr ), and the fractional independent set µ clearly satisfy the requirements of the lemma.

6.2. Concurrent flows and embedding Let W be a set of vertices and let (X1,..., Xk ) be a partition of W. A uniform concurrent flow of value on (X1,..., Xk ) is a compatible set of k flows Fi,j (1 ≤ i j ≤ k) where Fi,j is an (Xi, Xj )-flow of value. The maximum value of a uniform concurrent flow on W can be expressed as the optimum values of the primal and dual linear programs in Figure 6.

Intuitively, the dual linear program expresses that the “distance” of Xi and Xj is at least i,j (where distance is measured as the minimum total weight of the edges intersected by an Xi − Xj path) and the sum of these k distances is at least 1.

If H is connected, then the maximum value of a uniform concurrent flow on (X1,..., Xk ) is at least 1/ k = Ω(k −2 ): if each of the k flows has value 1/ k, then they are clearly compatible. The following lemma shows that in a (µ, λ)-connected set, if the sets X1,..., Xk are cliques and µ(Xi ) ≥ 1/2 for every i, then we can guarantee a better bound of Ω(k − 2 ).

Lemma 6.6.

Let H be a hypergraph, µ a fractional independent set of H, and W ⊆ V (H) a (µ, λ)-connected set for some 0 λ 1. Let (K1,..., Kk ) (for some k ≥ 1) be a partition of W such that Ki is a clique and µ(Ki ) ≥ 1/2 for every 1 ≤ i ≤ k. Then there is a uniform concurrent flow of value Ω(λ/k 2 ) on (K1,..., Kk ).

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

A:38 D. Marx Proof. Suppose that there is no uniform concurrent flow of value β · λ/k 2, where β 0 is a sufficiently small universal constant specified later. This means that the dual linear program has a solution having value less than that. Let us fix such a solution (y, i,j )

of the dual linear program. In the following, for every path P, we denote by y(P ) :=

e∈E(H),e∩P =∅ y(e) the total weight of the edges intersecting P. It is clear from the dual linear program that y(P ) ≥ i,j for every P ∈ Pi,j.

We construct two graphs G1 and G2 : the vertex set of both graphs is {1,..., k} and for every 1 ≤ i j ≤ k, vertices i and j are adjacent in G1 (resp., G2 ) if and only if i,j 1/(3k ) (resp., i,j 1/k ). Note that G2 is a subgraph of G1. First we prove the

following claim:

Claim 1. If the distance of u and v is at most 3 in the complement of G1, then u and v are not adjacent in G2.

Proof. Suppose that uw1 w2 v is a path of length 3 in the complement of G1 (the same argument works for paths of length less than 3). By definition of G1, there is a Ku − Kw1 path P1, a Kw1 − Kw2 path P2, and a Kw2 − Kv path P3 such that y(P1 ), y(P2 ), y(P3 ) ≤ 1/(3k 2 ). Since Kw1 and Kw2 are cliques, paths P1 and P2 touch, and paths P2 and P3 touch. Thus by concatenating the three paths, we can obtain a Ku − Kv path P with y(P ) ≤ y(P1 ) + y(P2 ) + y(P3 ) ≤ 1/k 2, implying that u and v are not adjacent in G2, proving the claim. Note that the proof of this claim is the only point where we use that the Ki ’s are cliques.

E(H) → R+ be defined by y (e) := 3k 2 · y(e), thus y has total weight less Let y : √ than 3β · λ k. Suppose first that G1 has a matching a1 b1,..., am bm of size m = k/4.

This means that y covers every Kai − Kbi path for every 1 ≤ i ≤ k/4. Therefore, by √ k/4 · (1/2) 3β ·λ k, if β is sufficiently small, Lemma 6.3, y has weight at least (λ/7)· yielding a contradiction.

Thus the size of the maximum matching in G1 is less than k/4, which means that there is a vertex cover S1 of size at most k/2. Let S2 ⊆ S1 contain those vertices of S1 that are adjacent to every vertex outside S1 in G1. We claim that S2 is a vertex cover of G2. Suppose that there is an edge uv of G2 for some u, v ∈ S2. By the definition of S2, either u ∈ S1, or there is a vertex w1 ∈ S1 such that u and w1 are not adjacent in G1. Similarly, either v is not in S1, or it is not adjacent in G1 to some w2 ∈ S1. Since vertices not in S1 are not adjacent in G1 (as S1 is a vertex cover of G1 ), we get that the distance of u and v is at most 3 in the complement of G1. Thus by the claim, u and v are not adjacent in G2.

Let us give an upper bound on 1≤ij≤k i,j by bounding i,j separately for pairs that are adjacent in G2 and for pairs that are not adjacent in G2. The number of edges in G2 is at most |S2 |k (as S2 is vertex cover). The total weight of y, which is less than β · λ/k 2, is an upper bound on any i,j. Furthermore, if i and j are not adjacent in G2, then we have i,j ≤ 1/k. Therefore,

–  –  –

Intuitively, the intersection structure of the paths appearing in a uniform concurrent flow on cliques K1,..., Kk is reminiscent of the edges of the complete graph on k vertices: if {i1, j1 } ∩ {i2, j2 } = ∅, then every path of Fi1,j1 touches every path of Fi2,j2. We use the following result from [Marx 2010b], which shows that the line graph of cliques have good embedding properties. If G is a graph and q ≥ 1 is an integer, then the blow up G(q) is obtained from G by replacing every vertex v with a clique Kv of size q and for every edge uv of G, connecting every vertex of the clique Ku with every vertex of the clique Kv. Let Lk be the line graph of the complete graph on k vertices.

Lemma 6.7 (Marx [2010b]).

For every k 1 there is a constant nk 0 such that (q) for every G with |E(G)| nk and no isolated vertices, the graph G is a minor of Lk for q = 130|E(G)|/k 2. Furthermore, a minor mapping can be found in time polynomial in the size of G.

(q) Using the terminology of embeddings, a minor mapping of G into Lk can be considered as an embedding from G to Lk where every vertex of Lk appears in the image of at most q vertices, i.e., the vertex depth of the embedding is at most q. Thus we can restate Lemma 6.7

the following way:

Lemma 6.8.

For every k 1 there is a constant nk 0 such that for every G with |E(G)| nk and no isolated vertices, the graph G has an embedding into Lk with vertex depth O(|E(G)|/k 2 ). Furthermore, such an embedding can be found in time polynomial in the size of G.

Now we are ready to prove Theorem 6.1, the main result of the section:

Proof (of Theorem 6.1). By Lemma 6.5 and Lemma 6.6, for some k = Ω(λ conλ (H)), there are cliques K1,..., Kk and a uniform concurrent flow Fi,j (1 ≤ i j ≤ k) of value = Ω(λ/k 2 ) on (K1,..., Kk ). By trying all possibilities for the cliques and then solving the uniform concurrent flow linear program, we can find these flows (the time required for this step is a constant f (H, λ) depending only on H and λ). Let w0 be the smallest positive weight appearing in the flows.

Let m = |E(G)| and suppose that m ≥ nk, for the constant nk in Lemma 6.8. Thus the algorithm of Lemma 6.8 can be used to find a an embedding ψ from G to Lk with vertex depth q = O(m/k 2 ). Let us denote by v{i,j} (1 ≤ i j ≤ k) the vertices of Lk with the meaning that distinct vertices v{i1,j1 } and v{i2,j2 } are adjacent if and only if {i1, j1 } ∩ {i2, j2 } = ∅.

We construct an embedding φ from G to H the following way. The set φ(u) ⊆ V (H) is obtained from the set ψ(u) ⊆ V (Lk ) by replacing each vertex of v{i,j} ∈ ψ(u) ⊆ V (Lk ) by a path from the flow Fi,j (thus φ(u) is the union of |ψ(u)| paths of H). We select the paths in such a way that the following requirement is satisfied: a path P of Fi,j having weight w is selected into the image of at most (q/ ) · w vertices of G. We set mH,λ sufficiently large that (q/ ) · w0 ≥ 1 (note that q depends on m, but and w0 depends only on H and λ). Thus if m ≥ mH,λ, then (q/ ) · w ≤ 2(q/ ) · w. Since the total weight of the paths in Fi,j is, these paths can accommodate the image of at least (q/ ) · = q vertices. As each vertex v{i,j} of Lk appears in the image of at most q vertices of G in the mapping ψ, we can satisfy the requirement.

It is easy to see that if u1 and u2 are adjacent in G, then φ(u1 ) and φ(u2 ) touch: in this case, there are vertices v{i1,j1 } ∈ ψ(u1 ), v{i2,j2 } ∈ ψ(u2 ) that are adjacent or the same in Lk (that is, there is a t ∈ {i1, j1 } ∩ {i2, j2 }), and the corresponding paths of Fi1,j1 and Fi2,j2 selected into φ(u1 ) and φ(u2 ) touch, as they both intersect the clique Kt. With a similar argument, we can show that φ(u) is connected.

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

Similar works:

«Learning about Job Search: A Field Experiment with Job Seekers in Germany⇤ Steffen Altmann† Armin Falk‡ Simon Jäger§ Florian Zimmermann May 2015 Abstract We conduct a large-scale field experiment in the German labor market to investigate how information provision affects job seekers’ employment prospects and labor market outcomes. Individuals assigned to the treatment group of our experiment received a brochure that informed them about job search strategies and the consequences of...»

«Avec le partenariat méthodologique Anorexie mentale : Avec le partenariat de Avec la participation et le soutien financier de la prise en charge Juin 2010 Préambule Repérage, diagnostic et fondements de la prise en charge Intérêt du repérage précoce Modalités du repérage ciblé de l’anorexie mentale Populations à risque Diagnostic et fondements de la prise en charge Premiers soins spécialisés et filières de prise en charge Différents niveaux de soins Prise en charge...»

«Investment Research — General Market Conditions 13 December 2016 Danske Daily  In the eurozone, German ZEW expectations are due out today. Since July, ZEW expectations Selected readings from Danske Bank have followed a rising tendency to 13.8 in November but the December figure may bring this tendency to a halt. The Sentix released last week saw an unexpected fall, which maybe  Norges Bank preview reflected the uncertainty related to the Italian referendum. However, although the 'no'...»

«Education and Information Technologies 7:3, 237–255, 2002.  2002 Kluwer Academic Publishers. Manufactured in The Netherlands. Pedagogical Reasoning: Issues and Solutions for the Teaching and Learning of ICT in Secondary Schools MARY E. WEBB Department of Education and Professional Studies, King’s College London, Franklin–Wilkins Building, Waterloo Bridge Wing, Waterloo Road, London SE1 9NN, UK E-mail: mary.webb@kcl.ac.uk Abstract Confusion has developed over the role of ICT in schools...»

«CAST. DAYTOURS Vive las mejores experiencias en las comarcas de Valencia Cullera Requena Xàtiva Llíria València Summer Day Sagunt Ontinyent Bocairent Gandia Salidas todos los días desde la oficina de información turística en la Plaza del Ayuntamiento (Valencia).HORARIOS: Salida: 10.00 Regreso: 18.00   PRECIOS: Adultos: 35 € Niños: 15 € (3 años de edad 10) Menores de 3: gratis (no incluye almuerzo)   (El precio incluye traslados, visita guiada y almuerzo)   + INFO: Tel. 900 70 18...»

«Persian Occupation of Egypt 619-629: Politics and Administration of Sasanians Saeid Jalalipour e-Sasanika Graduate paper 10 California State University, Fullerton The last great war of Late Antiquity was fought between the Persians and the Romans in the beginning of the seventh century.1 After the death of the Roman emperor Maurice by the usurper Phocas in 602 C.E., the Persian king Khusro II attacked the Byzantine Empire to avenge the death of his benefactor.2 Even though the usurper was...»

«Uncovered And Out In The Cold Middle America’s unmet need for life insurance, and the role for America’s credit unions. Page Introduction: Bringing clarity to the problem of underinsured Middle America....................... 1 A market largely overlooked and underserved............ 2 Middle Americans recognize the need.................. 3 Credit union members among the uninsured............. 4 The need among seniors........»

«Determining the Drag Coefficient Of A Model Rocket Using Acclerometer Based Payloads By Tim Van Milligan C-Division NAR 35872 R&D Event NARAM-54 July, 2012 Page 1 Determining the Drag Coefficient Of A Model Rocket Using Acclerometer Based Payloads By Tim Van Milligan C-Division NAR 35872 R&D Event NARAM-54 July, 2012 Summary In order to accurately predict the performance of a model rocket, whether by doing simple hand calculations or using sophisticated computer software, the modeler must have...»

«Interventions: Communication Research and Practice Call for Papers Conference of the International Communication Association C o m mun ic at i al on on As ti na so er ci San Diego, California, USA at i Int o n 25-29 May 2017 INTERVE COMMUNICATION PRAC The Conference Theme for ICA 20 “I ntervention” points to a range of communication practices that engage with a political event, social phenomena, industrial or socio-cultural practice, in order to alter and disrupt events and the norms and...»

«ISSN(Online): 2320-9801 ISSN (Print): 2320-9798 International Journal of Innovative Research in Computer and Communication Engineering (An ISO 3297: 2007 Certified Organization) Vol. 2, Issue 4, April 2014 Implementation of Embedded System Using RFID and Alcohol Sensor at the Toll Plaza Abdulshabaz1, K. Mounika2, B. Krishna3, K.J.Arvind chary4 Student, Dept. of E.C.E, KITE College of Professional Engineering sciences-Shabad, Hyderabad, Andhrapradesh, India1,2 Associate Prof, Dept. of E.C.E,...»

«Humble Hero Ellen G. White Copyright © 2012 Ellen G. White Estate, Inc. Information about this Book Overview This eBook is provided by the Ellen G. White Estate. It is included in the larger free Online Books collection on the Ellen G. White Estate Web site. About the Author Ellen G. White (1827-1915) is considered the most widely translated American author, her works having been published in more than 160 languages. She wrote more than 100,000 pages on a wide variety of spiritual and...»

«KARANDAAZ PAKISTAN Request for Quotations RFQ # 008 “JANITORIAL SERVICES FOR KARANDAAZ PAKISTAN” Date: April 06, 2016 Deadline for Questions: April 11, 2016 Deadline for Karandaaz Responses: April 13, 2016 Deadline for submission of quotations: April 22, 2016 www.karandaaz.com.pk A company set up under Section 42 of the Companies Ordinance, 1984 RFQ No. 8 – Janitorial Services SECTION 1. LETTER OF INVITATION RFQ No. 8 April 06, 2016, Islamabad 1. The purpose of this RFQ is to solicit...»

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