FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 11 |

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

-- [ Page 4 ] --

1. Because in our case we want to control the size of the constraint relations, we need a notion of depth that is sensitive to “what the edges see.” We define the depth dψ (e) of an edge e ∈ E(H) as dψ (e) = v∈e dψ (e) and the edge depth to be the maximum of e taken over all edges e ∈ E(H). Equivalently, we can define the depth of an edge e ∈ H as dψ (e) = v∈V (G) |ψ(v) ∩ e|, that is, each vertex v contributes |ψ(v) ∩ e| to the depth. (A different, perhaps more natural, definition of edge depth would be to define it simply as a maximum number of sets ψ(v) that intersect an edge. Somewhat unexpectedly, most results of the paper remain true with both notions; see Remarks 7.6–7.7.) Trivially, for any graph G and hypergraph H, there is an embedding of G into H having vertex depth and edge depth at most |V (G)|. If G has m edges and no isolated vertices, then |V (G)| is at most 2m. We are interested in how much we can gain compared to this trivial solution of depth O(m). We define the embedding power emb(H) to be the maximum (supremum) value of α for which there is an integer mα such that every graph G with m ≥ mα edges has an embedding into H with edge depth m/α. It might look unmotivated that we define embedding power in terms of the number of edges of G: defining it in terms of the number of vertices might look more natural. However, if we replace the number m of edges with the number n of vertices in the definition, then the worst case occurs if G is a clique on n vertices. Such a definition would describe how well cliques can be embedded, and would give us no information about how sparse graphs can be embedded.

3. WIDTH PARAMETERS Treewidth and its various generalizations are defined in this section. We follow the framework of width functions introduced by Adler [2006]. A tree decomposition of a hypergraph H is a tuple (T, (Bt )t∈V (T ) ), where T is a tree and (Bt )t∈V (T ) is a family of subsets of V (H) satisfying the following two conditions: (1) for each e ∈ E(H) there is a node t ∈ V (T ) such that e ⊆ Bt, and (2) for each v ∈ V (H) the set {t ∈ V (T ) | v ∈ Bt } is connected in T. The sets Bt are called the bags of the decomposition. Let f : 2V (H) → R+ be a function that assigns a nonnegative real number to each nonempty subset of vertices. The f -width of a tree-decomposition (T, (Bt )t∈V (T ) ) is max f (Bt ) | t ∈ V (T )}. The f -width of a hypergraph H is the minimum of the f -widths of all its tree decompositions. In other words, f -width(H) ≤ w if and only if there is a tree decomposition of H where f (B) ≤ w for every bag B.

The main idea of tree decomposition based algorithms is that if we have a tree decomposition for instance I such that at most C assignments on Bt have to be considered for each bag Bt, then the problem can be solved by dynamic programming in time polynomial in C and I. The various width notions try to guarantee the existence of such decompositions.

The simplest such notion, treewidth, can be defined as follows:

Definition 3.1. Let s(B) = |B| − 1. The treewidth of H is tw(H) := s-width(H).

Further width notions defined in the literature can also be conveniently defined using this setup. A subset E ⊆ E(H) is an edge cover if e∈E e = V (H). The edge cover number ρ(H) is the size of the smallest edge cover (here we assume that H has no isolated vertices).

For X ⊆ V (H), let ρH (X) be the size of the smallest set of edges covering X.

Definition 3.2. The generalized hypertree width of H is hw(H) := ρH -width(H).

The original (nongeneralized) definition [Gottlob et al. 2002a] of hypertree width includes an additional requirement on the decomposition (we omit the details), thus it cannot be

–  –  –

A crucial idea in [Marx 2011] is to make the choice of tree decomposition adaptive:

instead of assigning a single decomposition to each hypergraph, we choose the best decomposition based on additional properties of the current instance. Motivated by this idea, we generalize the notion of f -width from a single function f to a class of functions F. Let H be a hypergraph and let F be an arbitrary (possibly infinite) class of functions that assign nonnegative real numbers to nonempty subsets of vertices of H. The F-width of H is F-width(H) := sup f -width(H) | f ∈ F. Thus if F-width(H) ≤ k, then for every f ∈ F, hypergraph H has a tree decomposition with f -width at most k. Note that this tree decomposition can be different for the different functions f. For normalization purposes, we consider only functions f on V (H) that satisfy f (∅) = 0 and that are edge-dominated, that is, f (e) ≤ 1 holds for every e ∈ E(H).

Using these definitions, we can define adaptive width, introduced in [Marx 2011], as follows. Recall that in Section 2, we stated that if µ is a fractional independent set, then µ is extended to subsets of vertices by defining µ(X) := v∈X µ(v) for every X ⊆ V (H).

