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
1235
Venue
PODS
Year
2001
Pagerank
0.00010040854
Overall Rank
1,673 | 88.53%
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
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
673 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00015095061
814 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013841737
816 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013827772
1,857 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.6047945e-05
2,448 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 8.5693075e-05
2,550 Computing Cores for Data Exchange: New Algorithms and Practical Solutions 2005 PODS 8.4290753e-05
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
3,453 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.4004131e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
6,624 Queries Determined by Views: Pack Your Views 2007 PODS 5.8204482e-05
7,052 The Parameterized Complexity of Database Queries 2001 PODS 5.7171307e-05
7,759 The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability 2010 PODS 5.5505938e-05
9,009 Efficient Approximations of Conjunctive Queries 2012 PODS 5.3335287e-05
10,159 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 5.093636e-05
10,296 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 5.093636e-05
11,366 Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying 2023 PODS 5.093636e-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