Reproduce “Rerootable Hypertree Decompositions” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Zhekai Jiang, Christoph Koch, Peter Lindner, Reinhard Pichler, Qichen Wang
Rerootable normal form (RNF) extends hypertree decompositions with root-independent validity while retaining fixed-width tractability. The work proves that full rerootability is equivalent to projection-freeness, develops a modified robber-and-marshals characterization and an O(|E|^{2k}|V|) algorithm for fixed width, and finds that RNF preserves ordinary hypertree width on all 535 HyperBench queries tested, with only one increase among 1,079 additional low-width instances.
Key insights
- Rerootability is governed entirely by the projection-free property, isolating the source of root dependence in the HD special condition.
- Projection-free normal form is tractable but can require arbitrarily greater width than projection-free decompositions; enforcing symmetric normal-form conditions directly can be even more restrictive.
- RNF balances symmetry and algorithmic feasibility by treating one neighboring direction as exceptional rather than requiring identical component behavior in every direction.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.