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
- 1236
- Venue
- PODS
- Year
- 2001
- Pagerank
- 9.7901938e-05
- Overall Rank
- 2,015 | 85.99%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 15 of 15 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 626 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018973823 |
| 1,056 |
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates |
2017 |
SIGMOD |
0.0001441128 |
| 1,328 |
Hypertree Decompositions: Questions and Answers |
2016 |
PODS |
0.00012565612 |
| 2,063 |
Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability |
2014 |
PODS |
9.6447857e-05 |
| 2,296 |
Joins via Geometric Resolutions: Worst-case and Beyond |
2015 |
PODS |
9.0776226e-05 |
| 2,829 |
Computing Cores for Data Exchange: New Algorithms and Practical Solutions |
2005 |
PODS |
8.0546963e-05 |
| 3,715 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8220943e-05 |
| 4,953 |
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms |
2023 |
PODS |
5.8085795e-05 |
| 5,809 |
Queries Determined by Views: Pack Your Views |
2007 |
PODS |
5.3185501e-05 |
| 5,855 |
Optimal Join Algorithms Meet Top-k |
2020 |
SIGMOD |
5.3006096e-05 |
| 6,239 |
The Parameterized Complexity of Database Queries |
2001 |
PODS |
5.1417208e-05 |
| 7,473 |
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability |
2010 |
PODS |
4.7198203e-05 |
| 8,851 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4363908e-05 |
| 11,160 |
Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying |
2023 |
PODS |
4.1945683e-05 |
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 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 11,556 |
The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs |
2020 |
PODS |
4.1945683e-05 |
| 10,483 |
Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized |
2025 |
SIGMOD |
4.1945683e-05 |
| 11,132 |
A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition |
2024 |
VLDB |
4.1945683e-05 |
| 8,486 |
Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth |
2022 |
PODS |
4.4999394e-05 |
| 7,473 |
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability |
2010 |
PODS |
4.7198203e-05 |
| 626 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018973823 |
| 1,038 |
Weighted Hypertree Decompositions and Optimal Query Plans |
2004 |
PODS |
0.00014492414 |
| 1,328 |
Hypertree Decompositions: Questions and Answers |
2016 |
PODS |
0.00012565612 |
| 2,796 |
Hypertree Decompositions and Tractable Queries |
1999 |
PODS |
8.1112658e-05 |
| 11,324 |
The Complexity of Conjunctive Queries with Degree 2 |
2022 |
PODS |
4.1945683e-05 |