WWW.ABSTRACT.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Abstracts, online materials
 
<< HOME
CONTACTS



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

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

-- [ Page 8 ] --

For the proof, our strategy is similar to the embedding result of [Marx 2010b]: we show that a highly connected set implies that a uniform concurrent flow exists, the paths appearing in the uniform concurrent flow can be used to embed (a blowup of) the line graph of a complete graph, and every graph has an appropriate embedding in the line graph of a complete graph. To make this strategy work, we need generalizations of concurrent flows, multicuts, and multicommodity flows in our hypergraph setting and we need to obtain results that connect these √ concepts to highly connected sets. Some of these results are similar in spirit to the O( n)-approximation algorithms appearing in the combinatorial optimization literature [Gupta 2003; Hajiaghayi and R¨cke 2006; Agarwal et al. 2007]. However, those approximation algorithms are mostly a based on clever rounding of fractional solutions, while in our setting rounding is not an option: as discussed in Section 5, the existence of a fractional (X, Y )-separator of small weight does not imply the existence of a small integer separator. Thus we have to work directly with the fractional solution and use the properties of the highly connected set.

It turns out that the right notion of uniform concurrent flow for our purposes is a collection of flows that connect cliques: that is, a collection Fi,j (1 ≤ i j ≤ k) of compatible flows, each of value, such that Fi,j is a (Ki, Kj )-flow, where K1,..., Kk are disjoint cliques.

Thus our first goal is to find a highly connected set that can be partitioned into k cliques in an appropriate way.

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

A:32 D. Marx

6.1. Highly connected sets with cliques Let (X1, Y1 ),..., (Xk, Yk ) be pairs of vertex sets such that the minimum weight of a fractional (Xi, Yi )-separator is si. Analogously to multicut problems in combinatorial optimization, we investigate weight assignments that simultaneously separate all these pairs.

Clearly, the minimum weight of such an assignment is at least the minimum of the si ’s and at most the sum of the si ’s. The following lemma shows that in a highly connected set, such a simultaneous separator cannot be very efficient: roughly speaking, its weight is at least the square root of the sum of the si ’s.

Lemma 6.3.

Let µ be a fractional independent set in hypergraph H and let W be a (µ, λ)-connected set for some 0 λ ≤ 1. Let (X1,..., Xk, Y1,..., Yk ) be a partition of W, k let wi := min{µ(Xi ), µ(Yi )} ≥ 1/2, and let w := i=1 wi. Let s : E(H) → R+ be a weight assignment of total weight p such that s is a fractional (Xi, Yi )-separator for every 1 ≤ i ≤ k.

√ Then p ≥ (λ/7) · w.

Proof. Let us define the function s by s (e) = 6s(e) and let x(v) := e∈E(H),v∈e s (e).

We define the distance d(u, v) to be the minimum of r∈P x(r), taken over all paths P from u to v. It is clear that the triangle inequality holds, i.e., d(u, v) ≤ d(u, z) + d(z, v) for every u, v, z ∈ V (H). If s covers every u − v path, then d(u, v) ≥ 6: every edge e intersecting a u − v path P contributes at least s (e) to the sum r∈P x(r) (as e can intersect P in more than one vertices, e can increase the sum by more than s (e)). On the other hand, we claim that if d(u, v) ≥ 2, then s covers every u − v path. Clearly, it is sufficient to verify this for minimal paths. Such a path P can intersect an edge e at most twice, hence e contributes at most 2s (e) to the sum r∈P x(r) ≥ 2, implying that the edges intersecting P have total weight at least 1 in s. √ Suppose for contradiction that p (λ/7) · w, that is, w 49p2 /λ2. As s is an k (Xi, Yi )-separator, we have that p ≥ 1. Let A := ∅ and B := i=1 (Xi ∪ Yi ). Note that k µ(B) ≥ 2 i=1 wi = 2w. We will increase A and decrease B while maintaining the invariant condition that the distance of A and B is at least 2 in d. Let T be the smallest T integer such that i=1 wi 6p/λ; if there is no such T, then w ≤ 6p/λ, a contradiction.

As wi ≥ 1/2 for every i, it follows that T ≤ 12p/λ + 1 ≤ 13p/λ (since p ≥ 1 and λ ≤ 1).

