FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 9 | 10 ||

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

-- [ Page 11 ] --

A different version of CSP was investigated in [Marx 2011], where each variable has a different domain, and each constraint relation is represented by a full truth table (see the exact definition in [Marx 2011]). Let us denote by CSPtt (H) this variant of the problem. It is easy to see that CSPtt (H) can be reduced to CSP(H) in polynomial time, but a reduction in the other direction can possibly increase the representation of a constraint by an exponential factor. Nevertheless, the hardness results of this section apply to the “easier” problem CSPtt (H) as well. What we have to verify is that the proof of Lemma 7.5 works even if I2 is an instance of CSPtt, i.e., the constraint relations have to be represented by truth tables. Inspection of the proof shows that it indeed works: the product in Inequality (4) is exactly the size of the truth table describing the constraint corresponding to edge e, thus the |D1 |q upper bound remains valid even if constraints are represented by truth tables. Therefore, the hardness results of [Marx 2011] are subsumed by the following


Corollary 7.8. If H is a recursively enumerable class of hypergraphs with unbounded submodular width, then CSPtt (H) is not fixed-parameter tractable, unless the Exponential Time Hypothesis fails.

8. CONCLUSIONS The main result of the paper is introducing submodular width and proving that bounded submodular width is the property that determines the fixed-parameter tractability of CSP(H). The hardness result is proved assuming the Exponential Time Hypothesis. This conjecture was formulated relatively recently [Impagliazzo et al. 2001], but it turned out to be very useful in proving lower bounds in a variety of settings [Marx 2010b; Andoni et al.

2006; Marx 2007; Pˇtra¸cu and Williams 2010].

as For the hardness proof, we had to understand what large submodular width means and we had to explore the connection between submodular width and other combinatorial properties. We have obtained several equivalent characterizations of bounded submodular width, in particular, we have showed that bounded submodular width is equivalent to bounded

adaptive width:

Corollary 8.1. The following are equivalent for every class H of hypergraphs:

(1 ) There is a constant c1 such that µ-width(H) ≤ c1 for every H ∈ H and fractional independent set µ.

(2 ) There is a constant c2 such that b-width(H) ≤ c2 for every H ∈ H and edgedominated monotone submodular function b on V (H) with b(∅) = 0.

(3 ) There is a constant c3 such that b∗ -width(H) ≤ c3 for every H ∈ H and edgedominated monotone submodular function b on V (H) with b(∅) = 0.

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:45 (4 ) There is a constant c4 such that conλ (H) ≤ c4 for every H ∈ H, where λ 0 is a universal constant.

(5 ) There is a constant c5 such that emb(H) ≤ c5 for every H ∈ H.

Implications (2)⇒(1) and (3)⇒(2) are trivial; (4)⇒(3) follows from Lemma 5.10; (5)⇒(4) follows from Corollary 6.2; (1)⇒(5) follows from Lemma 6.9.

Let us briefly review the main ideas that were necessary for proving the main result of

the paper:

— Recognizing that submodular width is the right property characterizing the complexity of the problem.

— A CSP instance can be partitioned into a bounded number of uniform instances (Section 4.2).

— The number of solutions in a uniform CSP instance can be described by a submodular function (Section 4.3).

— There is a connection between fractional separation and finding a separator minimizing an edge-dominated submodular cost function (Section 5.2).

— The transformation that turns b into b∗, and the properties of b∗ that are more suitable than b for recursively constructing a tree decomposition (Section 5.1).

— Our results on fractional separation and the standard framework of finding tree decompositions show that large submodular width implies that there is a highly connected set (Section 5.3).

— A highly connected set can be turned into a highly connected set that is partitioned into cliques in an appropriate way (Section 6.1).

— A highly connected set with appropriate cliques implies that there is a uniform concurrent flow of large value between the cliques (Section 6.2).

— Similarly to [Marx 2010b], we use the observation that a concurrent flow is analogous to a line graph of a clique, hence it has good embedding properties (Section 6.2).

— Similarly to [Marx 2010b], an embedding in a hypergraph gives a way of simulating 3SAT with CSP(H) (Section 7).

