FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 | 2 || 4 | 5 |   ...   | 11 |

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

-- [ Page 3 ] --

On the complexity side, fixed-parameter tractability of CSP(H) seems to be a more robust question than polynomial-time solvability. For example, any polynomial-time reduction to CSP(H) should be able to pick a member of H, thus it seems that polynomial-time reduction to CSP(H) is only possible if certain artificial technical conditions are imposed on H (such as there is an algorithm efficiently generating appropriate members of H). Furthermore, there are classes H for which CSP(H) is polynomial-time equivalent to Log Clique [Grohe 2007], thus we cannot hope to classify CSP(H) into polynomial-time solvable and NP-hard cases.

Another difficulty in understanding polynomial-time solvability is that it can depend on the “irrelevant” parts of the hypergraph. Suppose for example that there is class H for which CSP(H) is not polynomial-time solvable, but it is fixed-parameter tractable: it can be solved in time f (H) · ( I )O(1). Let H be constructed the following way: for every H ∈ H, class H contains a hypergraph H that is obtained from H by adding a new component that is a path of length f (H). This new path is trivial with respect to the CSP problem, thus any algorithm for CSP(H) can be used for CSP(H ) as well. Consider an instance I of CSP(H ) having hypergraph H, which was obtained from hypergraph H. After taking care of the path, the assumed algorithm for CSP(H) can solve this instance in time f (H) · ( I )O(1), which is polynomial in I : instance I contains a representation of H, which has at least f (H) vertices, thus I is at least f (H). Therefore, CSP(H ) is polynomial-time solvable.

This example shows that aiming for polynomial-time solvability instead of fixed-parameter tractability might require understanding such subtle, but mostly irrelevant phenomena.

In the hardness results obtained so far, evidence for the non-existence of polynomial-time algorithms is given not in the form of NP-hardness, but by giving evidence that the problem is not even fixed-parameter tractable. In Theorem 1.1, it is a remarkable coincidence that polynomial-time solvability and fixed-parameter tractability are equivalent. However, there is no reason to expect this to remain true in more general cases. Therefore, as discussed above, it makes sense to focus first on understanding the fixed-parameter tractability of the problem.

Organization. For convenience, Section 2 collects many of the definitions appearing in the paper. The reader might want to skim through this at first and refer to appropriate parts of it later. Submodular width and other width measures are defined in Section 3.

Section 4 contains the algorithmic part of the paper: the algorithm for classes with bounded submodular width. Section 5 characterizes large submodular width with highly connected sets, while Section 6 uses highly connected sets to find good embeddings in hypergraph.

The main hardness result of the paper is proved in Section 7.

2. PRELIMINARIES Constraint satisfaction problems. We briefly recall the most important notions related to CSP. For more background, see e.g., [Grohe 2006; Feder and Vardi 1999].

Definition 2.1. An instance of a constraint satisfaction problem is a triple (V, D, C),


— V is a set of variables, — D is a domain of values, — C is a set of constraints, {c1, c2,..., cq }. Each constraint ci ∈ C is a pair si, Ri,


— si is a tuple of variables of length mi, called the constraint scope, and — Ri is an mi -ary relation over D, called the constraint relation.

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

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

For each constraint si, Ri the tuples of Ri indicate the allowed combinations of simultaneous values for the variables in si. The length mi of the tuple si is called the arity of the constraint. A solution to a constraint satisfaction problem instance is a function f from the set of variables V to the domain of values D such that for each constraint si, Ri with si = vi1, vi2,..., vim, the tuple f (vi1 ), f (vi2 ),..., f (vim ) is a member of Ri. We say that an instance is binary if each constraint relation is binary, i.e., mi = 2 for each constraint. 4 It can be assumed that the instance does not contain two constraints si, Ri, sj, Rj with si = sj, since in this case the two constraints can be replaced by the constraint si, Ri ∩ Rj.

In the input, the relation appearing in a constraint is represented by listing all the tuples of the constraint. We denote by I the size of the representation of the instance I = (V, D, C).

It can be assumed that |D| ≤ I : elements of D that do not appear in any relation can be safely removed.

Let I = (V, D, C) be a CSP instance and let V ⊆ V be a nonempty subset of variables. If f is a solution of I, then prV f is the projection of f to V, which is simply the restriction of the function f : V → D to V ⊆ V. If R is a set of solutions for I, then we let prV R = {prV f | f ∈ R}.

The projection prV I of I to V is a CSP I = (V, D, C ), where C is defined the following way: For each constraint c = (v1,..., vk ), R having at least one variable in V, there is a corresponding constraint c in C. Suppose that vi1,..., vi are the variables among v1,..., vk that are in V. Then the constraint c is defined as (vi1,..., vi ), R, where the relation R is the projection of R to the coordinates i1,..., i, that is, R contains an tuple (d1,..., d ) ∈ D if and only if there is a k-tuple (d1,..., dk ) ∈ R such that dj = dij for 1 ≤ j ≤. Clearly, if f is a solution of I, then prV f is a solution of prV I (but the converse is not true). For a subset V ⊆ V, we denote by solI (V ) the set of all solutions of prV I (which can contain a solution which is not the projection of any solution of I). If the instance I is clear from the context, we drop the subscript.

The primal graph (or Gaifman graph) of a CSP instance I = (V, D, C) is a graph with vertex set V such that u, v ∈ V are adjacent if and only if there is a constraint whose scope contains both u and v. The hypergraph of a CSP instance I = (V, D, C) is a hypergraph H with vertex set V, where e ⊆ V is an edge of H if and only if there is a constraint whose scope is e (more precisely, where the scope is an |e|-tuple s, whose coordinates form a permutation of the elements of e). For a class H of graphs, we denote by CSP(H) the problem restricted to instances whose hypergraph is in H.

Graphs and hypergraphs. If G is a graph or hypergraph, then we denote by V (G) and E(G) the set of vertices and the set of edges of G, respectively. Vertices u, v ∈ V (G) are adjacent if there is an edge e ∈ E(G) with u, v ∈ e. A set K ⊆ V (G) is a clique if the vertices in K are pairwise adjacent. If H is a hypergraph and V ⊆ V (H), then the subhypergraph induced by V is a hypergraph H with vertex set S and ∅ ⊂ e ⊆ V is an edge of H if and only if there is an edge e ∈ E(H) with e ∩ V = e. We denote by H \ S the subhypergraph of H induced by V (H) \ S.

Paths, separators, and flows in hypergraphs. A path P in hypergraph H is an ordered sequence v0, v1,..., vr of distinct vertices such that vi and vi−1 are adjacent for every 1 ≤ i r. We distinguish the endpoints of a path: vertex v0 is the first endpoint of P and vr is the second endpoint of P. For a path of length zero, the first and second endpoints coincide. A path is an X − Y path if its first endpoint is in X and its second endpoint is in Y. A path P = v1 v2... vt is minimal if there are no shortcuts, i.e., vi and vj are not adjacent if |i − j| 1. Note that a minimal path intersects each edge at most twice.

Let H be a hypergraph and X, Y ⊆ V (H) be two (not necessarily disjoint) sets of vertices.

An (X, Y )-separator is a set S ⊆ V (H) of vertices such that there is no (X \ S) − (Y \ S) 4 Itis unfortunate that while some communities use the term “binary CSP” in the sense that each constraint is binary (as does this paper), others use it in the sense that the variables are 0-1, i.e, the domain size is 2.

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

A:10 D. Marx path in H \ S, or in other words, every X − Y path of H contains at least one vertex of S.

In particular, this means that X ∩ Y ⊆ S.

An assignment s : E(H) → R+ is a fractional (X, Y )-separator if every X − Y path P is covered by s, that is, e∈E(H),e∩P =∅ s(e) ≥ 1. The weight of the fractional separator s is e∈E(H) s(e).

Let H be a hypergraph and let P be the set of all paths in H. A flow of H is an assignment f : P → R+ such that P ∈P,P ∩e=∅ f (P ) ≤ 1 for every e ∈ E(H). The value of the flow f is P ∈P f (P ). We say that a path P appears in flow f, or simply P is a path of f if f (P ) 0. For some X, Y ⊆ V (H), an (X, Y )-flow is a flow f such that only X − Y paths appear in f. A standard LP duality argument shows that the minimum weight of a fractional (X, Y )-separator is equal to the maximum value of an (X, Y )-flow.

If f, f are flows such that f (P ) ≤ f (P ) for every path P, then f is a subflow of f. The r sum of the flows f1,..., fr is a mapping that assigns weight i=1 fi (P ) to each path P.

Note that the sum of flows is not necessarily a flow itself as the total weight of the paths intersecting a certain edge can be more than 1 in the sum. If the sum of f1,..., fr happens to be a flow, then we say that f1,..., fr are compatible.

Highly connected sets. An important step in understanding various width measures is showing that if the measure is large, then the (hyper)graph contains a highly connected set (in a certain sense). We define here the notion of highly connectedness that will be used in the paper. First, recall that a fractional independent set of a hypergraph H is a mapping µ : V (H) → [0, 1] such that v∈e µ(v) ≤ 1 for every e ∈ E(H). We extend functions on the vertices of H to subsets of vertices of H the natural way by setting µ(X) := v∈X µ(v), thus we can equivalently say that µ : V (H) → [0, 1] is a fractional independent set if and only if µ(e) ≤ 1 for every e ∈ E(H).

Let µ be a fractional independent set of hypergraph H and let λ 0 be a constant. We say that a set W ⊆ V (H) is (µ, λ)-connected if for any two disjoint sets A, B ⊆ W, the minimum weight of a fractional (A, B)-separator is at least λ · min{µ(A), µ(B)}. Note that if W is (µ, λ)-connected, then W is (µ, λ )-connected for every λ λ and every W ⊆ W is also (µ, λ)-connected. Informally, if W is (µ, λ)-lambda connected for some fractional independent set µ such that µ(W ) is “large”, then we call W a highly connected set. For λ 0, we denote by conλ (H) the maximum of µ(W ), taken over every fractional independent set µ and (µ, λ)-connected set W of H. Note that if λ ≤ λ, then conλ (H) ≥ conλ (H).

Throughout the paper, λ can be thought of as a sufficiently small universal constant, say, 0.001.

Embeddings. The hardness result presented in the paper and earlier hardness results for CSP(H) [Grohe 2007; Marx 2011; 2010b] are based on embedding some other problem (with a certain graph structure) in a CSP instance whose hypergraph is a member of H. Thus we need appropriate notions of embedding a graph in a (hyper)graph. Let us first recall the definition of minors in graphs. A graph F is a minor of G if F can be obtained from G by a sequence of vertex deletions, edge deletions, and edge contractions. The following alternative definition is more relevant from the viewpoint of embeddings: a graph F is a minor of G if there is a mapping ψ that maps each vertex of F to a connected subset of V (G) such that ψ(u) ∩ ψ(v) = ∅ for u = v, and if u, v ∈ V (F ) are adjacent in F, then there is an edge in E(G) connecting ψ(u) and ψ(v).

A crucial difference between the proof of Theorem 1.1 in [Grohe 2007] and the proof of Theorem 1.2 in [Marx 2010b] is that the former result is a based on finding a minor embedding of a grid, while the latter result uses a more general notion of embedding where the images of distinct vertices are not necessarily disjoint, but can overlap in a controlled way. We define such embeddings the following way. We say that two sets of vertices X, Y ⊆ V (H) touch if either X ∩ Y = ∅, or there is an edge e ∈ E(H) intersecting both X and Y.

An embedding of graph G into hypergraph H is a mapping ψ that maps each vertex of G Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:11 to a connected subset of V (H) such that if u and v are adjacent in G, then ψ(u) and ψ(v) touch. The depth of a vertex v ∈ V (H) in embedding ψ is dψ (v) := |{u ∈ V (G) | v ∈ ψ(u)}|, the number of vertices of G whose images contain v. The vertex depth of the embedding is maxv∈V (H) dψ (v). Observe that ψ is a minor mapping if and only if it has vertex depth

Pages:     | 1 | 2 || 4 | 5 |   ...   | 11 |

Similar works:

«Toeing the Line Experiments with Line-following Algorithms Jonathan A. Gray Grade 9 Contents Abstract Introduction Purpose Hypothesis Materials Setup Programming the robot: Building the robot: Setting up the test area: Procedure Results Conclusions Pictures Works Cited -1Toeing the Line: Experiments with Line-following Algorithms Jonathan A. Gray Toeing the Line Experiments with Line-following Algorithms Jonathan A. Gray Abstract Following lines is an essential part of robot navigation in a...»