For i = 1, 2,..., T, we perform the following step. Let Xi (resp., Yi ) be the set of all vertices of W that are at distance at most 2 from Xi (resp., Yi ). As the distance of Xi and Yi is at least 6, by the triangle inequality the distance of Xi and Yi is at least 2, hence s is a fractional (Xi, Yi )-separator. Since W is (µ, λ)-connected and s is an assignment of weight 6p, we have min{µ(Xi ), µ(Yi )} ≤ 6p/λ. If µ(Xi ) ≤ 6p/λ, then let us put Xi (note: not Xi ) into A and let us remove Xi from B. The set Xi, which we remove from B, contains all the vertices that are at distance at most 2 from any new vertex in A, hence it remains true that the distance of A and B is at least 2. Similarly, if µ(Xi ) 6p/λ and µ(Yi ) ≤ 6p/λ, then let us put Yi into A and let us remove Yi from B. Note that we may put a vertex into A even if it was removed from B in an earlier step.

In the i-th step of the procedure, we increase µ(A) by at least wi (as µ(Xi ), µ(Yi ) ≥ wi and these sets are disjoint from the sets already contained in A) and µ(B) is decreased by T at most 6p/λ. Thus at the end of the procedure, we have µ(A) ≥ i=1 wi 6p/λ and µ(B) ≥ 2w − T · 6p/λ 98p2 /(λ2 ) − (13p/λ)(6p/λ) 6p/λ, that is, min{µ(A), µ(B)} 6p/λ. By the invariant condition, the distance of A and B is at least 2, thus s is a fractional (A, B)-separator of weight exactly 6p, contradicting the assumption that W is (µ, λ)-connected.





In the rest of the section, we need a more constrained notion of flow, where the endpoints “respect” a particular fractional independent set. Let µ1, µ2 be fractional independent sets Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:33 of hypergraph H and let X, Y ⊆ V (H) be two (not necessarily disjoint) sets of vertices.

A (µ1, µ2 )-demand (X, Y )-flow is an (X, Y )-flow F such that for each x ∈ X, the total weight of the paths in F having first endpoint x is at most µ1 (x), and similarly, the total weight of the paths in F having second endpoint y ∈ Y is at most µ2 (y). Note that there is no bound on the weight of the paths going through an x ∈ X, we only bound the paths whose first/second endpoint is x. The definition is particularly delicate if X and Y are not disjoint, in this case, a vertex z ∈ X ∩ Y can be the first endpoint of some paths and the second endpoint of some other paths, or it can be even both the first and second endpoint of a path of length 0. We use the abbreviation µ-demand for (µ, µ)-demand.

The following lemma shows that if a flow connects a set U with a highly connected set W, then U is highly connected as well (“W can be moved to U ”). This observation will be used in the proof of Lemma 6.5, where we locate cliques and show that their union is highly connected, since there is a flow that connects the cliques to a highly connected set.

Lemma 6.4.

Let H be a hypergraph, µ1, µ2 fractional independent sets, and W ⊆ V (H) a (µ1, λ)-connected set for some 0 λ ≤ 1. Suppose that U ⊆ V (H) is a set of vertices and F is a (µ1, µ2 )-demand (W, U )-flow of value µ2 (U ). Then U is (µ2, λ/6)-connected.

Proof. Suppose that there are disjoint sets A, B ⊆ U and a fractional (A, B)-separator s of weight w (λ/6) · min{µ2 (A), µ2 (B)}. (Note that this means µ2 (A), µ2 (B) 6w/λ ≥ 6w.) For a path P, let s(P ) = e∈E(H),e∩P =∅ s(e) be the total weight of the edges intersecting P. Let A ⊆ W (resp., B ⊆ W ) contain a vertex v ∈ W if there is a path P in F with first endpoint v and second endpoint in A (resp., B) and s(P ) ≤ 1/3. If A ∩ B = ∅, then it is clear that there is a path P with s(P ) ≤ 2/3 connecting a vertex of A and a vertex of B via a vertex of A ∩ B, a contradiction. Thus we can assume that A and B are disjoint.