It is possible that the main result can be proved in a simpler way by bypassing some of the ideas above. In particular, a surprising consequence of our results is that bounded submodular width and bounded adaptive width are the same, i.e., if a class H has unbounded submodular width, then for every k there is a Hk ∈ H and a fractional independent set µk such that µk -width(Hk ) ≥ k, or in other words, large submodular width can be certified by the modular function µk. To prove this, we need all the results of Sections 5 and 6. Having a better understanding and an independent proof of this fact could simplify the proofs considerably. Another possible target for simplification is Section 6.1, where a lot of effort is spent on proving that if there is a large highly connected set, then there is a large highly connected set that is partitioned into cliques in an appropriate way. It might be possible to strengthen the results of Section 5 (perhaps by better understanding the role of cliques in separators) so that they give such a highly connected set directly.

An obvious question for further research is whether it is possible to prove a similar dichotomy result with respect to polynomial-time solvability. At this point, it is hard to see what the answer could be if we investigate the same question using the more restricted notion of polynomial time solvability. We know that bounded fractional hypertree width implies polynomial-time solvability [Marx 2010a] and Theorem 7.1 shows that unbounded submodular width implies that the problem is not polynomial-time solvable (as it is not even fixed-parameter tractable). So only those classes of hypergraphs are in the “gray zone” that have bounded submodular width but unbounded fractional hypertree width.

What could be the truth in this gray zone? A first possibility is that CSP(H) is polynomial-time solvable for every such class, i.e., Theorem 4.1 can be improved from Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:46 D. Marx fixed-parameter tractability to polynomial-time solvability. However, Theorem 4.1 uses the power of fixed-parameter tractability in an essential way (splitting into a double-exponential number of uniform instances), so it is not clear how such improvement is possible. A second possibility is that unbounded fractional hypertree width implies that CSP(H) is not polynomial-time solvable. Substantially new techniques would be required for such a hardness proof. The hardness proofs of this paper and of [Grohe 2007; Marx 2010b] are based on showing that a large problem space can be efficiently embedded into an instance with a particular hypergraph. However, the fixed-parameter tractability results show that no such embedding is possible in case of classes with bounded submodular width. Therefore, a possible hardness proof should embed a problem space that is comparable (in some sense) with the size of the hypergraph and should create instances where the domain size is bounded by a function of the size of the hypergraph. A third possibility is that the boundary of polynomial-time solvability is somewhere between bounded fractional hypertree width and bounded submodular width. Currently, there is no natural candidate for a property that could correspond to this boundary and, again, the hardness part of the characterization should be substantially different than what was done before. Finally, there is a fourth possibility: the boundary of the polynomial-time cases cannot be elegantly characterized by a simple combinatorial property. In general, if we consider the restriction of a problem to all possible classes of (hyper)graphs, then there is no a priori reason why an elegant characterization should exist that describes the easy and hard classes. For example, it is highly unlikely that there is an elegant characterization of those classes of graphs where solving the Maximum Independent Set problem is polynomial-time solvable. As discussed earlier, the fixed-parameter tractability of CSP(H) is a more robust question than its polynomialtime solvability, hence it is very well possible that only the former question has an elegant answer.

REFERENCES Isolde Adler. 2006. Width functions for hypertree decompositions. Ph.D. Dissertation. Albert-LudwigsUniversit¨t Freiburg.

a Isolde Adler, Georg Gottlob, and Martin Grohe. 2007. Hypertree width and related hypergraph invariants.

European J. Combin. 28, 8 (2007), 2167–2181.

Amit Agarwal, Noga Alon, and Moses Charikar. 2007. Improved approximation for directed cut problems.

In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing. ACM, New York, 671–680.

Noga Alon, Ilan Newman, Alexander Shen, G´bor Tardos, and Nikolai Vereshchagin. 2007. Partitioning a multi-dimensional sets in a small number of “uniform” parts. European J. Combin. 28, 1 (2007), 134– 144.

Omid Amini, Fr´d´ric ee Mazoit, Nicolas Nisse, and St´phan e Thomass´.

e 2009. Submodular partition functions. Discrete Mathematics 309, 20 (2009), 6000 – 6008.

DOI:http://dx.doi.org/DOI:10.1016/j.disc.2009.04.033 Alexandr Andoni, Piotr Indyk, and Mihai Patrascu. 2006. On the Optimality of the Dimensionality Reduction Method. In FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE Computer Society, Washington, DC, USA, 449–458.

DOI:http://dx.doi.org/10.1109/FOCS.2006.56 Albert Atserias, Andrei A. Bulatov, and V´ ıctor Dalmau. 2007. On the Power of k-Consistency. In ICALP.


Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, and Mihalis Yannakakis. 1981. Properties of Acyclic Database Schemes. In STOC. 355–362.

Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. 1983. On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30, 3 (1983), 479–513.

Andrei A. Bulatov. 2003. Tractable conservative Constraint Satisfaction Problems. In 18th Annual IEEE Symposium on Logic in Computer Science (LICS’03). IEEE Computer Society, Los Alamitos, CA, USA, 321.

Andrei A. Bulatov. 2006. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J.

ACM 53, 1 (2006), 66–120.

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:47 A. A. Bulatov, A. A. Krokhin, and P. Jeavons. 2001. The complexity of maximal constraint languages. In Proceedings of the 33rd ACM Symposium on Theory of Computing. 667–674.

Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In STOC. 77–90.

Chandra Chekuri and Anand Rajaraman. 2000. Conjunctive query containment revisited. Theoret. Comput.

Sci. 239, 2 (2000), 211–229.

Hubie Chen and Martin Grohe. 2010. Constraint satisfaction with succinctly specified relations. J. Comput.

Syst. Sci. 76, 8 (2010), 847–860.

F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. 1986. Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A 43, 1 (1986), 23–37.

V´ıctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. In CP ’02: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming. Springer-Verlag, London, UK, 310–326.

R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer, New York. xvi+533 pages.

Ronald Fagin. 1983. Degrees of acyclicity for hypergraphs and relational database schemes. J. Assoc. Comput. Mach. 30, 3 (1983), 514–550.

Tom´s Feder and Moshe Y. Vardi. 1999. The computational structure of monotone monadic SNP and a constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 1 (1999), 57–104.

J¨rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin.

o E. C. Freuder. 1990. Complexity of K-Tree Structured Constraint Satisfaction Problems. In Proc. of AAAIBoston, MA, 4–9.

G. Gottlob, N. Leone, and F. Scarcello. 2002a. Hypertree Decompositions and Tractable Queries. J. Comput.

System Sci. 64 (2002), 579–627.

Georg Gottlob, Francesco Scarcello, and Martha Sideri. 2002b. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence 138, 1-2 (2002), 55–86.

G. Gottlob and S. Szeider. 2008. Fixed-Parameter Algorithms For Artificial Intelligence, Constraint Satisfaction and Database Problems. Comput. J. 51, 3 (2008), 303–325.

Gianluigi Greco and Francesco Scarcello. 2010. The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACTSIGART symposium on Principles of database systems (PODS ’10). ACM, New York, NY, USA, 327–338. DOI:http://dx.doi.org/10.1145/1807085.1807127 Martin Grohe. 2006. The Structure of Tractable Constraint Satisfaction Problems.. In MFCS 2006. 58–72.

Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1 (2007), 1. DOI:http://dx.doi.org/10.1145/1206035.1206036 Martin Grohe and D´niel Marx. 2009. On tree width, bramble size, and expansion. Journal of Combinatorial a Theory Ser. B 99, 1 (2009), 218–228.

Martin Grohe and D´niel Marx. 2012+. Constraint solving via fractional edge covers. (2012+). To appear a in ACM Transactions on Algorithm.

Anupam Gupta. 2003. Improved results for directed multicut. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003). ACM, New York, 454–455.

√ Mohammad Taghi Hajiaghayi and Harald R¨cke. 2006. An O( n)-approximation algorithm for directed a sparsest cut. Inform. Process. Lett. 97, 4 (2006), 156–160.

Petr Hlinˇn´. 2005. A parametrized algorithm for matroid branch-width. SIAM J. Comput. 35, 2 (2005), ey 259–277.

Petr Hlinˇn´ and Sang-il Oum. 2008. Finding branch-decompositions and rank-decompositions. SIAM J.

ey Comput. 38, 3 (2008), 1012–1032.

Petr Hlinˇn´ and Geoff Whittle. 2006. Matroid tree-width. European J. Combin. 27, 7 (2006), 1117–1128.

