FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 || 3 | 4 |   ...   | 11 |

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

-- [ Page 2 ] --

If there is a compuable function f and a recursively enumerable class H of hypergraphs with bounded edge size and unbounded treewidth such that the problem CSP(H) can be solved in time f (H) I o(tw(H)/ log tw(H)) for instances I with hypergraph H ∈ H, then ETH fails.

This means that the treewidth-based algorithm is almost optimal on every class of hypergraphs: in the exponent only an O(log tw(H)) factor improvement is possible. It is conjectured in [Marx 2010b] that Theorem 1.2 can be made tight, i.e., the lower bound holds even if the logarithmic factor is removed from the exponent.

Conjecture 1.3 (Marx [2010b]). If H is a class of hypergraphs with bounded edge size, then there is no algorithm that solves CSP(H) in time f (H) I o(tw(H)) for instances I with hypergraph H ∈ H, where f is an arbitrary function.

Unbounded arities. The situation is less understood in the unbounded arity case, i.e., when there is no bound on the maximum edge size in H. First, the complexity in the unbounded-arity case depends on how the constraints are represented. In the bounded-arity case, if each constraint contains at most r variables (r being a fixed constant), then every reasonable representation of a constraint has size |D|O(r). Therefore, the size of the different representations can differ only by a polynomial factor. On the other hand, if there is no bound on the arity, then there can be exponential difference between the size of succinct representations (e.g., formulas [Chen and Grohe 2010]) and verbose representations (e.g., truth tables [Marx 2011]). The running time of an algorithm is expressed as a function of the input size, hence the complexity of the problem can depend on how the input is represented: longer representation means that it is potentially easier to obtain a polynomialtime algorithm.

The most well-studied representation of constraints is listing all the tuples that satisfy the constraint. This representation is perfectly compatible with our database-theoretic motivation: the constraints are relations of the database, and a relation is physically stored as a table containing all the tuples in the relation. For this representation, there are classes H with unbounded treewidth such that CSP restricted to this class is polynomial-time solvable. A trivial example is the class H of all hypergraphs having only a single hyperedge of Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

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

arbitrary size. The treewidth of such hypergraphs can be arbitrarily large (as the treewidth of a hypergraph consisting of a single edge e is exactly |e| − 1), but CSP(H) is trivial to solve: we can pick any tuple from the constraint corresponding to the single edge. There are other, nontrivial, classes of hypergraphs with unbounded treewidth such that CSP(H) is solvable in polynomial time: for example, classes with bounded (generalized) hypertree width [Gottlob et al. 2002b], bounded fractional edge cover number [Grohe and Marx 2012], and bounded fractional hypertree width [Grohe and Marx 2012; Marx 2010a]. Thus, unlike in the bounded-arity case, treewidth is not the right measure for characterizing the complexity of the problem.

Our results. We introduce a new hypergraph width measure that we call submodular width. Small submodular width means that for every monotone submodular function b on the vertices of the hypergraph H, there is a tree decomposition where b(B) is small for every bag B of the decomposition. (This definition makes sense only if we normalize the considered functions: for this reason, we require that b(e) ≤ 1 for every edge e of H.) The main result of the paper is showing that bounded submodular width is the property that

precisely characterizes the complexity of CSP(H):

Theorem 1.4 (Main).

Let H be a recursively enumerable class of hypergraphs. Assuming the Exponential Time Hypothesis, CSP(H) parameterized by H is fixed-parameter tractable if and only if H has bounded submodular width.

Theorem 1.4 has an algorithmic side (algorithm for bounded submodular width) and a complexity side (hardness result for unbounded submodular width).

Unlike previous width measures in the literature, where small value of the measure suggests a way of solving CSP(H) it is not at all clear how bounded submodular width is of any help. In particular, it is not obvious what submodular functions have to do with CSP instances. The main idea of our algorithm is that a CSP instance can be “split” into a small number of “uniform” CSP instances; for this purpose, we use a partitioning procedure inspired by a result of Alon et al. [2007]. More precisely, splitting means that we partition the set of tuples appearing in the constraint relations in a certain way and each new instance inherits only one class of the partition (thus each new instance has the same set of variables as the original). Uniformity means that for any subset B ⊆ A of variables, every solution for the problem restricted to B has roughly the same number of extensions to A. The property of uniformity allows us to bound the logarithm of the number of solutions on the different subsets by a submodular function. Therefore, bounded submodular width guarantees that each uniform instance has a tree decomposition where only a polynomially bounded number of solutions has to be considered in each bag.

Conceptually, our algorithm goes beyond previous decomposition techniques in two ways.

First, the tree decomposition that we use depends not only on the hypergraph, but on the actual constraint relations in the instance (we remark that this idea first appeared in [Marx 2011] in a different context that does not directly apply to our problem). Second, we are not only decomposing the set of variables, but we also split the constraint relations. This way, we can apply different decompositions to different parts of the solution space.

The proof of the complexity side of Theorem 1.4 follows the same high-level strategy as the proof of Theorem 1.2 in [Marx 2010b]. In a nutshell, the argument of [Marx 2010b] is the following: if treewidth is large, then there is subset of vertices which is highly connected in the sense that the set does not have a small balanced separator; such a highly connected set implies that there is uniform concurrent flow (i.e., a compatible set of flows connecting every pair of vertices in the set); the paths in the flows can be used to embed the graph of a 3SAT formula; and finally this embedding can be used to reduce 3SAT to CSP. These arguments build heavily on well-known characterizations of treewidth and results from combinatorial optimization (such as the O(log k) integrality gap of sparsest cut). The proof of Theorem 1.4 follows this outline, but now no such well-known tools are available: we are

–  –  –

dealing with hypergraphs and submodular functions in a way that was not explored before in the literature. Thus we have to build from scratch all the necessary tools. One of the main

difficulties of obtaining Theorem 1.4 is that we have to work in three different domains:

— CSP instances. As our goal is to investigate the existence of algorithms solving CSP, the most obvious domain is CSP instances. In light of previous results, we are especially interested in algorithms based on tree decompositions. For such algorithms, what matters is the existence of subsets of vertices such that restricting the instance to any of these subsets gives an instance with “small” number of solutions. In order to solve the instance, we would like to find a tree decomposition where every bag is such a small set.

— Submodular functions. Submodular width is defined in terms of submodular functions, thus submodular functions defined on hypergraphs is our second natural domain. We need to understand what large submodular width means, that is, what property of the submodular function and the hypergraph makes it impossible to obtain a tree decomposition where every bag has small value.

— Flows and embeddings in hypergraphs. In the hardness proof, our goal is to embed the graph of a 3SAT formula into a hypergraph. Thus we need to define an appropriate notion of embedding and study what guarantees the existence of embeddings with suitable properties. As in [Marx 2010b], we use the paths appearing in flows to construct embeddings. For our purposes, the right notion of flow is a collection of weighted paths where the total weight of the paths intersecting each hyperedge is at most 1. This notion of flows has not been studied in the literature before, thus we need to obtain basic results on such flows, such as exploring the duality between flows and separators.

A key question is how to find connections between these domains. As mentioned above and detailed in Section 4, we have a procedure that reduces a CSP instance into a set of uniform CSP instances, and the number of solutions on the different subsets of variables in a uniform CSP instance can be described by a submodular function. This method allows us to move from the domain of CSP instances to the domain of submodular functions.

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

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

Section 5 is devoted to showing that if submodular width of a hypergraph is large, then there is a certain “highly connected” set in the hypergraph. Highly connected set is defined as a property of the hypergraph (it requires the existence of certain flows) and has no longer anything to do with submodular functions. Thus this connection allows us to move from the domain of submodular functions to the study of hypergraphs. In Section 6, we show that a highly connected set in a hypergraph means that graphs can be efficiently embedded into the hypergraph. In particular, the graph of a 3SAT formula can be embedded into the hypergraph, which gives us (as shown in Section 7) a reduction from 3SAT to CSP(H). This connection allows us to move from the domain of embeddings back to the domain of CSP instances. We remark that Sections 4–7 are written in a self-contained way: only the first theorem of each section is used outside the section.

A consequence of our characterization of submodular width implies the surprising fact

that bounded submodular width equals bounded adaptive width (defined in [Marx 2011]):

Theorem 1.5.

A class of hypergraphs has bounded submodular width if and only if it has bounded adaptive width.

It is proved in [Marx 2011] that there are classes of hypergraphs having bounded adaptive width (and hence bounded submodular width), but unbounded fractional hypertree width.

Previously, bounded fractional hypertree width was the most general property that was known to guarantee fixed-parameter tractability [Grohe and Marx 2012]. Thus Theorem 1.4 not only gives a complete characterization of the parameterized complexity of CSP(H), but its algorithmic side proves fixed-parameter tractability in a strictly more general case than what was known before.

Why fixed-parameter tractability? We argue that investigating the fixed-parameter tractability of CSP(H) is at least as interesting as investigating polynomial-time solvability.

In problems coming from our database-theoretic motivation, the size of the hypergraph (that is, the size of the query) is assumed to be much smaller than the input size (which is usually dominated by the size of the database), hence a constant factor in the running time depending only on the number of variables (or on the hypergraph) is acceptable3. Even the STOC 1977 landmark paper of Chandra and Merlin [1977], which started the complexity research on conjunctive queries, suggests spending exponential time (in the size of the query) on finding the best possible evaluation order. Furthermore, the notion of fixed-parameter tractability formalizes the usual viewpoint of the literature on conjunctive queries: in the complexity analysis, we should analyze separately the contribution of the query size and the contribution of the database size.

By aiming for fixed-parameter tractability, we can focus more on the core algorithmic question: is there some method for decomposing the space of all solutions in a way that allows efficient evaluation of the query? Some of the progress in this area was made by introducing new decomposition techniques, without showing how to actually find such decompositions. For example, this was the case for the papers introducing query width [Chekuri and Rajaraman 2000] and fractional hypertree width [Grohe and Marx 2012]: it was shown that if a certain type of decomposition is given, then the problem can be solved in polynomial time. In our terminology, these results already show the fixed-parameter tractability of CSP(H) for the classes H where such decompositions exist (since the time required to find an appropriate decomposition can be bounded by a function of the hypergraph H only), but do not give polynomial-time algorithms. It took some more time and effort to come up with polynomial-time (approximation) algorithms for finding such decompositions [Gottlob et al. 2002a; Marx 2010a]. While investigating algorithms for finding decompositions 3 Thisassumption is valid only for evaluation problems (where the problem instance includes a large database) and not for problems that involves only queries, such as the Conjunctive Query Containment problem.

–  –  –

give rise to interesting and important problems, they are purely combinatorial problems on graphs and hypergraphs, and no longer has anything to do with query evaluation, constraints, or databases. Thus fixed-parameter tractability gives us a formal way of ignoring these issues and focusing exclusively on the evaluation problem.

Pages:     | 1 || 3 | 4 |   ...   | 11 |

Similar works:


«Merger-in-Progress of Tonal Classes in Masan/Changwon Korean Akira Utsugi (RIKEN) Utsugi, Akira. (2009). Merger-in-Progress of Tonal Classes in Masan/Changwon Korean. Language Research 45.1, 23-42. In Masan/Changwon Korean, a dialect in the South Gyeongsang (Kyungsang) Province, two lexical tonal classes—“Final” and “Medial-Double” (MDouble)—have similar phonetic realizations. In data collection, three sets of materials were recorded from younger speakers: (i) words with particles,...»

«1 A Speech by The Rev. Timothy C. Ahrens, 15th Senior Minister, The First Congregational Church, United Church of Christ, 444 East Broad St., Columbus, Ohio 43215 phone: 614-228-1741, ext. 13; tahrens@first-church.org delivered October 1, 2011 at Greenlawn Cemetery, Columbus dedicated to all the men and women who built Greenlawn Cemetery, all who have sustained it through the years and all who have been laid to rest here, including The Rev. Dr. Washington Gladden and his family and always to...»

«BY ORDER OF THE AIR FORCE INSTRUCTION 13-201 SECRETARY OF THE AIR FORCE 20 SEPTEMBER 2001 Space, Missile, Command and Control AIR FORCE AIRSPACE MANAGEMENT COMPLIANCE WITH THIS PUBLICATION IS MANDATORY NOTICE: This publication is available digitally on the AFDPO WWW site at: http://afpubs.hq.af.mil. OPR: HQ AF/XOOR Certified by: HQ USAF/XOO (Maj William J. Mahony Jr.) (Maj Gen Charles R. Henderson) Supersedes AFI 13-201, 20 March 2001. Pages: 57 Distribution: F This instruction implements AFPD...»

«THE PINEAPPLE Chapter 01 Photo Garth Sanewski Version 1, 31 August 2009 Pineapple best practice manual Classification and origins World pineapple production Botanical and physiological adaptations Leaf shape and arrangement Axillary root system Basal white tissue Stomata Trichomes (“leaf hairs”) Water storage tissue CAM photosynthesis Life cycle Stem (butt) Root system Reproduction Flowering Fruit Nutritional, medical and industrial value of pineapple References and further reading...»

«Prospects for the UK Balance of Payments Embargo: 00.01 Saturday 27 March 2010 Prospects for the UK Balance of Payments Ken Coutts and Robert Rowthorn Commentary by Bill Martin Civitas: Institute for the Study of Civil Society London Published March 2010 © Individual authors Civitas 55 Tufton Street London SW1P 3QL Civitas is a registered charity (no. 1085494) and a company limited by guarantee, registered in England and Wales (no. 04023541) email: books@civitas.org.uk All rights reserved ISBN...»

«EMBEDDING HUMAN SKULL BONES IN PERSPEX BLOCKS D. H. TOMPSET Ph.D. Department of Anatomy, Royal College of Surgeons of England Summary A METHOD IS described for embedding human skull bones in rectangular Perspex blocks. Severe tests suggest that such specimens will last a very long time without deterioration. The bones are perfectly protected, and the blocks can be repolished in a few minutes when the surface of the Perspex gets scratched. Introduction IN 1948, AT THE suggestion of Professor R....»

«ANNOTATED LIST OF UTAH TORTRICID MOTHS: A PROVISIONAL COMPILATION Jerry A. Powell Essig Museum of Entomology University of California, Berkeley Microlepidoptera have been relatively neglected in Utah compared to several other western states. During the early part of the descriptive era for western Nearctic micros, 1879-1929, Colorado and California attracted more visitors who collected small moths. California, British Columbia, and Washington had resident microlepidopterists through parts of...»

«SANITATION2004-INDONESIA SANITATION COUNTRY PROFILE INDONESIA Decision -Making A. Basic Sanitation B. Solid Wastes C. Hazardous Wastes D. Radioactive Wastes Programmes and Projects A. Basic Sanitation B. Solid Wastes C. Hazardous Wastes D. Radioactive Wastes Status A. Basic Sanitation B. Solid Wastes C. Hazardous Wastes D. Radioactive Wastes Capacity-Building, Education, Training and Awareness-Raising A. Basic Sanitation B. Solid Wastes C. Hazardous Wastes D. Radioactive Wastes Information A....»

«God’s unchanging Word transcending every age and culture www.newtestamentpattern.net More Bible studies can be read at www.newtestamentpattern.net NOTE Throughout this study.  Church (capital ‘C’) denotes the One ‘Universal’ Body of Christ.  church (small ‘c’) denotes a local church/assembly. 1 Corinthians 11: 1-16. “Be ye followers of me, even as I also am of Christ. Now I praise you, brethren, that ye remember me in all things, and keep the ordinances, as I delivered...»

«2203 EAST BROAD STREET Home of Randolph & Karla Bell This Greek Revival house was begun in 1855 but completed after the Civil War in 1873 along the originally intended architectural lines and was, therefore, “out of date” for its Victorian completion date. Higher up the block are the Yarborough (2215 East broad) and Turpin (2209 East broad) houses. Messrs. Yarborough and Turpin jointly owned a tobacco factory. 2203 reportedly was begun for the Turpin’s daughter. The high ceilings and...»

«L’analyse de conflit et évaluation de besoin effectuée dans le cadre de l’opérationnalisation de la deuxième phase du STAREC/ISSSS dans les territoires de Mambasa et Bafwasende Joost van Puijenbroek, Octobre 2014 Adresse: Adresse postale: Godebaldkwartier 74 P.O. Box 19318 NL3511 DZ Utrecht NL – 3501 DH Utrecht, Pays-Bas info@paxforpeace.nl www.paxforpeace.com Ce rapport est compilé par PAX, l’organisation conjointe de Pax Christi Pays Bas et du Conseil de Paix des Eglises...»

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