Since F is a flow and s has weight w, the total weight of the paths in F with s(P ) ≥ 1/3 is at most 3w. As the value of F is exactly µ2 (U ), the total weight of the paths in F with second endpoint in A is exactly µ2 (A). If s(P ) ≤ 1/3 for such a path, then its first endpoint is in A by definition. Therefore, the total weight of the paths in F with first endpoint in A is at least µ2 (A) − 3w, which means that µ1 (A ) ≥ µ2 (A) − 3w ≥ µ2 (A)/2. Similarly, we have µ1 (B ) ≥ µ2 (B)/2. Since W is (µ1, λ)-connected and s is an assignment with weight less than (λ/6) · min{µ2 (A), µ2 (B)} ≤ (λ/3) · min{µ1 (A ), µ1 (B )}, there is an A − B path P with s(P ) 1/3. Now the concatenation of an A − A path PA having s(PA ) ≤ 1/3, the path P, and a B − B path PB having s(PB ) ≤ 1/3 forms an A − B path that is not covered by s, a contradiction.

A µ-demand multicommodity flow between pairs (A1, B1 ),..., (Ar, Br ) is a set F1,..., Fr of compatible flows such that Fi is a µ-demand (Ai, Bi )-flow (recall that a set of flows is compatible if their sum is also a flow, that is, does not violate the edge constraints). The r value of a multicommodity flow is the sum of the values of the r flows. Let A = i=1 Ai, r B = i=1 Bi, and let us restrict our attention to the case when (A1,..., Ar, B1,..., Br ) is a partition of A ∪ B. In this case, the maximum value of a µ-demand multicommodity flow between pairs (A1, B1 ),..., (Ar, Br ) can be expressed as the optimum values of the primal and dual linear programs in Figure 5.

The following lemma shows that if conλ (H) is sufficiently large, then there is a highly connected set that has the additional property that it is the union of k cliques K1,..., Kk with µ(Ki ) ≥ 1/2 for every clique. The high-level idea of the proof is the following.

Take a (µ, λ)-connected set W with µ(W ) = conλ (H) and find a large multicommodity flow between some pairs (A1, B1 ),..., (Ar, Br ) in W. Consider the dual solution y. By complementary slackness, every edge with nonzero value in y covers exactly 1 unit of the multicommodity flow. If most of the weight of the dual solution is on the edge variables, then we can choose k edges that cover at least Ω(k) units of flow. These edges are connected to

–  –  –

Fig. 5. Primal and dual linear programs for µ-demand multicommodity flow between pairs (A1, B1 ),..., (Ar, Br ). We denote by Puv the set of all u − v paths.

W by a flow, and therefore by Lemma 6.4 the union of these edges is also highly connected and obviously can be partitioned into a small number cliques.

There are two things that can go wrong with this argument. First, it can happen that the dual solution assigns most of the weight to the vertex variables y(u), y(v) (u ∈ A, v ∈ B).

