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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |

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

-- [ Page 6 ] --
The aim of this section is to show that if a hypergraph H has large submodular width, then there is a large highly connected set in H. Recall that we say that a set W is (µ, λ)connected for some fractional independent set µ and λ 0, if for every disjoint A, B ⊆ W, every fractional (A, B)-separator has weight at least λ · min{µ(A), µ(B)} (see Section 2).

Equivalently, we can say that for every disjoint A, B ⊆ W, there is an (A, B)-ﬂow of value λ · min{µ(A), µ(B)}. Recall also that conλ (H) denotes the maximum value of µ(W ) taken over every fractional independent set µ and (µ, λ)-connected set W.

The main result of this section allows us to identify a highly connected set if submodular

width is large:

Theorem 5.1.

For every suﬃciently 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 2 (w + 1), then conλ (H) ≥ w.

For the proof of Theorem 5.1, we need to show that if there is no tree decomposition where b(B) is small for every bag B, then a highly connected set exists. There is a standard recursive procedure that either builds a tree decomposition or ﬁnds a highly connected set (see e.g., [Flum and Grohe 2006, Section 11.2]). Simplifying somewhat, the main idea is that if the graph can be decomposed into smaller graphs by splitting a certain set of vertices into two parts, then a tree decomposition for each part is constructed using the algorithm recursively, and the tree decompositions for the parts are joined in an appropriate way to obtain a tree decomposition for the original graph. On the other hand, if the set of vertices cannot be split, then we can conclude that it is highly connected. This high-level idea has been applied for various notions of tree decompositions [Oum and Seymour 2006; Oum 2005; Adler et al. 2007; Oum and Seymour 2007; Marx 2010a], and it turns out to be useful

in our context as well. However, we need to overcome two major diﬃculties:

(1) Highly connected set in our context is deﬁned as not having certain fractional separators (i.e., weight assignments). However, if we want to build a tree decomposition in a recursive manner, we need integer separators (i.e., subsets of vertices) that decompose the hypergraph into smaller parts.

(2) Measuring the sizes of sets with a submodular function b can lead to problems, since the size of the union of two sets can be much smaller than the sum of the sizes of the two sets. We need the property that, roughly speaking, removing a “large” part from a set makes it “much smaller.” For example, if A and B are components of H \ S, and both b(A) and b(B) are large, then we need the property that both of them are much smaller than b(A ∪ B). Adler [2006, Section 4.2] investigates the relation between some notion of highly connected sets and f -width, but assumes that f is additive: if A and B do not touch, then f (A∪B) = f (A)+f (B). However, for a submodular function b, there is no reason to assume that additivity holds: for example, it very well may be that b(A) = b(B) = b(A ∪ B).

To overcome the ﬁrst diﬃculty, we have to understand what fractional separation really means. The ﬁrst question is whether fractional separation is equivalent to some notion of integral separation, perhaps up to constant factors. The ﬁrst, naive, question is whether a fractional (X, Y )-separator of weight w implies that there are O(w) edges whose union is an (X, Y )-separator, i.e., there is an (X, Y )-separator S with ρH (S) = O(w). There is a simple counterexample showing that this is not true. It is well-known that for every integer k 0, there is a hypergraph Hk such that ρ∗ (Hk ) = 2 and ρ(Hk ) = k. Let V be the set of vertices of Hk and let Hk be obtained from Hk by extending it with two independent sets X, Y, each of size k, and connecting every vertex of X ∪ Y with every vertex of V. It is Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:23 clear that there is a fractional (X, Y )-separator of weight 2, but every (X, Y )-separator S has to fully contain at least one of X, Y, or V, implying ρH (S) ≥ k.

A less naive question is whether a fractional (X, Y )-separator with weight w in H implies that there exists an (X, Y )-separator S with ρ∗ (S) = O(w) (or at most f (w) for some H function f ). It can be shown that this is not true either: using the hypergraph family presented in [Marx 2011, Section 5], one can construct counterexamples where the minimum weight of a fractional (X, Y )-separator is a constant, but ρ∗ (S) has to be arbitrarily large H for every (X, Y )-separator S (we omit the details).

