Cuts and Gauges for Submodular Width
2026-04-24 • Data Structures and Algorithms
Data Structures and AlgorithmsDatabasesDiscrete Mathematics
AI summaryⓘ
The authors study a measure called submodular width, which helps understand how hard it is to solve certain database queries. They show that submodular width can be closely approximated using a new geometric concept involving splitting edges in hypergraphs. This new view links submodular width to known graph ideas like treewidth and flow problems. The authors also provide conditions showing when submodular width strongly relates to another measure called generalized hypertree width.
submodular widthconjunctive querybranchwidthhypergraphtreewidthgeneralized hypertree widthmulticommodity flowconvex bodyedge separation
Authors
Matthias Lanzinger
Abstract
Submodular width is a central structural measure governing the complexity of conjunctive query evaluation. In this paper we recast submodular width in geometric terms. We how that submodular width can be approximated, up to a factor $3/2$, by a new branchwidth parameter defined in terms of edge separations in the hypergraph and the costs induced on them by admissible submodular functions. This reformulation turns lower bounds on submodular width into the problem of constructing well-balanced edge separations whose induced cost remains small. We then express this connection through a variational characterisation in terms of a convex body. Using these tools, we relate submodular width to more familiar graph-theoretic notions, including line-graph treewidth and multicommodity flow, and obtain general conditions under which submodular width is tightly linked to generalised hypertree width. In particular, under various natural conditions we show that \[ subw(H) \in Ω\left(\frac{ghw(H)}{\log ghw(H)} \right). \]