«Prosodic phrasing : production, perception, acceptability and comprehension Sanderman, A.A.DOI: 10.6100/IR461536 Published: 01/01/1996 Document Version Publisher’s PDF, also known as Version of Record (includes final page, issue and volume numbers) Please check the document version of this publication: • A submitted manuscript is the author’s version of the article upon submission and before peer-review. There can be important differences between the submitted version and the official...»



«An Examination of the Impact of Paratextual Variables on Response and ROI In Direct Mail Fund-Raising Campaigns: If Your Envelope Doesn’t Get Opened, Then It If Your Envelope Doesn’t Get Opened, Then It Really Doesn’t Mater What You Put Inside! Matter What You Put Inside! Frank C. Dickerson Frank C. Dickerson Ph.D. Ph.D. Running Head: The Impact of Paratextual Variables on Response and ROI The Impact of Paratextual Variables on Response and ROI Executive Summary In speech, two classes of...»

«SULLY COUNTY BOARD OF COMMISSIONERS MARCH 4, 2014 The Board of Sully County Commissioners held their regular scheduled mtg on Tues, March 4, 2014. Chmn Bill Floyd called the mtg to order. Other members present: Jerry Richards, Judy Pullman, Joe Fanger & Beverly Zebroski. MINUTES: Moved by Zebroski, seconded by Richards to approve the minutes of Feb 4, 2014. Unanimous vote aye. REVIEW OF CLAIMS: Bd reviewed claims submitted for the month of March. HIGHWAY: Highway Supt Wolforth met with the Bd....»

«Singularity-theoretic methods in robot kinematics P. S. Donelan School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO Box 600, Wellington, New Zealand E-mail: peter.donelan@vuw.ac.nz Abstract The significance of singularities in the design and control of robot manipulators is well known and there is an extensive literature on the determination and analysis of singularities for a wide variety of serial and parallel manipulators—indeed such an analysis...»

«BYLAWS OF DEKALB CHAMBER OF COMMERCE, INC. ARTICLE I DEFINITIONS AND ABBREVIATIONS As used in these Bylaws, when capitalized: (a) DeKalb Chamber means the DeKalb Chamber of Commerce, Inc., a Georgia nonprofit corporation. (b) Act means the Georgia Nonprofit Corporation Code, as amended from time to time. (c) DELETED (d) State means the State of Georgia. (e) Bylaws means the Bylaws of the DeKalb Chamber, as amended from time to time. (f) Board Annual Meeting means the annual meeting of the Board...»

«The 82nd Airborne Division in Transformation: Is it Possible to Significantly Increase the Combat Power in the Division Ready Brigade and Reduce Deployment Sorties Using Current, Fielded Technology? A MONOGRAPH BY Douglas J. DeLancey Major, Infantry School of Advanced Military Studies United States Army Command and General Staff College Fort Leavenworth, Kansas First Term AY 00-01 Approved for Public Release Distribution is Unlimited Acknowledgments This monograph would not have been possible...»

«Bangladesh Greater Dhaka Telecommunications Network Improvement Project (II) External Evaluators: Juichi Inada, Mamoru Kobayashi, Takeko Iinuma (Senshu University) Field Survey: February and April 2007 1. Project Profile and Japan’s ODA Loan Bhutan Nepal Project site Bangladesh India Dhaka Myanmar Map of project area Switchboard installed under the project 1.1 Background The telephone density in Bangladesh was 0.18 per 100 people as of 1987, one of the lowest even among the least developed...»

«The Dhokra Artisans of Bankura and Dariapur, West Bengal: A Case Study and Knowledge Archive of Technological Change in Progress David Smith, Newport, UK Rajesh Kochhar, New Delhi, India The project report describes the process of village renewal in the Bengal region of India. It deals with the replacing of an ancient traditional but inefficient metal-foundry technique in the village with another which is almost as ancient but more efficient. The impact of this apparently simple change on this...»

«Housing and Public Protection Department Wrexham County Borough Council Ruthin Road Wrexham LL13 7TU Part B Variation form Application for a variation of permit conditions (Petrol station) Local Authority Pollution Prevention and Control Pollution Prevention and Control Act, 1999 Environmental Permitting (England and Wales) Regulations 2010 Introduction When to use this form This environmental permitting regime is known as and referred to as Local Authority Pollution Prevention and Control...»

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