We will characterize fractional separation in a very diﬀerent way. We show that if there is a fractional (A, B)-separator of weight w, then there is an (A, B)-separator S with b(S) = O(w) for every edge-dominated monotone submodular function b. Note that this separator S can be diﬀerent for diﬀerent functions b, so we are not claiming that there is a single (A, B)-separator S that is small in every b. The converse is also true, thus this gives a novel characterization of fractional separation, tight up to a constant factor. This result is the key idea that allows us to move from the domain of submodular functions to the domain of pure hypergraph properties: if there is no (A, B)-separator such that b(S) is small, then we know that there is no small fractional (A, B)-separator, which is a property of the hypergraph H only and has no longer anything to do with the submodular function b.

To overcome the second diﬃculty, we introduce a transformation that turns a monotone submodular function b on V (H) into a function b∗ that encodes somehow the neighborhood structure of H as well. The new function b∗ is no longer monotone and submodular, but it has a number of remarkable properties, for example, b∗ remains edge dominated and b∗ (S) ≥ b(S) for every set S ⊆ V (H), implying that b∗ -width is not smaller than b-width.

The main idea is to prove Theorem 5.1 for b∗ -width instead of b-width (note that this makes the statement stronger). Because of the way b∗ encodes the neighborhoods, the second diﬃculty will disappear: for example, it will be true that b∗ (A ∪ B) = b∗ (A) + b∗ (B) if there are no edges between A and B, that is, b∗ is additive on disjoint components.

Lemma 5.6 formulates (in a somewhat technical way) the exact property of b∗ that we will need.

Furthermore, luckily it turns out that the result mentioned in the previous paragraph remains true with b replaced by b∗ : if there is a fractional (A, B)-separator of weight w, then there is an (A, B)-separator S such that not only b(S), but even b∗ (S) is O(w).

–  –  –

Thus bπ (Z) is the sum of the marginal values with respect to a given ordering, while b∗ (Z) is the smallest possible sum taken over all possible orderings. Let us prove some simple properties of the function b∗. Properties (1)–(3) and their proofs show why b∗ was deﬁned

–  –  –

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:25

Prop. 5.2(3) implies that ∂bw,Z can be used to deﬁne a fractional independent set:

Lemma 5.3.

Let H be a hypergraph and let b be an edge-dominated monotone submodular function deﬁned on V (H) with b(∅) = 0. Let W ⊆ V (H) and let π be an ordering of W.

Let us deﬁne µ(v) = ∂bπ,W (v) for v ∈ W and µ(v) = 0 otherwise. Then µ is a fractional independent set of H with µ(W ) = bπ (W ).

Proof. Let e be an edge of H and let Z := e ∩ W. We have µ(e) = µ(Z) = ∂bπ,W (Z) ≤ ∂bπ,Z (Z) = bπ (Z) = b(Z) ≤ 1, where the ﬁrst inequality follows from Prop. 5.2(4), the last equality follows from Prop. 5.2(3), and the second inequality follows from the fact that b is edge dominated.

Furthermore, we have µ(W ) = ∂bπ,W (W ) = bπ (W ).

We close this section by proving the main property of b∗ that allows us to avoid the second diﬃculty described at the beginning of Section 5. First, although it is not used directly, let

us state that b∗ is additive on sets that are independent from each other:

Lemma 5.4.

Let H be a hypergraph, let b be an edge-dominated monotone submodular function deﬁned on V (H) with b(∅) = 0, and let A, B ⊆ V (H) be disjoint sets such that there is no edge intersecting both A and B. Then b∗ (A ∪ B) = b∗ (A) + b∗ (B).