Definition 3.4. The adaptive width adw(H) of a hypergraph H is F-width(H), where F is the set of all fractional independent sets of H.

A function f : 2V (H) → R is modular if f (X) = v∈X cv for some constants cv (v ∈ V (H)).

The function µ(X) arising from a fractional independent set is clearly a modular and edge dominated function, in fact, in Definition 3.4 we can equivalently define F as the set of all nonnegative modular edge-dominated functions on V (H). The main new definition of the paper is a new width measure, which is obtained by imposing a requirement weaker than

modularity on the functions in F (hence the considered set F of functions is larger):

Definition 3.5. A function b : 2V (H) → R+ is submodular if b(X) + b(Y ) ≥ b(X ∩ Y ) + b(X ∪ Y ) holds for every X, Y ⊆ V (H). Given a hypergraph H, let F contain every edge-dominated monotone submodular function b on V (H) with b(∅) = 0. The submodular width of hypergraph H is subw(H) := F-width(H).

It is well-known that submodular functions can be equivalently characterized by the property that b(X ∪ v) − b(X), the marginal value of v with respect to X, is a nonincreasing function of X. That is, for every v and X ⊆ Y, b(X ∪ v) − b(X) ≥ b(Y ∪ v) − b(Y ). (1) It is clear that subw(H) ≥ adw(H): Definition 3.5 considers a larger set of functions than Definition 3.4. Furthermore, we show that subw(H) is at most the fractional hypertree width fhw(H). This is a straightforward consequence of the fact that an edge-dominated

submodular function is always bounded by the fractional cover number:

Lemma 3.6.

Let H be a hypergraph and b be a monotone edge-dominated submodular function with b(∅) = 0. Then b(S) ≤ ρ∗ (S) for every S ⊆ V (H).


–  –  –

(the equality is a simple telescopic sum; the inequality uses (1), i.e., the marginal value of vi with respect to Vi−1 is not greater than with respect to e ∩ Vi−1 ).

–  –  –

(in the first inequality, we use that f is edge dominated; in the last inequality, we use that γ is a fractional edge cover).

Proposition 3.7. For every hypergraph H, subw(H) ≤ fhw(H).

Proof. Let (T, Bt∈V (T ) ) be a tree decomposition of H whose ρ∗ -width is fhw(H). If b is H an edge-bounded monotone submodular function with b(∅) = 0, then by Lemma 3.6, b(Bt ) ≤ ρ∗ (Bt ) ≤ fhw(H) for every bag Bt of the decomposition, i.e., b-width(H) ≤ fhw(H). This H is true for every such function b, hence subw(H) ≤ fhw(H).

Since adw(H) ≤ subw(H) ≤ fhw(H), if a class H of hypergraphs has bounded fractional hypertree width, then it has bounded submodular width, and if a class H has bounded submodular width, then it has bounded adaptive width. Surprisingly, it turns out that the latter implication is actually an equivalence: Corollary 6.10 shows that subw(H) is at most O(adw(H)4 ), thus a class of hypergraphs has bounded submodular width if and only if it has bounded adaptive width. In other words, large submodular width can be certified already by modular functions: if submodular width is unbounded in H and we want to choose an H ∈ H and a submodular function b such that the b-width of H is larger than some constant k, then we can choose H and b such that b is actually modular. There is no intuitive reason why this is true: submodular functions seem to be much more powerful than modular functions. Still, we obtain this result as a byproduct of our characterization of submodular width.

There is no such connection between adaptive width and fractional hypertree width: it is shown in [Marx 2011] that there is a class of hypergraphs with bounded adaptive width and unbounded fractional hypertree width. Thus the property bounded fractional hypertree width is a strictly weaker property than bounded adaptive/submodular width.

Figure 2 shows the relations of the hypergraph properties defined in this section (note that the elements of this Venn diagram are sets of hypergraphs; e.g., the set “bounded treewidth” contains every set H of hypergraphs with bounded treewidth). As discussed above, all the inclusions in the figure are proper.

Finally, let us remark that there have been investigations of tree decompositions and branch decompositions of submodular functions and matroids in the literature [Hlinˇn´ ey and Oum 2008; Oum and Seymour 2007; Hlinˇn´ and Whittle 2006; Hlinˇn´ 2005; Amini ey ey

et al. 2009]. However, in those results the submodular function is a connectivity function:

b(S) describes the boundary of S, that is, the cost of separating S from its complement. In

–  –  –

Fig. 2. Hypergraph properties that make CSP fixed-parameter tractable.

our case, b(S) describes the cost of the separator S itself. Therefore, we are in a completely different setting and the previous results cannot be used.


In this section, we prove the main algorithmic result of the paper: CSP(H) is fixed-parameter tractable if H has bounded submodular width.

Theorem 4.1.

