DBScholar

Back to papers

Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width

Summary: Introduce a Robber-and-Marshals game: hypergraph H has hypertree-width ≤ k iff k marshals can trap the robber, extending the cops-and-robbers/treewidth characterization to hypergraphs. Characterize HW[k]=GF_k(L) (k‑guarded fragment of existential-conjunctive FO) and show GF_k(FO) equals nonrecursive stratified datalog of hypertreewidth ≤ k. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h5334912244fc0b74
Venue
PODS
Year
2001
Pagerank
9.8609347e-05
Overall Rank
1,690 | 88.64%
DOI
10.1145/375551.375579

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{gottlob_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width}},
        url = {https://dl.acm.org/doi/10.1145/375551.375579},
        doi = {10.1145/375551.375579},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Leone, Nicola and Scarcello, Francesco},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
684 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014798237
812 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013729015
818 Hypertree Decompositions: Questions and Answers 2016 PODS 0.0001366708
1,812 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5803973e-05
2,481 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 8.403072e-05
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
2,594 Computing Cores for Data Exchange: New Algorithms and Practical Solutions 2005 PODS 8.2426092e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2582926e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
6,744 Queries Determined by Views: Pack Your Views 2007 PODS 5.6908598e-05
7,186 The Parameterized Complexity of Database Queries 2001 PODS 5.5912387e-05
7,922 The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability 2010 PODS 5.4261252e-05
9,169 Efficient Approximations of Conjunctive Queries 2012 PODS 5.2141412e-05
10,376 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 4.9793485e-05
10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9793485e-05
11,682 Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying 2023 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Semantically Similar Papers