Proof. By Prop. 5.2(6), we have to show only b∗ (A ∪ B) ≥ b∗ (A) + b∗ (B). Let π be an ordering of V (H) such that bπ (A ∪ B) = b∗ (A ∪ B); we can assume that π starts with the vertices of A ∪ B. Since there is no edge that intersects both A and B, and no vertex outside − − A ∪ B precedes a vertex u ∈ A ∪ B, we have Nπ (u) ⊆ A for every u ∈ A and Nπ (u) ⊆ B for every u ∈ B. Thus ∂bπ,A∪B (u) = ∂bπ,A (u) for every u ∈ A and ∂bπ,A∪B (u) = ∂bπ,B (u) for every u ∈ B. Therefore, b∗ (A ∪ B) = bπ (A ∪ B) = bπ (A) + bπ (B) ≥ b∗ (A) + b∗ (B), what we had to show.

The actual statement that we use is more complicated than Lemma 5.4: there can be edges between A and B, but we assume that there is a small (A, B)-separator. We want to

generalize the following simple statement to our setting:

Proposition 5.5. Let G be a graph, W ⊆ V (G) a set of vertices, A, B ⊆ W two disjoint subsets, and an (A, B)-separator S. If |S| |A|, |B|, then |(C ∩ W ) ∪ S| |W | for every component C of G \ S.

The proof of Prop. 5.5 is easy to see: every component C of G \ S is disjoint from either A or B, thus |C ∩ W | is at most |W | − min{|A|, |B|} |W | − |S|, implying that |(C ∩ W ) ∪ S| is less than |W |. Statements of this form are useful when constructing tree decompositions in a recursive way. In our setting, we want to measure the size of the sets using the function b∗, not by the number of vertices. More precisely, we measure the size of S and (C ∩ W ) ∪ S using b∗, while the size of W, A, and B are measured using the fractional independent set

µ deﬁned by Lemma 5.3. The reason for this will be apparent in the proof of Lemma 5.10:

we want to claim that if such a separator S does not exist for any A, B ⊆ W, then W is a (µ, λ)-connected set for this fractional independent set µ.

Lemma 5.6.

Let H be a hypergraph, let b be an edge-dominated monotone submodular function deﬁned on V (H) with b(∅) = 0 and let W be a set of vertices. Let πW be an ordering of V (H), and let µ(v) := ∂bπW,W (v) for v ∈ W and µ(v) = 0 otherwise. Let A, B ⊆ W be two disjoint sets, and let S be an (A, B)-separator. If b∗ (S) µ(A), µ(B), then b∗ ((C ∩ W ) ∪ S) µ(W ) for every component C of H \ S.

Proof. Let C be a component of H \ S and let Z := (C ∩ W ) ∪ S. Let πS be the ordering reaching the minimum in the deﬁnition of b∗ (S). Let us deﬁne the ordering π that starts with S in the order of πS, followed by C ∩ W in the order of πW, and ﬁnished by

–  –  –

b∗ (Z) ≤ bπ (Z) = ∂bπ,Z (v) ≤ b∗ (S) + µ(C ∩ W ) ∂bπ,Z (v) + v∈S v∈C∩W µ(A) + µ(W \ A) = µ(W ).

5.2. Submodular separation This section is devoted to understanding what fractional separation means: we show that having a small fractional (A, B)-separator is essentially equivalent to the property that for every edge-dominated submodular function b, there is an (A, B)-separator S such that b(S) is small. The proof is based on a standard trick that is often used for rounding fractional solutions for separation problems: we deﬁne a distance function and show by an averaging argument that cutting at some distance t gives a small separator. However, in our setting, we need signiﬁcant new ideas to make this trick work: the main diﬃculty is that the cost function b is deﬁned on subsets of vertices and is not a modular function deﬁned by the cost of vertices. To overcome this problem, we use the deﬁnitions in Section 5.1 (in particular, the function ∂bπ (v)) to assign a cost to every single vertex.

Theorem 5.7. Let H be a hypergraph, X, Y ⊆ V (H) two sets of vertices, and b :

V (H) → R+ an edge-dominated monotone submodular function with b(∅) = 0. Suppose that s is a fractional (X, Y )-separator of weight at most w. Then there is an (X, Y )-separator S ⊆ V (H) with b(S) ≤ b∗ (S) = O(w).

Proof. The total weight of the edges covering a vertex v is e∈E(H),v∈e s(e); let us deﬁne x(v) := min{1, e∈E(H),v∈e s(e)}. It is clear that if P is a path from X to Y, then v∈P x(v) ≥ 1. We deﬁne the distance d(v) to be the minimum of v ∈P x(v ), taken over all paths from X to v (this means that d(v) = x(v) for every v ∈ X, that is, d(v) 0 is possible for v ∈ X). It is clear that d(v) ≥ 1 for every v ∈ Y. Let us associate the closed interval ι(v) = [d(v) − x(v), d(v)] to each vertex v. If v is in X, then the left endpoint of ι(v) is 0, while if v is in Y, then the right endpoint of ι(v) is at least 1.

Let u and v be two adjacent vertices in H such that d(u) ≤ d(v). It is easy to see that d(v) ≤ d(u) + x(u): there is a path P from X to u such that u ∈P x(u ) = d(u), thus the path P obtained by appending v to P has v ∈P x(v ) = u ∈P x(u )+x(v) = d(u)+x(v).

Therefore, we have:

Claim 1. If u and v are adjacent, then ι(u) ∩ ι(v) = ∅.

The class of a vertex v ∈ V (H) is the largest integer κ(v) such that x(v) ≤ 2−κ(v), and we deﬁne κ(v) := ∞ if x(v) = 0. Recall that x(v) ≤ 1, thus κ(v) is nonnegative. The oﬀset of a vertex v is the unique value 0 ≤ α 2 · 2−κ(v) such that d(v) = i(2 · 2−κ(v) ) + α for some integer i. In other words, if the class is 0, 1, 2,..., the oﬀset is d(v) modulo 2, 1, 1/2,..., respectively. Let us deﬁne an ordering π = (v1,..., vn ) of V (H) such that — κ(v) is nondecreasing, — among vertices having the same class, the oﬀset is nondecreasing.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |

Similar works:

«The Perfumer’s Apprentice www.perfumersapprentice.com (Disclaimer: this article was written in 1961, when attitudes towards women in perfumery and women in general were quite different than what they are now. I hope that readers of this paper can take this into consideration, and passages referring to women can just be read as though the author had referred instead to the consumer in general, both men and women.) A Method of Creation in Perfumery By Jean Carles (1961) Part 2 Accords with...»

«A Problem Course on Projective Planes Version 0.4 Stefan Bilaniuk Department of Mathematics Trent University Peterborough, Ontario Canada K9J 7B8 E-mail address: sbilaniuk@trentu.ca 1991 Mathematics Subject Classiﬁcation. 51 Key words and phrases. projective plane To Prof. F.A. Sherk, who got me interested in this topic. Abstract. This is a text for a problem-oriented course on projective planes. Copyright c 2001-2005 Stefan Bilaniuk. Permission is granted to copy, distribute and/or modify...»

«CATALYTIC EMISSION CONTROL WITH RESPECT TO CH4 AND CO FOR HIGHLY EFFICIENT GAS FUELED DECENTRALISED HEAT AND POWER PRODUCTION Jan de Wit1), Keld Johansen2), Poul L. Hansen2), Helle Rossen2), Niels B. Rasmussen1) 1) Danish Gas Technology Centre (DGC) Dr. Neergaardsvej 5B 2970 Hoersholm DK-Denmark, 2) Haldor Topsoe A/S Nymoellevej 55 2800 Lyngby DK-Denmark ABSTRACT A new Rhodium (Rh) based monolithic catalyst has been developed for oxidation of carbonmonoxide (CO), methane and other hydrocarbons...»

«SNE Student project Information retrieval from a TomTom Nike+ smart watch Leendert van Duijn & Hristo Dimitrov June 1, 2014 TomTom Nike+ sport watch Image: http://ecx.images-amazon.com/images/I/414rF-Fk7HL._SY300_.jpg I Abstract Smart watches can be used to collect data, an example is the Nike+ Sportwatch. It can collect GPS data so you can keep track of your exercises. This information can be a wealth of information in an investigation to show that someone did, or did not, visit a particular...»