Let H be a class of hypergraphs such that subw(H) ≤ c0 for every O(|V (H)|) H ∈ H. Then CSP(H) can be solved in time 2c0 ·2 · I O(c0 ).

The proof of Theorem 4.1 is based on two main ideas:

(1) A CSP instance I can be decomposed into a bounded number of “uniform” CSP instances I1,..., It (Lemma 4.11). Here uniform means that if B ⊆ A are two sets of variables, then every solution of prB Ij has roughly the same number of extensions to prA Ij.

(2) If I is a uniform CSP instance, then (the logarithm of) the number of solutions on the different projections of I can be described by an edge-dominated monotone submodular function b (Lemma 4.12). Therefore, if the hypergraph H of I has bounded submodular width, then it follows that there is a tree decomposition where every bag has a polynomially bounded number of solutions. This means that the existence of a solution can be tested by standard techniques.

While our algorithm is based on these two ideas, the technical implementation is slightly different. First, we can achieve uniformity only on “small sets” of variables. For technical reasons, we have to ensure a certain consistency condition (for example, in order to ensure that the submodular function b is monotone). It follows from the consistency condition that when we find a tree decomposition for a uniform instance such that every bag has a small number of solutions, then this automatically implies that the instance has a solution; we do not even have to use the tree decomposition (see Lemma 4.7).

In Section 4.1 we define the notion of consistency that we use and discuss how it can be achieved. Section 4.2 describes how the instance can be partitioned into uniform instances.

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:15 Section 4.3 shows how a submodular function can be defined based on a uniform instance, connecting our algorithm to submodular width.

4.1. Consistency Recall from Section 2 that prA I is instance I projected to a set A of variables and solI (A) is the set of all solutions of prA I. Note that, in general, it is possible that | solI (S )| | solI (S)| for some S ⊂ S. In the implementation of the first idea (Lemma 4.11), we guarantee uniformity only to subsets of variables that are “small” in the following hereditary sense Definition 4.2. Let I be a CSP instance and M ≥ 1 an integer. We say that S ⊆ V is M -small if | solI (S )| ≤ M for every S ⊆ S.

It is not difficult to find all the M -small sets, and every solution of the instances projected

onto these sets:

Lemma 4.3.

Let I = (V, D, C) be a CSP instance and M ≥ 1 an integer. There is an algorithm with running time 2O(|V |) · poly( I, M ) that finds the set S of all M -small sets S ⊆ V and constructs solI (S) for each such S ∈ S.

Proof. For i = 1, 2,..., |V |, we find every M -small set S of size i and construct solI (S).

This is trivial to do for i = 1. Suppose that we have already found the collection Si of all M -small sets of size exactly i. By definition, every size i subset S of an M -small set S of size i + 1 is an M -small set. Thus we can find every M -small set of size i + 1 by enumerating every S ∈ Si and checking for every v ∈ V \ S whether S := S ∪ {v} is M -small. To check whether S is M -small, we first check whether every subset of size i is M -small, which is easy to do using the set Si. Then we construct solI (S ): this can be done by enumerating every tuple s ∈ solI (S) and every extension of s by a new value from D. Thus we need to consider at most | solI (S)| · |D| ≤ M · |D| tuples as possible members in solI (S ), which means that solI (S ) can be constructed in time polynomial in M and I. If | solI (S )| ≤ M, then we put S into Si+1. As the collection Si contains at most 2|V | sets and every operation is polynomial in M and I, the total running time is 2O(|V |) · poly( I, M ).

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 11 |

Similar works:

«  December 2, 2013 Via E-Mail (rule-comments@sec.gov) Ms. Elizabeth M. Murphy, Secretary Securities and Exchange Commission 100 F. Street, N.E. Washington, D.C. 20549-1090 Re: File No. S7-07-13— Proposed Rule to Implement Section 953(b) of the Dodd-Frank Wall Street Reform and Consumer Protection Act of 2010 Dear Ms. Murphy: Meridian Compensation Partners, LLC (“Meridian”) is pleased to provide comments to the Securities and Exchange Commission (“Commission”) on the Commission’s...»


«Chapter 2 The Terrestrial Planets General View Unlike the gaseous giant planets, which are preserved essentially unmodified in structure and composition since their origin 4.55 billion years ago, the terrestrial (inner) planets (Fig. 2.1) experienced dramatic changes in the course of their evolution. This is evident in their interior structure, geology, surface landforms, and atmospheres (Fig. 2.2a). The evolution of the inner planets was mainly controlled by both endogenous and exogenous...»

«The Paperweight Chase Newsletter of the Paperweight Collectors Association, Ontario, Canada Number 12 February 2008 Silent Auction from the John Gooderham Collection We send our warm thanks to Jennine O’Connor, daughter of our dear friend and former artist member, John Gooderham, who provided a variety of pieces from her late father’s personal collection for auction at our December Holiday Social. All items except one were taken home by delighted members who had great fun in the bidding...»