ey Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. System Sci. 63, 4 (2001), 512–530.

Satoru Iwata. 2008. Submodular function minimization. Math. Program. 112, 1, Ser. B (2008), 45–64.

Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. 2001. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 4 (2001), 761–777 (electronic).

P. Jeavons, D. A. Cohen, and M. Gyssens. 1997. Closure properties of constraints. J. ACM 44, 4 (1997), 527–548.

Phokion G. Kolaitis and Moshe Y. Vardi. 2000a. Conjunctive-query containment and constraint satisfaction.

J. Comput. Syst. Sci. 61, 2 (2000), 302–332. DOI:http://dx.doi.org/10.1006/jcss.2000.1713 Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:48 D. Marx Phokion G. Kolaitis and Moshe Y. Vardi. 2000b. A Game-Theoretic Approach to Constraint Satisfaction.

In AAAI/IAAI. 175–181.

D´niel Marx. 2007. On the optimality of planar and geometric approximation schemes. In 48th Annual a IEEE Symposium on Foundations of Computer Science (FOCS’07). 338–348.

D´niel Marx. 2010a. Approximating fractional hypertree width. ACM Trans. Algorithms 6, 2 (2010), 1–17.

a DOI:http://dx.doi.org/10.1145/1721837.1721845 D´niel Marx. 2010b. Can You Beat Treewidth? Theory of Computing 6, 1 (2010), 85–112.

a DOI:http://dx.doi.org/10.4086/toc.2010.v006a005 D´niel Marx. 2010c. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In a Proceedings of the 42nd ACM Symposium on Theory of Computing. 735–744.

D´niel Marx. 2011. Tractable Structures for Constraint Satisfaction with Truth Tables. Theory of Computing a Systems 48 (2011), 444–464.

Rolf Niedermeier. 2006. Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford. xii+300 pages.

Sang-il Oum. 2005. Approximating Rank-width and Clique-width Quickly. In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science. 49–58.

Sang-il Oum and Paul Seymour. 2007. Testing branch-width. J. Combin. Theory Ser. B 97, 3 (2007), 385–393.

Sang-il Oum and Paul Seymour. 2006. Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96, 4 (2006), 514–528.

Mihai Pˇtra¸cu and Ryan Williams. 2010. On the Possibility of Faster SAT Algorithms. In Proc. 21st as ACM/SIAM Symposium on Discrete Algorithms (SODA). 1065–1075.

Francesco Scarcello, Georg Gottlob, and Gianluigi Greco. 2008. Uniform Constraint Satisfaction Problems and Database Theory. In Complexity of Constraints. 156–195.

Thomas J. Schaefer. 1978. The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978). ACM, New York, 216– 226.

Alexander Schrijver. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 2 (2000), 346–355.

Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. 82–94.

Pages:     | 1 |   ...   | 9 | 10 ||

Similar works:

«THE GRAND CHESSBOARD: THE BIRTH OF A NEW WORLD BY SIMON HUNT, SIMON HUNT STRATEGIC SERVICES Slide 1: “The Grand Chessboard: The Birth Of A New World” Moscow: June 2015 By Simon Hunt Simon Hunt Strategic Services Simon H unt Strategic Services I feel humbled and honoured to be invited to address you today and to pose the question “Where is the World Heading?” Will it be in peaceful accord with itself or are we entering an era of mounting tension? Whilst the question is not easy to...»

«Telecom Decision CRTC 2014-627 PDF version Ottawa, 5 December 2014 File number: 8695-C12-201402685 Final 2014 revenue-percent charge and related matters The Commission approves on a final basis, effective 1 January 2014, a 2014 contribution collection revenue-percent charge of 0.55% and the 2014 subsidy per residential network access service (NAS) amounts for the incumbent local exchange carriers (ILECs). In addition, the Commission approves on an interim basis, effective 1 January 2015, a 2015...»