The cost of covering the Ai − Bi paths using vertex variables only is min{µ(Ai ), µ(Bi )}, thus this case is only possible if the value of the dual (and hence the primal) solution is close r to i=1 (min{µ(Ai ), µ(Bi )}). To avoid this situation, we want to select the pairs (Ai, Bi ) such that they are only “moderately connected”: there is a fractional (Ai, Bi )-separator of weight 2λ min{µ(Ai ), µ(Bi )}, that is, at most twice the minimum possible. This means that r the weight of the dual solution is at most 2λ i=1 (min{µ(Ai ), µ(Bi )}), which is much less r than i=1 (min{µ(Ai ), µ(Bi )} (if λ is small). If we are not able to find sufficiently many such pairs, then we argue that a larger highly connected set can be obtained by scaling µ by a factor of 2. More precisely, we show that there is a large subset W ⊆ W that is (2µ, λ)-connected and 2µ(W ) conλ (H), a contradiction (a technical difficulty here that we have to make sure first that 2µ is also a fractional independent set).

The second problem we have to deal with is that the value of the dual solution can be so small that we find a very small set of edges that already cover a large fraction of the multicommodity flow. However, we can use Lemma 6.3 to argue that a weight assignment on the edges that covers a large multicommodity flow in a (µ, λ)-connected set cannot have very small weight.

Lemma 6.5.

Let H be a hypergraph and let 0 λ 1/16 be a constant. Then there is fractional independent set µ, a (µ, λ/6)-connected set W, and a partition (K1,..., Kk ) of W such that k = Ω(λ conλ (H)), and for every 1 ≤ i ≤ k, Ki is a clique with µ(Ki ) ≥ 1/2.

Proof. Let k be the largest integer such that conλ (H) ≥ 3T + 2k holds, where T :=

(56/λ)2 · k 2 ; it is clear that k = Ω(λ conλ (H)). Let µ0 be a fractional independent set and W0 be a (µ0, λ)-connected set with µ0 (W0 ) = conλ (H). We can assume that µ0 (v) 0 if and only if v ∈ W0. This also implies that W0 is in one connected component of H.

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:35 Highly loaded edges. First, we want to modify µ0 such that there is no edge e with µ0 (e) ≥ 1/2. The following claim shows that we can achieve this by restricting µ0 to an appropriate subset W of W0.

Claim 1. There is a subset W ⊆ W0 such that µ0 (W ) ≥ conλ (H) − k and µ0 (e ∩ W ) 1/2 for every edge e.

Proof.

Let us choose edges g1, g2,... as long as possible with the requirement µ0 (Ki ) ≥ 1/2 for i−1 Ki := (gi ∩ W0 ) \ j=1 Kj. If we can select at least k such edges, then the cliques K1,..., k Kk satisfy the requirements of Lemma 6.5 and we are done. Indeed, W := i=1 Ki ⊆ W0 is a (µ0, λ)-connected set, µ0 (Ki ) ≥ 1/2, and (K1,..., Kk ) is a partition of W into cliques.

Thus we can assume that the selection of the edges stops at edge gt for some t k. Let t W := W0 \ i=1 Ki. Observe that there is no edge e ∈ E(H) with µ0 (e ∩ W ) ≥ 1/2, as in this case the selection of the edges could be continued with gt+1 := e. Furthermore, we t have µ0 (W ) = µ0 (W0 \ i=1 Ki ) µ0 (W0 ) − k = conλ (H) − k, as required.



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


Similar works:

«International Journal on Asian Language Processing 20 (4):171-179 171 Evaluating the Quality of Web-Mined Bilingual Sentence Pairs Xiaohua Liu1,2, Ming Zhou2 School of Computer Science and Technology Harbin Institute of Technology,Harbin,150001,China Microsoft Research Asia,Beijing, 100190,China {xiaoliu,mingzhou}@microsoft.com Abstract We come up with the problem of evaluating the quality of bilingual sentence pairs mined from the web, which is critical for a wide range of applications such as...»

«Report of the Commonwealth Expert Team RWANDA LEGISLATIVE ELECTION (Chamber of Deputies) 16-18 September 2013 Rwanda Legislative Election (Chamber of Deputies) 16-18 September 2013 Table of Contents Letter of Transmittal... iv CHAPTER ONE INTRODUCTION Invitation Terms of Reference Activities CHAPTER TWO POLITICAL BACKGROUND Political Parties CHAPTER THREE THE ELECTORAL FRAMEWORK AND ELECTION ADMINISTRATION Legal Framework for the Elections Constitutional Background National Electoral...»

«International Journal of Algebra, Vol. 6, 2012, no. 27, 1343 1352 Changing and Unchanging Domination Number of a Commutative Ring J. Ravi Sankar Department of Mathematics, Saradha Gangadharan College Puducherry 605 004, India ravisankar.maths@gmail.com S. Meena Department of Mathematics, Government Arts College Chidambaram 608 104, India meenasaravanan14@gmail.com Abstract Let R be a commutative ring and let Γ(Zn ) be the zero divisor graph of a commutative ring R, whose vertices are non-zero...»

«Office of the City Manager ACTION CALENDAR May 31, 2016 To: Honorable Mayor and Members of the City Council From: Dee Williams-Ridley, City Manager Submitted by: Mark Numainville, City Clerk Subject: Placing a Charter Amendment and Ordinance Measure on the November 8, 2016 Ballot to Create a Public Campaign Financing System RECOMMENDATION 1. Adopt a Resolution submitting a Charter Amendment and Ordinance Measure related to Berkeley Charter Article III (Elections) and Municipal Code Chapter 2.12...»

«Forested Tidal Wetland Communities Forested Tidal Wetland Communities of Maryland’s Eastern Shore of Maryland’s Eastern Shore Identification, Assessment, and Monitoring Jason W. Harrison Peter Stango III Maria C. Aguirre Maryland Department of Natural Resources Wildlife and Heritage Service Maryland Natural Heritage Program The United States Environmental Protection Agency Clean Water Act 1998 State Wetlands Development Protection Grant Program FORESTED TIDAL WETLAND COMMUNITIES OF...»

«2014 Working Paper Series Volume 7 Terror Tactics – Shootings of Indonesian Police and the definition of terror Adam Fenton, Hery Firmansyah, and David Price Editors: Christopher A. Woodrich and Frank Dhont Recommended Citation: Fenton, Adam; Firmansyah, Hery; Price, David. Terror Tactics – Shootings of Indonesian Police and the definition of terror. 2014 International Indonesia Forum, Working Paper Series 7 (2014). Page 1 of 21 Terror Tactics – Shootings of Indonesian Police and the...»

«Public Disclosure Authorized Public Disclosure Authorized Opportunities and Options for Governments to Promote Corporate Social Responsibility in Europe and Central Asia Public Disclosure Authorized Evidence from Bulgaria, Croatia, and Romania Public Disclosure Authorized Working Paper Opportunities and Options for Governments to Promote Corporate Social Responsibility Copyright©2005 The Development Communication Division (DevComm), EXT The World Bank 1818 H Street, N.W. Washington, D.C.,...»

«7 “Yes Sir, Yes Sir, Three Bags Full” T he squad goes out in file, and as we go the guys who are digging nod and give us mock salutes. It’s brotherhood, not manhood. The brush thickens, and ten minutes outside the wire it’s a different world. Prophet is walking point with his steel pot on, and his ruck rides high on his back. Peacock is next with the Sixty over his shoulder, its belt of ammo coming out the side like miniature ears of corn. I follow him, Eltee Williams is behind me, then...»

«EUROSPHERE Diversity and the European Public Sphere Towards a Citizens' Europe Linking the European Union with the Citizens Evaluation of EU Policies Aiming to Create a Democratic European Public Sphere Edited by Hakan G Sicakkan University of Bergen This paper can be downloaded without charge from: http://eurospheres.org/ ISSN 1890-5986 EUROSPHERE FINAL COMPARATIVE STUDY, VOLUME I Title: Linking the European Union with the Citizens. Evaluation of EU Policies Aiming to Create a Democratic...»

«A reindeer out of season meets a lone wolf, and sparks and fur fly. Venny can’t believe she missed mating season! With her body in an uproar and no males free, this reindeer high tails it to the Crossroads in search of a male to quench her fire. With her own species out of the running she is willing to experiment, and while the wolf she meets knows she’s a dear, he has no idea she’s a deer. One lone wolf against a horny reindeer.what chance does he have? The unauthorized reproduction or...»

«Pak. J. Bot., 36(3): 611-615, 2004. EMPLOYMENT OF IN VITRO TECHNOLOGY FOR LARGE SCALE MULTIPLICATION OF PINEAPPLES (ANANAS COMOSOS) SAIFULLAH KHAN, ASMA NASIB AND BUSHRA AHMAD SAEED Plant Tissue Culture and Biotechnology Lab., International Centre for Chemical Sciences, H.E.J. Research Institute of Chemistry University of Karachi, Karachi, Pakistan. Abstract Experiments were carried out for the micropropagation of pineapples. It is thus possible to produce disease free, uniform propagules at...»

«OBO and OWL: Leveraging Semantic Web Technologies for the Life Sciences Christine Golbreich1, Matthew Horridge2, Ian Horrocks3, Boris Motik3, and Rob Shearer3 University of Versailles-Saint Quentin 55 avenue de Paris, 78035 Versailles, France Christine.Golbreich@uvsq.fr School of Computer Science, University of Manchester Oxford Road, Manchester, M13 9PL, UK horridge@cs.man.ac.uk Oxford University Computing Laboratory Wolfson Building, Parks Road, Oxford, OX1 3QD, UK...»





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