article

Hypertree width and related hypergraph invariants

Authors:

Isolde Adler,

Georg Gottlob,

Martin GroheAuthors Info & Claims

European Journal of Combinatorics, Volume 28, Issue 8

Pages 2167 - 2181

https://doi.org/10.1016/j.ejc.2007.04.013

Published: 01 November 2007 Publication History

Abstract

We study the notion of hypertree width of hypergraphs. We prove that, up to a constant factor, hypertree width is the same as a number of other hypergraph invariants that resemble graph invariants such as bramble number, branch width, linkedness, and the minimum number of cops required to win Seymour and Thomas's robber and cops game.

References

[1]

Adler, I., Marshals, monotone marshals, and hypertree-width. Journal of Graph Theory. v47. 275-296.

Crossref

Google Scholar

[2]

I. Adler, A note on monotonicity cost on hypergraphs, 2005. Unpublished note

Google Scholar

[3]

Cohen, D.A., Jeavons, P. and Gyssens, M., A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In: Kaelbling, L.P., Saffiotti, A. (Eds.), IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Professional Book Center. pp. 72-77.

Crossref

Google Scholar

[4]

Gottlob, G., Grohe, M., Musliu, N., Samer, M. and Scarcello, F., Hypertree decompositions: Structure, algorithms, and applications. In: Kratsch, D. (Ed.), Lecture Notes in Computer Science, vol. 3787. Springer Verlag. pp. 1-15.

Crossref

Google Scholar

[5]

Gottlob, G., Leone, N. and Scarcello, F., A comparison of structural CSP decomposition methods. Artificial Intelligence. v124 i2. 243-282.

Crossref

Google Scholar

[6]

Gottlob, G., Leone, N. and Scarcello, F., Hypertree decompositions and tractable queries. Journal of Computer and System Sciences. v64. 579-627.

Google Scholar

[7]

Gottlob, G., Leone, N. and Scarcello, F., Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences. v66. 775-808.

Crossref

Google Scholar

[8]

Grohe, M. and Marx, D., Constraint solving via fractional edge covers. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press. pp. 289-298.

Crossref

Google Scholar

[9]

Iwata, S., Fleischer, L. and Fujishige, S., A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM. v48 i4. 761-777.

Crossref

Google Scholar

[10]

Oum, S.-I., Approximating rank-width and clique-width quickly. In: Kratsch, D. (Ed.), Lecture Notes in Computer Science, vol. 3787. Springer. pp. 49-58.

Crossref

Google Scholar

[11]

Oum, S.-I. and Seymour, P.D., Approximating clique-width and branch-width. Journal of Combinatorial Theory. Series B. v96 i4. 514-528.

Crossref

Google Scholar

[12]

B. Reed, Tree width and tangles: A new connectivity measure and some applications. in: R.A. Bailey (Ed.) Surveys in Combinatorics, in: LMS Lecture Note Series, vol. 241, Cambridge University Press, 1997, pp. 87-162

Google Scholar

[13]

Robertson, N. and Seymour, P.D., Graph minors X. Obstructions to tree-decomposition. Journal of Combinatorial Theory. Series B. v52. 153-190.

Crossref

Google Scholar

[14]

Seymour, P.D. and Thomas, R., Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory. Series B. v58. 22-33.

Crossref

Google Scholar

Cited By

View all

Calautti MLivshits EPieris ASchneider M(2024)Combined Approximations for Uniform Operational Consistent Query AnsweringProceedings of the ACM on Management of Data10.1145/36516002:2(1-16)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651600
Gottlob GLanzinger MOkulmus CPichler R(2023)Fast Parallel Hypertree Decompositions in Logarithmic Recursion DepthACM Transactions on Database Systems10.1145/363875849:1(1-43)Online publication date: 30-Dec-2023
https://dl.acm.org/doi/10.1145/3638758
van Bremen TMeel KGeerts FNgo HSintos S(2023)Probabilistic Query Evaluation: The Combined FPRAS LandscapeProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588677(339-347)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588677
Show More Cited By

Index Terms

Hypertree width and related hypergraph invariants
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
      2. Hypergraphs
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Approximating fractional hypertree width

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, Constraint Satisfaction Problems (CSP) and various problems in database theory ...
Approximating fractional hypertree width
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms

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 ...
Generalized hypertree decompositions: np-hardness and tractable variants
PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image European Journal of Combinatorics

European Journal of Combinatorics Volume 28, Issue 8

November, 2007

231 pages

ISSN:0195-6698

Issue’s Table of Contents

Publisher

Academic Press Ltd.

United Kingdom

Publication History

Published: 01 November 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Calautti MLivshits EPieris ASchneider M(2024)Combined Approximations for Uniform Operational Consistent Query AnsweringProceedings of the ACM on Management of Data10.1145/36516002:2(1-16)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651600
Gottlob GLanzinger MOkulmus CPichler R(2023)Fast Parallel Hypertree Decompositions in Logarithmic Recursion DepthACM Transactions on Database Systems10.1145/363875849:1(1-43)Online publication date: 30-Dec-2023
https://dl.acm.org/doi/10.1145/3638758
van Bremen TMeel KGeerts FNgo HSintos S(2023)Probabilistic Query Evaluation: The Combined FPRAS LandscapeProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588677(339-347)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588677
Bumpus BKocsis Z(2023)Spined categoriesEuropean Journal of Combinatorics10.1016/j.ejc.2023.103794114:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.ejc.2023.103794
Gottlob GLanzinger MOkulmus CPichler RLibkin LBarceló P(2022)Fast Parallel Hypertree Decompositions in Logarithmic Recursion DepthProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3524153(325-336)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3524153
Lanzinger MLibkin LBarceló P(2022)The Complexity of Conjunctive Queries with Degree 2Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3524152(91-102)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3524152
Gottlob GOkulmus CPichler R(2022)Fast and parallel decomposition of constraint satisfaction problemsConstraints10.1007/s10601-022-09332-127:3(284-326)Online publication date: 3-Jun-2022
https://dl.acm.org/doi/10.1007/s10601-022-09332-1
Gottlob GLanzinger MPichler RRazgon I(2021)Complexity Analysis of Generalized and Fractional Hypertree DecompositionsJournal of the ACM10.1145/345737468:5(1-50)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1145/3457374
Lanzinger MLibkin LPichler RGuagliardo P(2021)Tractability Beyond ß-Acyclicity for Conjunctive Queries with NegationProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458308(355-369)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458308
Fischl WGottlob GLongo DPichler R(2021)HyperBenchACM Journal of Experimental Algorithmics10.1145/344001526(1-40)Online publication date: 9-Jul-2021
https://dl.acm.org/doi/10.1145/3440015
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Approximating fractional hypertree width

Approximating fractional hypertree width

Generalized hypertree decompositions: np-hardness and tractable variants

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations