skip to main content
10.5555/1496770.1496868guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

Approximating fractional hypertree width

Published: 04 January 2009 Publication History

Abstract

Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work [14], constraint satisfaction problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this paper, we show that for every w ≥ 1, there is a polynomial-time algorithm that, given a hypergraph H with fractional hypertree width at most w, computes a fractional hypertree decomposition of width O(w3) for H. This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if H is a class of hypergraphs with bounded fractional hypertree width, then CSP restricted to instances whose structure is in H is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP, Boolean Conjuctive Queries, and Conjunctive Query Containment polynomial-time solvable.

References

[1]
I. Adler, G. Gottlob, and M. Grohe. Hypertree width and related hypergraph invariants. European J. Combin., 28(8):2167--2181, 2007.
[2]
H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305--1317, 1996.
[3]
H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms, 18(2):238--255, 1995.
[4]
F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A, 43(1):23--37, 1986.
[5]
T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput., 28(1):57--104, 1999.
[6]
J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, 2006.
[7]
E. C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In Proc. of AAAI-90, pages 4--9, Boston, MA, 1990.
[8]
G. Gottlob, M. Grohe, N. Musliu, M. Samer, and F. Scarcello. Hypertree decompositions: structure, algorithms, and applications. In Graph-theoretic concepts in computer science, volume 3787 of Lecture Notes in Comput. Sci., pages 1--15. Springer, Berlin, 2005.
[9]
G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64:579--627, 2002.
[10]
G. Gottlob, Z. Miklós, and T. Schwentick. Generalized hypertree decompositions: NP-hardness and tractable variants. In PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 13--22, New York, NY, USA, 2007. ACM.
[11]
G. Gottlob and S. Szeider. Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. The Computer Journal, 51(3):303--325, 2008.
[12]
M. Grohe. The structure of tractable constraint satisfaction problems. In MFCS 2006, pages 58--72, 2006.
[13]
M. Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1, 2007.
[14]
M. Grohe and D. Marx. Constraint solving via fractional edge covers. In SODA '06: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 289--298, New York, NY, USA, 2006. ACM Press.
[15]
M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive queries tractable? In STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 657--666, New York, NY, USA, 2001. ACM Press.
[16]
P. G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci., 61(2):302--332, 2000.
[17]
L. Lovász. Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3):319--324, 1978.
[18]
J. Matoušek. A combinatorial proof of Kneser's conjecture. Combinatorica, 24(1):163--170, 2004.
[19]
S. Oum. Approximating rank-width and clique-width quickly. In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, pages 49--58, 2005.
[20]
S. Oum and P. Seymour. Testing branch-width. J. Combin. Theory Ser. B, 97(3):385--393, 2007.
[21]
S.-i. Oum and P. Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514--528, 2006.
[22]
T. J. Schaefer. The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), pages 216--226. ACM, New York, 1978.
[23]
R. E. Tarjan. Decomposition by clique separators. Discrete Math., 55(2):221--232, 1985.
[24]
V. Vazirani. Approximation algorithms. Springer-Verlag, 2004.
[25]
S. H. Whitesides. An algorithm for finding clique cut-sets. Inform. Process. Lett., 12(1):31--32, 1981.

Cited By

View all
  • (2013)Measuring the structural complexity of feature modelsProceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2013.6693103(454-464)Online publication date: 11-Nov-2013
  • (2012)Factorised representations of query resultsProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274607(285-298)Online publication date: 26-Mar-2012
  • (2010)Structural tractability of enumerating CSP solutionsProceedings of the 16th international conference on Principles and practice of constraint programming10.5555/1886008.1886032(236-251)Online publication date: 6-Sep-2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
January 2009
1297 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2009

Qualifiers

  • Research-article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)16
  • Downloads (Last 6 weeks)2
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)Measuring the structural complexity of feature modelsProceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2013.6693103(454-464)Online publication date: 11-Nov-2013
  • (2012)Factorised representations of query resultsProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274607(285-298)Online publication date: 26-Mar-2012
  • (2010)Structural tractability of enumerating CSP solutionsProceedings of the 16th international conference on Principles and practice of constraint programming10.5555/1886008.1886032(236-251)Online publication date: 6-Sep-2010
  • (2010)The power of tree projectionsProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807127(327-338)Online publication date: 6-Jun-2010
  • (2010)Tractable hypergraph properties for constraint satisfaction and conjunctive queriesProceedings of the forty-second ACM symposium on Theory of computing10.1145/1806689.1806790(735-744)Online publication date: 5-Jun-2010
  • (2009)Generalized hypertree decompositions: NP-hardness and tractable variantsJournal of the ACM10.1145/1568318.156832056:6(1-32)Online publication date: 8-Sep-2009

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media