«WERVING LEDEN ERVING LEDENW INhouD Ledenwerving (p.5) 1. Vooronderzoek (p.6) 2. Actie ondernemen (p.13) 3. Ideeën voor ledenwervingsactiviteiten (p.26) 4. Evalueren (p.29) COLOFON Redactie: Ruth Busschaert Lay-out: Pepijn Haghebaert Foto’s: KSA Mater, KSA Rooyghem, KSA Zele, KSA Zutendaal, Dag van de Jeugdbeweging Illustraties jaarthema: Stef Vandommele Dit is een uitgave van KSA Nationaal Vooruitgangsstraat 225 1030 Brussel juli 2015 LEDENWERVING Elke groep doet aan ledenwerving, maar...»

«Approximating Polyhedra with Spheres for Time-Critical Collision Detection PHILIP M. HUBBARD Cornell University. This article presentsa method for approximatingpolyhedralobjects to support a time-critical collision-detectionalgorithm. The approximationsare hierarchies of spheres, and they allow the time-critical algorithm to progressively refine the accuracy of its detection, stopping as needed to maintain the real-time performanceessential for interactive applications. The key to this...»

«A NOTION OF MORAL RESPONSIBILITY IMMUNE TO THE THREAT FROM CAUSAL DETERMINATION Derk Pereboom, Cornell University Forthcoming in The Nature of Moral Responsibility, Randolph Clarke, Michael McKenna and Angela Smith, eds., Oxford University Press, 2015. Penultimate draft Abstract: This article sets out a notion of moral responsibility that incorporates the central features of the answerability conception advocated by T. M Scanlon, Hilary Bok, and Angela Smith, and of Michael McKenna’s more...»

«295 THE TERMINATION OF OPTIC FIBRES IN THE LATERAL GENICULATE BODY OF THE MONKEY By P. GLEES AND W. E. LE GROS CLARK Department of Anatomy, University of Oxford THE classical observations made by Henschen (1897, 1898) and Winkler (1912, 1913) on the localization of optic fibres in the lateral geniculate body of the human brain were amplified by Ronne (1913, 1914). This author published a series of clinical cases of alcoholic and diabetic amblyopia which provided definite evidence that the...»

«wolf of zhongshan tian yuan tan The Wolf of Zhongshan and Ingrates: Problematic Literary Contexts in Sixteenth-Century China N o later than the first half of the sixteenth century, the story about an ungrateful wolf captured the interests and attention of Chinese writers and readers. It offers the following scenario: a wolf, on the run from pursuing hunters in the Zhongshan area of the kingdom of Zhao, asks a traveling scholar named Master Dongguo to be hid in the scholar’s book bag. After...»

«Hong Kong Exchanges and Clearing Limited and The Stock Exchange of Hong Kong Limited take no responsibility for the contents of this announcement, make no representation as to its accuracy or completeness and expressly disclaim any liability whatsoever for any loss howsoever arising from or in reliance upon the whole or any part of the contents of this announcement. FREEMAN FINANCIAL CORPORATION LIMITED (incorporated in the Cayman Islands with limited liability) (Stock Code: 279) (1)...»

«Street Drugs in 2015 By: Jason Martin, RN CEN NREMT-P Injury Prevention/Outreach Coordinator CoxHealth Trauma Center Springfield, MO Where are we heading? Safety of our coworkers and general public Drugs have changed These patients are not getting good care Toxicology: What’s in our patients › Alcohol › Marijuana › Pills: Vicodin, Percocet, Morphine, Xanax, etc. › Meth, Heroin, Cocaine › Designer Drugs › Synthetics & Bath Salts › Regional What is the problem? › 1350 EMS called...»

«Curriculum Connections An American Story: The Multiphone • Background information for the educator Learning by Doing: Design a Music Machine • Classroom activities based on the object Interdisciplinary Content Standards WR 3 use critical thinking and problem-solving skills WR 4 demonstrate self-management skills VPA 1.2 refine skills through creating art VPA 1.3 utilize arts elements to produce artistic products LA 3.1 speak in a variety of contexts LA 3.2 active listening, interpreting,...»

«Modalités de prise en charge d’un appel de demande de soins non programmés dans le cadre de la régulation médicale Mars 2011 Définitions Processus médical de prise en charge Centre de régulation médicale Suivi de la prise en charge Coordinations entre intervenants lors de Modalités de réception d’un appel la régulation médicale Appels en langue étrangère et d’un Modalités d’analyse d’un appel patient sourd ou malentendant Différents types de réponses Traçabilité de...»


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