«Nieuwsbrief Stichting NGID Nieuwsbrief Stichting NGID Nieuwsbrief Stichting NGID Namens het bestuur: We hebben net de themadag Opschool achter de rug en 55 deelnemers hebben een fijne dag gehad. In deze nieuwsbrief vindt u een artikel en fotoreportage over deze dag. De andere activiteiten voor 2012 hebben we moeten annuleren vanwege onvoldoende belangstelling. Deze activiteiten waren een voortvloeisel van de in 2011 gehouden enquête, maar er bleek onvoldoende draagkracht onder de...»

«Hkkjr oSxu BHARAT WAGON & ENGG. CO. LTD oSxu BWEL INFORMATION ON BWEL IN ACCORDANCE WITH RTI ACT 2005 In accordance with the provisions of the Right to Information Act, 2005 and in compliance with chapter II section 4(1) sub clause (b), the following information is placed: Compliance under Section 4(1)(b) of Right to information Act, 2005 Chapter Particulars I Particulars of Organisation, Functions and Duties II Powers and duties of BWEL Officers and employees III Procedure followed in the...»

«THE CORPORATION OF THE TOWN OF ESSEX BY-LAW #321 Being a by-law to provide for Backflow Prevention. WHEREAS Municipal Corporations are authorized to enact by-laws pursuant to the provisions ofPart 7;ofthe Ontario Building Code S.O. 1997 (Ontario Regulation 403/97) as amended to more·particularly provide for backflow prevention and regulate the connection of individual :water services to the municipal potable water supply system; AND WHEREAS within the scope ofPart 9 of Ontario Regulation...»

«Uncle Howard Page 1 of 65 AS BROADCAST TRANSCRIPT SEPTEMBER 30, 2015 TRANSCRIBED BY : AJ PROCESSING 00:00:01 BEGIN 00:00:01 GRAPHIC: Uncle Howard Dur: 96:40 1920x1080 23.98PsF Element at end 24/11/2015 00:00:13 GRAPHIC: PINBALL LONDON 00:00:18 GRAPHIC: Pinball London presents 00:00:22 GRAPHIC: In association with Creative Europe Jerome Foundation The Filmmaker Fund IFP Bertha Foundation 00:00:45 GRAPHIC: a Pinball London production 00:00:52 GRAPHIC: a film by Aaron Brookner 00:00:57 JOHN:...»

«CLIENT ADVICE JOURNEY WITH SCRUTTON BLAND LIMITED INDEPENDENT FINANCIAL ADVISERS Client Details: «Client_Report_Name» «Client_Address_1» «Client_Address_2» «Client_Address_3» «Client_Address_4» «Client_Address_5» «Client_Postcode» Scrutton Bland Ltd is authorised and regulated by the Financial Conduct Authority CONTENTS 1 ADVISERS PROFILES 2 CLIENT JOURNEY 3 SCRUTTON BLAND LIMITED’S METHODOLOGY 4 THE REVIEW SERVICE 5 FEE MENU Adviser Profile Neil Hewitt, APFS, AIFP, Certified...»

«International Electronic Journal of Elementary Education, 2013, 6(1), 95-116. Mother Tongue Tuition in Sweden Curriculum Analysis and Classroom Experience Anne REATH WARREN∗ Stockholm University, Sweden Received: 19 April 2013 / Revised: 11 June 2013 / Accepted: 21 October 2013 Abstract The model of Mother Tongue Tuition (MTT) which has developed in Sweden since the 1970’s offers speakers of languages other than Swedish the opportunity to request tuition in their mother tongue, from...»

«Villes de Colombes et de Nanterre Direction régionale des affaires culturelles d’Ile-de-France Conseil départemental des Hauts-de-Seine TERRITOIRES EN MUTATION APPEL A CANDIDATURE En direction d’artistes en vue de 4 résidences-missions menées en faveur des habitants des villes de Colombes et de Nanterre (92) prenant place dans le cadre du Contrat local d’éducation artistique (CLEA) pour l’année 2016-2017 sur la thématique suivante : Territoires en mutation. Cadre des...»

«RÉPUBLIQUE DÉMOCRATIQUE DU CONGO La République démocratique du Congo (RDC) est une république nominalement centralisée, possédant une population d’environ 68 millions d’habitants. Le président et la chambre basse du parlement (Assemblée nationale) sont élus au suffrage populaire ; les membres de la chambre haute (Sénat) sont nommés par les assemblées provinciales. Les élections présidentielles et à la chambre basse de 2006, qui ont mis en lice plusieurs partis, ont été...»

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