«01 Perennial crops: needs, perceptions, essentials 02 Perennial rice: challenges and opportunities 03 The progression of perennial rice breeding and genetics research in China 04 Perennial wheat breeding: current germplasm and a way forward for breeding and global cooperation 05 Evaluation of nine perennial wheat derivatives grown in Italy 06 Current efforts to develop perennial wheat and domesticate Thinopyrum intermedium as a perennial grain 07 Viewpoint: multiple-harvest sorghums toward...»

«PALINDROMIC PRIMITIVES AND PALINDROMIC BASES IN THE FREE GROUP OF RANK TWO ADAM PIGGOTT Abstract. The present paper records more details of the relationship between primitive elements and palindromes in F2, the free group of rank two. We characterize the conjugacy classes of palindromic primitive elements as those in which cyclically reduced words have odd length. We identify large palindromic subwords of certain primitives in conjugacy classes which contain cyclically reduced words of even...»

«Sediment Dynamics and the Hydromorphology of Fluvial Systems (Proceedings of a symposium held in 64 Dundee, UK, July 2006). IAHS Publ. 306, 2006. Episodic discharge of coarse sediment in a mountain torrent RICHARD JOHNSON1 & JEFF WARBURTON2 1 School of Natural Resources, University of Central Lancashire, Penrith Campus, Penrith, Cumbria CA11 0AH, UK rmjohnson1@uclan.ac.uk 2 Catchment, Hillslope and River Science Research Group, Department of Geography, Durham University, Science Laboratories,...»

«Getting Started with AWS Getting Started with AWS Getting Started with AWS Getting Started with AWS Copyright © 2016 Amazon Web Services, Inc. and/or its affiliates. All rights reserved. Amazon's trademarks and trade dress may not be used in connection with any product or service that is not Amazon's, in any manner that is likely to cause confusion among customers, or in any manner that disparages or discredits Amazon. All other trademarks not owned by Amazon are the property of their...»

«UNCHRISTIAN AMERICA Living with faith in a nation that was never under God MICHAEL BABCOCK, PH.D. AN IMPRINT OF TYNDALE HOUSE PUBLISHERS, INC. Visit Tyndale’s exciting Web site at www.tyndale.com TYNDALE is a registered trademark of Tyndale House Publishers, Inc. SaltRiver and the SaltRiver logo are registered trademarks of Tyndale House Publishers, Inc. UnChristian America: Living with Faith in a Nation That Was Never under God Copyright © 2008 by Michael A. Babcock. All rights reserved....»

«Holding Child Support Orders of Incarcerated Payers in Abeyance: Final Evaluation Report Jennifer L. Noyes, Maria Cancian, and Laura Cuesta Institute for Research on Poverty University of Wisconsin–Madison September 2012 This report has been prepared as part of the Child Support Research Agreement between the Wisconsin Department of Children and Families and the Institute for Research on Poverty. Any views expressed in this paper are those of the authors and not necessarily those of the...»

«Journal of Statistical Planning and Inference 139 (2009) 1243 1245 Contents lists available at ScienceDirect Journal of Statistical Planning and Inference journal homepage: w w w. e l s e v i e r. c o m / l o c a t e / j s p i Discussion of reified Bayesian modelling and inference for physical systems by Michael Goldstein and Jonathan Rougier Michael Lavinea,∗, Gabriele C. Hegerlb, Susan Lozierc a University of Massachusetts, Amherst, MA 01003-9305, USA b School of Geosciences, The...»

«Operating Instruction 750 W 24 V F-Pickup CQF 04/2 + Interface M12 Order Number 91212-332-3108051 BAL9100-0131b-E www.conductix.com Translated document page 1 of 36 Operating Instruction 750 W 24 V F-Pickup CQF 04/2 + Interface M12 Index page 1  Symbols and Hints 2  Advisory Information for the User 3  Intended Purpose 4  Technical Data 4.1  Electrical Data 4.2  Environmental Data 4.3  Protection Features 4.4  Mechanical Integration 4.5  Electrical Connections 4.5.1  Connection of DC...»

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