arXiv CSopen access

Cuts and Gauges for Submodular Width

Cuts and Gauges for Submodular Width

arXiv:2604.22663v1 [cs.DS] 24 Apr 2026

MATTHIAS LANZINGER∗ , Institute of Logic and Computation, TU Wien, Austria 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 show 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   ghw(𝐻 ) subw(𝐻 ) ∈ Ω . log ghw(𝐻 )

Contents Abstract Contents 1 Introduction 2 Preliminaries 3 Lifted Cuts and Widths 4 The Geometry of the Submodular Realisable Body 4.1 An Antiblocker-Dual Interpretation 5 General Cut Certificates from Treewidth 5.1 Balanced Edge Set Functions Force Large Cuts 5.2 From Treewidth to Multicommodity Flows 5.3 From Multicommodity Flows to Cut Weightings 6 Connecting ghw and subw 6.1 A General Fractional Witness Principle 7 Complexity Consequences 8 Conclusion & Outlook 8.1 Conclusion 8.2 Directions for Future Research References A A Direct Lifted Submodular Width Lower Bound B Additional Details for Section 6 C A Natural Family with Logarithmic Edge Excess

1 1 2 4 6 8 13 15 15 16 19 21 23 24 25 25 26 28 29 30 32

∗ Supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201].

Author’s Contact Information: Matthias Lanzinger, Institute of Logic and Computation, TU Wien, Vienna, Austria, matthias. [email protected].

2

1

Matthias Lanzinger

Introduction

Context. Evaluation of conjunctive queries (CQs) refers to the problem of, given a relational FO formula 𝑞 built using only ∃ and conjunction and a relational structure 𝐷, deciding whether 𝑞 is satisfied in 𝐷. This represents one of the core algorithmic questions underlying data management but is also just as fundamental for a broad range of fields in computer science: it is equivalent to deciding the existence of a homomorphism between relational structures and to deciding constraint satisfaction problems. The general problem is NP-complete, but its wide use has inspired highly detailed research into the specific factors that make it hard or easy. For instance, recently Bulatov [3] and Zhuk [28] independently proved a PTIME/NP dichotomy for the problem depending on the form of 𝐷, concluding a decades long major research programme of understanding that side of the problem. On the other hand, the question of how the form of 𝑞 affects the complexity of CQ evaluation has also received major attention. Especially in a database setting, the structure of 𝑞 corresponds to the structure of a database query, and positive algorithmic results directly transfer into more efficient algorithms for database query evaluation. In this direction, the “cyclicity” of 𝑞 was identified as the major source of hardness. For constantly bounded arity of 𝑞, Grohe [13] showed that CQ evaluation is in PTIME exactly for queries of constantly bounded treewidth. When arity is not considered constant, generalisations of hypergraph 𝛼-acyclicity — such as generalised and fractional hypertree width (ghw and fhw, respectively) [12, 15] — were shown sufficient for PTIME algorithms, even when treewidth is unbounded. However, no matching lower bound is known in the unbounded rank setting (except for the special case of maximum hypergraph degree 2 [21]). From the perspective of parameterised complexity (one considers the query 𝑞 as the parameter), the situation is clearer. Seminal work of Marx [23] introduced submodular width (subw), and showed that bounded subw characterises exactly those classes of queries for which evaluation is fixedparameter tractable. This in turn has motivated the development of important new algorithmic techniques that achieve 𝑓 (𝑞)poly(𝐷) subw(𝑞) time [16, 19, 20]. Despite its algorithmic importance, the structural aspects of subw remain opaque. Bounded subw is the exact boundary for fixed-parameter tractability, while bounded ghw and fhw are the standard sufficient conditions for polynomial-time tractability, yet the relationship between these parameters is largely unresolved. While we know that subw(𝐻 ) ≤ fhw(𝐻 ) ≤ ghw(𝐻 ), neither inequality can be reversed generally1 . However, unbounded fhw (and hence ghw) with bounded subw is currently only known to occur in pathological examples [22]. In classical structural settings, they are only known to coincide under bounded rank and maximum degree 2 [21], but even there, the known relationship is purely qualitative, offering no insight into the quantitative relationship of the two parameters. The root of this disconnect is a lack of appropriate mathematical tools. Establishing lower bounds on subw requires identifying an edge-dominated submodular witness 𝑏 such that every tree decomposition of 𝐻 contains at least one bag with a large 𝑏-weight. The community has struggled to find general techniques to systematically construct these witnesses. Consequently, fundamental gaps remain in our understanding: we lack reliable ways to computationally check or certify submodular width, its exact relationship to measures like adaptive width is unmapped, and we do not even know if subw yields the optimal exponent for evaluation time. Bridging the gap between polynomial and fixed-parameter tractability for CQ evaluation demands a completely new analytical framework for subw.

1 Gottlob et al. [10] show reverse inequalities of the form ghw(𝐻 ) ≤ 𝑓 (fhw(𝐻 ) ) under a variety of conditions.

Cuts and Gauges for Submodular Width

3

Contribution. Our main contribution is a reformulation of submodular width in terms of symmetric cut functions and finite-dimensional convex geometry. The starting point is a branchwidth-type parameter, lifted submodular width, obtained by applying admissible submodular witnesses to edge boundaries. We prove that for every hypergraph 𝐻 , n 3 o subwlift (𝐻 ) ≤ subw(𝐻 ) ≤ max 1, subwlift (𝐻 ) . 2 lift That is, subw is equivalent to subw up to constant factor 3/2. This replaces tree decompositions by branch decompositions over certain cut cost functions. While this branchwidth perspective simplifies the structural decomposition, it still restricts us to cut weightings explicitly induced by submodular witnesses. Our second step removes this restriction by introducing a variational description of subwlift framed in terms of finite-dimensional convex geometry. We define the submodular realisable body 𝐾1Sub (𝐻 ) and its gauge2 𝛾𝐻Sub , demonstrating that 𝔅𝐻 (𝑞) subwlift (𝐻 ) = sup Sub 𝑞 ∈ S (𝐻 ) 𝛾𝐻 (𝑞) where S(𝐻 ) is the set of all symmetric edge set functions 2𝐸 → R ≥0 . This variational characterisation provides us with a significantly more technical freedom than previous formulations of submodular width. Instead of constructing cut weightings that correspond to a submodular function directly, the geometry of 𝐾1Sub (𝐻 ) allows us to use the much broader space of arbitrary symmetric edge-set functions to construct any 𝑞 that exhibits a large branchwidth value relative to its gauge. These first two results taken together provide us with an entirely new approach for reasoning about the submodular width of hypergraphs. Famously, freedom dies unless it is used. The second half of our contribution thus presents one way to build on this reframing of submodular width. Namely, we present a method for systematically constructing a kind of canonical function in S(𝐻 ). Drawing on classic results connecting well-linked sets and capacitated multicommodity flows in graphs, we prove that large line graph treewidth guarantees the existence of a 𝑞 ∈ S(𝐻 ) with 𝔅𝐻 (𝑞) ≥ 4/9 while bounding the local incident load on any single hyperedge 𝑒 ∈ 𝐸 (𝐻 ) to 𝑂 (log tw(𝑀)/tw(𝑀)), where 𝑀 is the line graph of 𝐻 . We subsequently formalise the translation of this bounded incident load into an upper bound on the gauge 𝛾𝐻Sub (𝑞). To this end we introduce the submodular gauge-routing ratio ℜ(𝐻 ), as a way measures how efficiently low incident load from the previous step can be transferred into an upper bound on 𝛾𝐻Sub (𝑞). Concretely, we obtain the general lower bound   ghw(𝐻 ) 1 subw(𝐻 ) ∈ Ω · . ℜ(𝐻 ) log ghw(𝐻 ) We then also relate this to concrete structural properties of the hypergraph. For instance, if 𝐻 satisfies the private intersection property (each pairwise intersection contains a degree-2 vertex), then ℜ(𝐻 ) ≤ 1. Alternatively, if 𝐻 has bounded edge excess ex(𝐻 ) (the sum of degrees in an edge, ignoring degree 2 vertices), then ℜ(𝐻 ) ≤ ex(𝐻 ) + 1. That is, we significantly generalise the previous best known conditions under which ghw and subw are tightly connected, and moreover, we give explicit quantitative bounds that were missing for previous work on the degree 2 case. We note that these examples are specific, easy to present, instances of our results. We additionally identify a more general principle under which ℜ(𝐻 ) is small. These structural results additionally demonstrate that for a wide range of structures, polynomial time tractability and fixed-parameter tractability coincide for CQ evaluation. 2 Intuitively, the gauge of a point is the minimum factor by which a fixed reference set must be scaled to contain it, serving

as a geometric measure of its complexity.

4

Matthias Lanzinger

Theorem 1.1 (Informal version of Theorem 7.3). Let H be a recursively enumerable class of hypergraphs with bounded submodular gauge-routing ratio, i.e., ℜ(H ) < ∞. Assuming ETH, the following are equivalent: (i) ghw(H ) < ∞. (ii) subw(H ) < ∞. (iii) CQ evaluation over queries with hypergraphs in H is tractable. (iv) CQ evaluation, parameterised by query size, over queries with hypergraphs in H is fixedparameter tractable. Organization. The remainder of the paper is structured as follows. Necessary technical preliminaries are introduced in Section 2. Section 3 formalises the boundary lift, establishing the core equivalence between submodular width and lifted submodular width. Section 4 develops the continuous geometry of the realisable submodular body and its dual antiblocker. Section 5 shows how to construct the universal balanced cuts via node-capacitated multicommodity flows. Section 6 combines the results of the previous three sections to show new lower bounds of subw in terms of ghw under a variety of conditions. Finally, Section 7 formalizes the complexity theoretic consequences for CQ evaluation, and Section 8 outlines the rich avenues for future research exposed by our new geometric approach to submodular width. 2

Preliminaries

Ð Ð 𝑋 as shorthand for 𝑠 ∈𝑋 𝑠. By convention, if 𝑋 = ∅, then For a set of sets 𝑋 we sometimes write
Ð 𝑋 = ∅. For set 𝑋 we also write 𝑋𝑘 for the set of all subsets of 𝑋 with cardinality 𝑘. Graphs & Hypergraphs. A hypergraph 𝐻 is a pair (𝑉 , 𝐸) where 𝑉 is a set of objects and 𝐸 ⊆ 2𝑉 . The degree of a vertex 𝑣 ∈ 𝑉 , also written deg𝐻 (𝑣) is the number of edges that contain 𝑣. The degree of 𝐻 is deg(𝐻 ) := max𝑣 ∈𝑉 deg𝐻 (𝑣). Throughout, we assume that hypergraphs have no isolated vertices, i.e., no vertices with degree 0. When there are multiple (hyper)graphs under discussion, we use the notation 𝑉 (𝐻 ) and 𝐸 (𝐻 ) to refer specifically to the vertex and edge sets of 𝐻 . The primal graph (also called Gaifman graph) of a hypergraph 𝐻 is the graph 𝑃 (𝐻 ) on vertex set 𝑉 (𝐻 ) in which two distinct vertices 𝑣, 𝑤 are adjacent if ∃𝑒 ∈ 𝐸 (𝐻 ) such that 𝑣, 𝑤 ∈ 𝑒. The dual hypergraph 𝐻 ∗ of 𝐻 has 𝐸 (𝐻 ) as its vertices, and for every 𝑣 ∈ 𝑉 (𝐻 ) it has the hyperedge 𝑓𝑣 = {𝑒 ∈ 𝐸 (𝐻 ) | 𝑣 ∈ 𝑒}. The graph 𝑃 (𝐻 ∗ ) will be referred to as the line graph of 𝐻 . For a hypergraph 𝐻 = (𝑉 , 𝐸) and a vertex 𝑥 ∈ 𝑉 , write Inc𝐻 (𝑥) := {𝑒 ∈ 𝐸Í| 𝑥 ∈ 𝑒} for the set of edges incident with 𝑥. For 𝛼 : 𝐸 → R ≥0 and 𝐹 ⊆ 𝐸, write 𝛼 (𝐹 ) := 𝑒 ∈𝐹 𝛼𝑒 . Thus 𝛼 (Inc𝐺 (𝑥)) is the total 𝛼-weight of edges incident with 𝑥. When 𝐺 = 𝑃 (𝐻 ∗ ) is fixed, we abbreviate to Inc(𝑥) := Inc𝑃 (𝐻 ∗ ) (𝑥). (Sub)Modular Set Functions. We will be interested in functions of the form 𝑏 : 2𝑆 → R ≥0 . that map sets to non-negative reals. We say that such a function is normalized if 𝑏 (∅) = 0, monotone if 𝑏 (𝑋 ) ≤ 𝑏 (𝑌 ) whenever 𝑋 ⊆ 𝑌 . It is modular if there are weights (𝑤 𝑣 )𝑣 ∈𝑆 with 𝑤 𝑣 ≥ 0 such that ∑︁ 𝑏 (𝑋 ) = 𝑤𝑣 ∀𝑋 ⊆ 𝑆. 𝑣 ∈𝑋

It is submodular if 𝑏 (𝑋 ) + 𝑏 (𝑌 ) ≥ 𝑏 (𝑋 ∪ 𝑌 ) + 𝑏 (𝑋 ∩ 𝑌 ) for all 𝑋, 𝑌 ⊆ 𝑆. Let Mod(𝐻 ) be the set of all functions 2𝑉 (𝐻 ) → R ≥0 that are normalised, and modular (and hence implicitly monotone). An edge profile p for hypergraph 𝐻 = (𝑉 , 𝐸) is a function 𝐸 (𝐻 ) → R ≥0 .

Cuts and Gauges for Submodular Width

5

Moreover, for an edge profile p define p-Mod(𝐻 ) := {𝑏 ∈ Mod(𝐻 ) | 𝑏 (𝑋 ) ≤ p(𝑒)

∀𝑒 ∈ 𝐸, ∀𝑋 ⊆ 𝑒}.

Similarly, Sub(𝐻 ) is the set of normalised, monotone, submodular functions, with p-Sub(𝐻 ) defined analogously to p-Mod. We write 1 for the edge profile that maps every edge to 1. 1-Mod then corresponds to the so-called edge-dominated normalised, monotone, and modular functions. Branch decompositions. For hypergraph 𝐻 = (𝑉 , 𝐸), a branch decomposition of 𝐸 is a pair (𝑇 , 𝛿) where 𝑇 is a subcubic (i.e., every vertex has at most degree 3) tree and 𝛿 is a bijection from the leaves of 𝑇 onto 𝐸. Every edge 𝑓 ∈ 𝐸 (𝑇 ) induces a bipartition (𝑋 𝑓 , 𝐸 \ 𝑋 𝑓 ) of the hyperedge set according to the two components of 𝑇 − 𝑓 . We call a function 𝑞 : 2𝐸 → R ≥0 an edge set function (of 𝐻 ). We say such a function is symmetric if 𝑞(𝑋 ) = 𝑞(𝐸 \𝑋 ). We will often refer to normalised symmetric edge set functions as cut weightings. For cut weighting 𝑞 define 𝔅𝐻 (𝑞) := min max 𝑞(𝑋𝑒 ), (𝑇 ,𝛿 ) 𝑒 ∈𝐸 (𝑇 )

where the minimum runs over branch decompositions (𝑇 , 𝛿) of 𝐸 (𝐻 ). By convention, if |𝐸| ≤ 1, 𝔅𝐻 (𝑞) is always 0. That is, 𝔅𝐻 is simply branchwidth over some symmetric normalised weighting function for the cuts, similar to previous work on branchwidth of connectivity functions, see e.g., [14, 25]. Note however that we generally do not deal with connectivity functions here as our cut weightings are not necessarily submodular. Tree decompositions. A tree decomposition of a hypergraph 𝐻 is a pair (𝑇 , 𝐵), where 𝑇 is a tree and 𝐵 : 𝑉 (𝑇 ) → 2𝑉 (𝐻 ) such that: • for each 𝑒 ∈ 𝐸 (𝐻 ) there is a node 𝑢 ∈ 𝑉 (𝑇 ) such that 𝑒 ⊆ 𝐵(𝑢). • for every vertex 𝑣 ∈ 𝑉 (𝐻 ), the set of nodes {𝑢 ∈ 𝑉 (𝑇 ) | 𝑣 ∈ 𝐵(𝑢)} is non-empty and forms a connected subgraph of 𝑇 . For 𝑏 : 2𝑉 (𝐻 ) → R, the 𝑏-width of a tree decomposition (𝑇 , 𝐵) is max𝑢 ∈𝑉 (𝑇 ) 𝑏 (𝐵(𝑢)). The 𝑏-width of 𝐻 is defined as 𝜏𝑏 (𝐻 ) := min max 𝑏 (𝐵(𝑢)) (𝑇 ,𝐵) 𝑢 ∈𝑉 (𝑇 )

where the minimum ranges over all tree decompositions (𝑇 , 𝐵) of 𝐻 . The treewidth tw(𝐻 ) of 𝐻 is 𝜏𝑏 where 𝑏 : 𝑈 ↦→ |𝑈 | − 1. The generalised hypertree width ghw(𝐻 ) = 𝜏𝑏 where 𝑏 maps set 𝑈 ⊆ 𝑉 (𝐻 ) to its edge cover number [12]. The following is well known and easy to verify (see, e.g., [21]). Proposition 2.1. For every hypergraph 𝐻 it holds that ghw(𝐻 ) ≤ tw(𝐻 ∗ ) + 1. The adaptive width adw [22] and submodular width subw [23] of 𝐻 are defined as adw(𝐻 ) =

sup 𝑏 ∈1-Mod(𝐻 )

𝜏𝑏 (𝐻 )

subw(𝐻 ) =

sup

𝜏𝑏 (𝐻 )

𝑏 ∈1-Sub(𝐻 )

It is known that ghw is always at least as high as subw. Much of this paper is concerned with the question under which conditions the two measures are linked more closely. Proposition 2.2 (Marx [23]). For every hypergraph 𝐻 it holds that adw(𝐻 ) ≤ subw(𝐻 ) ≤ ghw(𝐻 ).

6

Matthias Lanzinger

Cones & Gauges. Let 𝑋 be a real vector space. A set 𝐶 ⊆ 𝑋 is a cone if whenever 𝑥 ∈ 𝐶 and 𝛼 ≥ 0, we also have 𝛼𝑥 ∈ 𝐶. In other words, together with every point, the set contains the whole ray starting at the origin and passing through that point. A cone 𝐶 is convex if whenever 𝑥, 𝑦 ∈ 𝐶 and 𝛼, 𝛽 ≥ 0, we have 𝛼𝑥 + 𝛽𝑦 ∈ 𝐶. Equivalently, 𝐶 is closed under addition and under multiplication by nonnegative scalars. If 𝑋 is equipped with a topology (for example, if 𝑋 = R𝑛 with the usual topology), then a convex cone 𝐶 ⊆ 𝑋 is a closed convex cone if it is closed as a subset of 𝑋 . For any nonempty set 𝐴 ⊆ R𝑁≥0 , define its gauge (also called a Minkowski functional) as 𝛾𝐴 (𝑥) := inf {𝛼 ≥ 0 | 𝑥 ∈ 𝛼 · 𝐴}, with value +∞ if no such 𝛼 exists. A multivariate function 𝑓 (𝑥 1, . . . , 𝑥𝑛 ) is degree-1 positively homogeneous if 𝑓 (𝛼 𝑥 1, . . . , 𝛼 𝑥𝑛 ) = 𝛼 𝑓 (𝑥 1, . . . , 𝑥𝑛 ) 3

Lifted Cuts and Widths

In this section we introduce our first major reframing of submodular width. Part of the technical difficulty in understanding the submodular width of a hypergraph lies in reasoning about 𝜏𝑏 for arbitrary 𝑏 ∈ 1-Sub. In this section we identify an alternative way to understand the problem by instead considering cuts of the hypergraph, that themselves are weighted by some symmetric edge set function 𝜆 : 2𝐸 → R ≥0 . Concretely, we introduce a branchwidth analogue of submodular width (and adaptive width) that is equivalent to subw up to a constant factor 3/2. The key insight in constructing this branchwidth parameter is to base it specifically on cut weightings that are induced by 𝑏 ∈ 1-Sub. Definition 3.1 (Boundary Lift). For hypergraph 𝐻 = (𝑉 , 𝐸), define the boundary function Ø  Ø  𝜕𝐻 (𝐹 ) := 𝐹 ∩ (𝐸 \ 𝐹 ) consisting of all vertices that are in both sides of the edge bipartition induced by 𝐹 . For normalised and monotone 𝑏 : 2𝑉 → R ≥0 define the boundary lift of 𝑏 as 𝜆𝑏 := 𝑏 ◦ 𝜕𝐻 , i.e., 𝜆𝑏 (𝐹 ) = 𝑏 (𝜕𝐻 (𝐹 ))

∀𝐹 ⊆ 𝐸

Proposition 3.2. Let 𝑏 : 2𝑉 → R ≥0 be normalised. Then its boundary lift 𝜆𝑏 is a normalised symmetric edge set function. Proof. Recall that 𝑏 is normalised and 𝜕𝐻 (∅) = ∅, hence 𝜆𝑏 (∅) = 𝑏 (∅) = 0. Symmetry is immediate from 𝜕𝐻 (𝐹 ) = 𝜕𝐻 (𝐸 \ 𝐹 ). □ Definition 3.3 (Lifted width). The lifted submodular width of 𝐻 is subwlift (𝐻 ) := sup{𝔅𝐻 (𝜆𝑏 ) | 𝑏 ∈ 1-Sub(𝐻 )}. Analogously, define lifted adaptive width adwlift (𝐻 ) = sup{𝔅𝐻 (𝜆𝑏 ) | 𝑏 ∈ 1-Mod(𝐻 )}. Lifted submodular width is thus a measure of how expensive it is to cut a hypergraph, under certain cost functions. Importantly, this is in fact very closely tied to standard submodular width. This is best understood by thinking of 𝜕𝐻 (𝐹 ) as the “boundary” of an edge separation. Whenever the hyperedges are split into 𝐹 and 𝐸 (𝐻 ) \ 𝐹 , the vertices in 𝜕𝐻 (𝐹 ) are exactly those that still connect the two sides. Any decomposition that separates the two parts must therefore keep these vertices visible at the separator. Branch decompositions measure the size of this boundary directly, whereas tree decompositions measure the size of bags needed to contain it. So the two widths are measuring the same phenomenon from two different points of view.

Cuts and Gauges for Submodular Width

7

Theorem 3.4. Let 𝐻 = (𝑉 , 𝐸) be a hypergraph and let 𝑏 ∈ 1-Sub(𝐻 ). Then n 3 o 𝔅𝐻 (𝜆𝑏 ) ≤ 𝜏𝑏 (𝐻 ) ≤ max 1, 𝔅𝐻 (𝜆𝑏 ) . 2 Proof. For the first inequality, let (𝑇 , 𝐵) be a tree decomposition of 𝐻 of 𝑏-width 𝑤. For each hyperedge 𝑒 ∈ 𝐸 (𝐻 ) choose a node 𝑢𝑒 ∈ 𝑉 (𝑇 ) with 𝑒 ⊆ 𝐵(𝑢𝑒 ), and attach a new leaf ℓ𝑒 to 𝑢𝑒 labelled by 𝑒. Let 𝑇 + be a minimal subtree that spans all leaves ℓ𝑒 of the resulting tree. Replace every vertex of 𝑇 + of degree larger than 3 by an arbitrary subcubic refinement on the same incident branches. Every internal node created from the subcubic refinement of a node 𝑡 is also assigned the bag 𝐵(𝑡). Thus, the resulting leaf-labelled tree is a branch decomposition (𝑇 ′, 𝛿) of 𝐸 (𝐻 ). We claim that every cut of (𝑇 ′, 𝛿) is separated by some original bag 𝐵(𝑢). Indeed, if 𝑓 is an edge of 𝑇 ′ incident to a leaf ℓ𝑒 , then 𝜕𝐻 (𝑋 𝑓 ) ⊆ 𝑒 ⊆ 𝐵(𝑢𝑒 ). If 𝑓 comes from an original edge 𝑢 𝑢 ′ of 𝑇 , then any vertex meeting hyperedges on both sides of the cut must belong to both 𝐵(𝑢) and 𝐵(𝑢 ′ ), because the bags containing that vertex form a connected subtree crossing the edge 𝑢 𝑢 ′ . Finally, if 𝑓 was created inside the local subcubic refinement of a node 𝑢, then the two sides of the cut correspond to a partition of the branches incident with 𝑢. Any vertex meeting hyperedges on both sides again has its bag-subtree meeting two different incident branches at 𝑢, and therefore contains 𝑢 itself. In every case, 𝜕𝐻 (𝑋 𝑓 ) ⊆ 𝐵(𝑢) for some original node 𝑢. Now fix such a cut 𝑋 𝑓 . Since 𝜕𝐻 (𝑋 𝑓 ) ⊆ 𝐵(𝑢) and 𝑏 is monotone, 𝜆𝑏 (𝑋 𝑓 ) = 𝑏 (𝜕𝐻 (𝑋 𝑓 )) ≤ 𝑏 (𝐵(𝑢)) ≤ 𝑤 . Thus every cut of (𝑇 ′, 𝛿) has 𝜆𝑏 -value at most 𝑤, and therefore 𝔅𝐻 (𝜆𝑏 ) ≤ 𝜏𝑏 (𝐻 ).

For the second inequality, let (𝑇 , 𝛿) be a branch decomposition of 𝐸 with width 𝑘 = 𝔅𝐻 (𝜆𝑏 ). Suppressing degree-2 vertices – i.e., contracting the two incident edges of each such vertex – does not change the cuts, so we may assume that every internal vertex of 𝑇 has degree 3. If |𝐸 (𝐻 )| ≤ 1, then by convention 𝔅𝐻 (𝜆𝑏 ) = 0, and the trivial one-bag tree decomposition gives 𝜏𝑏 (𝐻 ) ≤ 1, so the claim is immediate. Assume |𝐸 (𝐻 )| ≥ 2. For each leaf ℓ labelled by a hyperedge 𝑒, define 𝐵(ℓ) = 𝑒. For each internal node 𝑢 of 𝑇 , let 𝐹 1, 𝐹 2, 𝐹 3 be the three hyperedge sets corresponding to the components of 𝑇 − 𝑢, and define Ø Ø  Ø Ø  Ø Ø  𝐵(𝑢) := 𝐹1 ∩ 𝐹2 ∪ 𝐹2 ∩ 𝐹3 ∪ 𝐹3 ∩ 𝐹1 .

We claim that these bags form a tree decomposition of 𝐻 . Every hyperedge 𝑒 is contained in its leaf bag 𝐵(ℓ) = 𝑒. Now fix 𝑣 ∈ 𝑉 (𝐻 ), and let 𝑇𝑣 be the minimal subtree of 𝑇 spanning all leaves labelled by hyperedges containing 𝑣. Then a node 𝑢 satisfies 𝑣 ∈ 𝐵(𝑢) if and only if 𝑢 ∈ 𝑉 (𝑇𝑣 ): this is immediate for leaves, and for an internal node 𝑢 with induced edge sets 𝐹 1, 𝐹 2, 𝐹 3 , the vertex 𝑣 belongs to 𝐵(𝑢) exactly when hyperedges containing 𝑣 occur in at least two of the three components of 𝑇 − 𝑢, which is equivalent to 𝑢 ∈ 𝑉 (𝑇𝑣 ). Hence the bags containing 𝑣 form the connected subtree 𝑇𝑣 . Fix an internal node 𝑢, and Ð write 𝑆𝑖 := 𝜕𝐻 (𝐹𝑖 ) for 𝑖 = 1, 2, 3. If 𝑥 ∈ 𝐵(𝑢), then 𝑥 lies in at least two of the three sets 𝑋𝑖 := 𝐹𝑖 for 𝑖 = 1, 2, 3. Suppose that 𝑥 ∈ 𝑋𝑖 ∩ 𝑋 𝑗 with 𝑖 ≠ 𝑗, then 𝑥 is incident with some hyperedge of 𝐹𝑖 and some hyperedge outside 𝐹𝑖 , so 𝑥 ∈ 𝜕𝐻 (𝐹𝑖 ) = 𝑆𝑖 . Likewise 𝑥 ∈ 𝑆 𝑗 . Therefore every 𝑥 ∈ 𝐵(𝑢) belongs to at least two of 𝑆 1, 𝑆 2, 𝑆 3 . In particular, 𝐵(𝑢) ⊆ 𝑈 := 𝑆 1 ∪ 𝑆 2 ∪ 𝑆 3

and

𝐵(𝑢) ⊆ 𝐼 := (𝑆 1 ∩ 𝑆 2 ) ∪ (𝑆 2 ∩ 𝑆 3 ) ∪ (𝑆 3 ∩ 𝑆 1 ).

8

Matthias Lanzinger

Applying submodularity thrice (always on the two left-most terms) yields a single chain of inequalities: 𝑏 (𝑆 1 ) + 𝑏 (𝑆 2 ) + 𝑏 (𝑆 3 ) ≥ 𝑏 (𝑆 1 ∪ 𝑆 2 ) + 𝑏 (𝑆 3 ) + 𝑏 (𝑆 1 ∩ 𝑆 2 )
≥ 𝑏 (𝑆 1 ∪ 𝑆 2 ) + 𝑏 (𝑆 1 ∩ 𝑆 2 ) ∪ 𝑆 3 + 𝑏 (𝑆 1 ∩ 𝑆 2 ∩ 𝑆 3 )
≥ 𝑏 (𝑆 1 ∪ 𝑆 2 ∪ 𝑆 3 ) + 𝑏 (𝑆 1 ∪ 𝑆 2 ) ∩ ((𝑆 1 ∩ 𝑆 2 ) ∪ 𝑆 3 ) + 𝑏 (𝑆 1 ∩ 𝑆 2 ∩ 𝑆 3 ) | {z } | {z } | {z } 𝑈

≥0

𝐼

Observe that (𝑆 1 ∪𝑆 2 ) ∩ ((𝑆 1 ∩𝑆 2 ) ∪𝑆 3 ) = (𝑆 1 ∩𝑆 2 ) ∪ (𝑆 2 ∩𝑆 3 ) ∪ (𝑆 3 ∩𝑆 1 ) = 𝐼 . Now, by nonnegativity of 𝑏, we may drop the last term and by monotonicity 𝑏 (𝑈 ), 𝑏 (𝐼 ) ≥ 𝑏 (𝐵(𝑢)), hence 𝑏 (𝑆 1 ) + 𝑏 (𝑆 2 ) + 𝑏 (𝑆 3 ) ≥ 𝑏 (𝑈 ) + 𝑏 (𝐼 ) ≥ 2 𝑏 (𝐵(𝑢)). Using 𝜆𝑏 (𝐹𝑖 ) = 𝑏 (𝑆𝑖 ) and 𝜆𝑏 (𝐹𝑖 ) ≤ 𝑘, we obtain 2 𝑏 (𝐵(𝑢)) ≤ 𝜆𝑏 (𝐹 1 ) + 𝜆𝑏 (𝐹 2 ) + 𝜆𝑏 (𝐹 3 ) ≤ 3𝑘. 3 Thus 𝑏 (𝐵(𝑢)) ≤ 2 𝑘 for any internal node 𝑢.

Leaf bags satisfy 𝑏 (𝐵(ℓ)) = 𝑏 (𝑒) ≤ 1 because 𝑏 ∈ 1-Sub(𝐻 ), and therefore also n 3 o 𝜏𝑏 (𝐻 ) ≤ max 1, 𝔅𝐻 (𝜆𝑏 ) . 2 □

Corollary 3.5. For every hypergraph 𝐻 , n 3 o subwlift (𝐻 ) ≤ subw(𝐻 ) ≤ max 1, subwlift (𝐻 ) . 2 n 3 o adwlift (𝐻 ) ≤ adw(𝐻 ) ≤ max 1, adwlift (𝐻 ) . 2 At first sight it might not be clear what is gained by this step. We argue that Corollary 3.5 in fact has real technical benefits. First, cuts are simpler to technically analyse than tree decompositions. Specifically to argue for high subw, one must argue that for some 𝑏 ∈ 1-Sub, some expensive bag under 𝑏 must occur in every tree decomposition. In general this is a highly challenging task, and it remains a major problem of current database theory how to do so. In the lifted setting the situation is in a sense simpler, we give weights to cuts 𝐹, 𝐸 \ 𝐹 , and roughly speaking it is then sufficient to demonstrate a cut weighting such that every bipartition of 𝐸 has large weight. To illustrate this point, we very simply prove a fairly general submodular width lower bound for a wide range of “hypergrid” style hypergraphs using boundary lifts in Section A. However, alone this approach is still limited. In particular, we are limited to considering cut weightings that are induced by a submodular function in the sense of Definition 3.1. However, we will show in the next section that this weakness cannot only be mitigated, but turned into a strength. 4

The Geometry of the Submodular Realisable Body

Throughout this section assume a fixed hypergraph 𝐻 = (𝑉 , 𝐸). We identify each set function 𝑉 𝑏 : 2𝑉 → R with its coordinate vector (𝑏 (𝑋 ))𝑋 ⊆𝑉 ∈ R2 , and we freely pass between the function and vector viewpoints. Accordingly, for 𝛼 ∈ R and set functions 𝑏, 𝑐 : 2𝑉 → R, scalar multiplication and addition are taken pointwise: (𝛼 · 𝑏) (𝑋 ) := 𝛼 · 𝑏 (𝑋 ),

(𝑏 + 𝑐) (𝑋 ) := 𝑏 (𝑋 ) + 𝑐 (𝑋 )

∀𝑋 ⊆ 𝑉 .

Likewise, inequalities between set functions are understood pointwise, i.e., 𝑏 ≤ 𝑐 means 𝑏 (𝑋 ) ≤ 𝑐 (𝑋 ) for all 𝑋 ⊆ 𝑉 .

Cuts and Gauges for Submodular Width

9

We use standard facts from analysis, finite-dimensional convex geometry and topology. In particular, we freely use that linear maps are continuous, that continuous images and coordinate projections of compact sets are compact, and that closed subsets of compact sets are compact. For a comprehensive treatment of these topics, we refer the reader to Rockafellar [27]. The following additional notation will be convenient. For a set 𝐴 ⊆ R𝑁≥0 , write ↓𝐴 := {𝑥 ∈ R𝑁≥0 | ∃𝑎 ∈ 𝐴 with 𝑥 ≤ 𝑎} for its (pointwise) downward closure. Moreover, we let S(𝐻 ) denote the set of all symmetric nonnegative edge-set functions of 𝐻 , that is, S(𝐻 ) := {𝑞 : 2𝐸 → R ≥0 | 𝑞(𝐹 ) = 𝑞(𝐸 \ 𝐹 ) ∀𝐹 ⊆ 𝐸}. Definition 4.1 (Boundary Lift Operator). Define the boundary-lift operator Λ𝐻 : R2 → R2 as 𝑉

𝐸

Λ𝐻 : 𝑏 ↦→ 𝑏 ◦ 𝜕𝐻 . Even when 𝑏 is normalised and submodular on 2𝑉 , its boundary lift Λ𝐻 𝑏 need not be submodular on 2𝐸 . Thus Λ𝐻 𝑏 is not, in general, a connectivity function. Nevertheless, symmetry and nonnegativity suffice for 𝔅𝐻 . Lemma 4.2. For every edge profile p, the set p-Sub(𝐻 ) is convex and compact. Proof. The set p-Sub(𝐻 ) is convex because normalization, monotonicity, submodularity, and the constraints 𝑏 (𝑒) ≤ p(𝑒) for 𝑒 ∈ 𝐸 are all preserved under convex combinations. 𝑉 Moreover, p-Sub(𝐻 ) ⊆ R2 is defined by finitely many closed conditions: 𝑏 (∅) = 0,

𝑏 (𝑋 ) ≤ 𝑏 (𝑌 )

∀𝑋 ⊆ 𝑌 ⊆ 𝑉 ,

𝑏 (𝑋 ) + 𝑏 (𝑌 ) ≥ 𝑏 (𝑋 ∪ 𝑌 ) + 𝑏 (𝑋 ∩ 𝑌 )

∀𝑋, 𝑌 ⊆ 𝑉 ,

and 𝑏 (𝑒) ≤ p(𝑒) for all 𝑒 ∈ 𝐸. Hence p-Sub(𝐻 ) is closed. To show boundedness, choose for each vertex 𝑣 ∈ 𝑉 a hyperedge 𝑒 𝑣 ∈ 𝐸 with 𝑣 ∈ 𝑒 𝑣 . Recall that we assume throughout that every vertex of 𝐻 lies in some hyperedge. By monotonicity, 0 ≤ 𝑏 ({𝑣 }) ≤ 𝑏 (𝑒 𝑣 ) ≤ p(𝑒 𝑣 ). Now recall that normalised submodular functions are subadditive, i.e., 𝑏 (𝑋 ∪ 𝑌 ) ≤ 𝑏 (𝑋 ) + 𝑏 (𝑌 )

∀𝑋, 𝑌 ⊆ 𝑉 .

Repeated application of this inequality then also implies ∑︁ 𝑏 (𝑋 ) ≤ 𝑏 ({𝑣 }) ∀𝑋 ⊆ 𝑉 . 𝑣 ∈𝑋

Therefore

0 ≤ 𝑏 (𝑋 ) ≤

∑︁ 𝑣 ∈𝑋

p(𝑒 𝑣 ) ≤

∑︁

p(𝑒 𝑣 )

∀𝑋 ⊆ 𝑉 .

𝑣 ∈𝑉

So every coordinate 𝑏 (𝑋 ) is uniformly bounded on p-Sub(𝐻 ). Thus p-Sub(𝐻 ) is closed and bounded in a finite-dimensional space, and therefore compact.

□

Definition 4.3 (Realisable Body and Submodular Gauge). For an edge profile p, define the submodular realisable body 𝐾pSub (𝐻 ) :=↓Λ𝐻 (p-Sub(𝐻 )). In other words, 𝐾pSub (𝐻 ) is the (pointwise) downward closure of Λ𝐻 (p-Sub(𝐻 )) in R2≥0 . We refer to the gauge on the submodular realisable body as the submodular gauge, namely, 𝐸

Sub 𝛾 p,𝐻 (𝑞) := 𝛾𝐾pSub (𝐻 ) (𝑞) = inf {𝛼 ≥ 0 | 𝑞 ∈ 𝛼 · 𝐾pSub (𝐻 )}.

10

Matthias Lanzinger

Sub . We will primarily be interested in the unit edge profile 1, for this we write 𝛾𝐻Sub := 𝛾 1,𝐻

While our results primarily rely on the unit profile 1 (matching the 1-Sub constraint), we believe it beneficial to establish the geometric results for arbitrary edge profiles p. On the one hand, this illustrates that there is a robust principle underlying these results. On the other hand, edge profiles in a sense express constraints on the data, similar to the study of degree-aware submodular width [18, 19]. Thus, this more general technical development may be useful for future work along those lines. Proposition 4.4. For every edge profile p, the set 𝐾pSub (𝐻 ) is nonempty, compact, convex, and coordinatewise downward closed. Proof. The zero vector belongs to p-Sub(𝐻 ), so 0 ∈ 𝐾pSub (𝐻 ). Downward closure holds by definition. For convexity, let 𝑞𝑖 ≤ Λ𝐻 (𝑏𝑖 ) with 𝑏𝑖 ∈ p-Sub(𝐻 ) for 𝑖 = 1, 2, and let 0 ≤ 𝛼 ≤ 1. Then 𝛼𝑞 1 + (1 − 𝛼)𝑞 2 ≤ 𝛼Λ𝐻 (𝑏 1 ) + (1 − 𝛼)Λ𝐻 (𝑏 2 ) = Λ𝐻 (𝛼𝑏 1 + (1 − 𝛼)𝑏 2 ). Since p-Sub(𝐻 ) is convex by Lemma 4.2, also 𝛼𝑏 1 +(1−𝛼)𝑏 2 ∈ p-Sub(𝐻 ), and hence 𝛼𝑞 1 +(1−𝛼)𝑞 2 ∈ 𝐾pSub (𝐻 ). That is, 𝐾pSub (𝐻 ) is convex as well. For compactness, Lemma 4.2 states that p-Sub(𝐻 ) is compact. Since Λ𝐻 is linear, hence continu𝐸 ous, the image 𝑈 := Λ𝐻 (p-Sub(𝐻 )) is compact in R2≥0 . Because 𝑈 is compact it is also bounded. That is, there exists 𝐵 < ∞ such that 𝑢 (𝐹 ) ≤ 𝐵 for all 𝑢 ∈ 𝑈 and all 𝐹 ⊆ 𝐸 (𝐻 ). Now consider 𝑆 := {(𝑞, 𝑢) ∈ R2≥0 × 𝑈 | 𝑞 ≤ 𝑢}. 𝐸

Since 𝑞 ≤ 𝑢 coordinatewise and every coordinate of every 𝑢 ∈ 𝑈 is at most 𝐵, we have 𝑆 ⊆ [0, 𝐵] 2 × 𝑈 . 𝐸

Moreover, 𝑆 is closed in R2 × R2 , hence also closed in the compact set [0, 𝐵] 2 × 𝑈 . Therefore 𝑆 is compact. Its projection onto the first coordinate is exactly 𝐾pSub (𝐻 ), so 𝐾pSub (𝐻 ) is compact. □ 𝐸

𝐸

𝐸

The next lemma isolates the abstract variational mechanism behind our geometric reformulation. This part of the argument is not specific to submodularity. It holds for any compact family of feasible symmetric profiles, that feasibility is preserved under decreasing coordinates, and that the objective under consideration is monotone and positively homogeneous of degree 1. In our application of the lemma below, the feasible family is the set of boundary lifts realised by functions in p-Sub(𝐻 ), and its downward closure is exactly the realisable body 𝐾pSub (𝐻 ). We nevertheless state and prove the following lemma in this general form to make it clear that this applies all the same to analogous width measures, and in particular to adaptive width via the realisable body 𝐾pMod (𝐻 ). Lemma 4.5. Let 𝐾 ⊆ S(𝐻 ) be nonempty and compact, and define its symmetric downward closure 𝐾 ↓S := (↓ 𝐾) ∩ S(𝐻 ) = {𝑞 ∈ S(𝐻 ) | ∃𝑢 ∈ 𝐾 such that 𝑞 ≤ 𝑢}. That is, 𝐾 ↓S is the symmetric slice of the downward closure of 𝐾. Let Φ : S(𝐻 ) → R ≥0 be monotone and degree-1 positively homogeneous. Then Φ(𝑞) , 𝛾 𝑞 ∈ S (𝐻 ) 𝐾 ↓S (𝑞)

sup Φ(𝑢) = sup 𝑢 ∈𝐾

with the conventions 0/0 := 0 and 𝑎/∞ := 0 for 𝑎 < ∞.

Cuts and Gauges for Submodular Width

11

Proof. Since every 𝑞 ∈ 𝐾 ↓S is dominated by some 𝑢 ∈ 𝐾, monotonicity of Φ gives sup Φ(𝑞) = sup Φ(𝑢). 𝑢 ∈𝐾

𝑞 ∈𝐾 ↓S

Now fix 𝑞 ∈ S(𝐻 ). If 𝛾𝐾 ↓S (𝑞) = ∞, then the ratio is 0 by convention. So suppose 𝛾 := 𝛾𝐾 ↓S (𝑞) < ∞. Then for every 𝛼 > 𝛾 one has 𝑞 ∈ 𝛼𝐾 ↓S , so 𝑞 = 𝛼𝑞 ′ for some 𝑞 ′ ∈ 𝐾 ↓S . Hence Φ(𝑞) = 𝛼 Φ(𝑞 ′ ) ≤ 𝛼 sup Φ(𝑢) = 𝛼 sup Φ(𝑢). 𝑢 ∈𝐾

𝑢 ∈𝐾 ↓S

That is, we have Φ(𝑞) ≤ 𝛼 sup𝑢 ∈𝐾 Φ(𝑢) and dividing by 𝛼 > 𝛾 ≥ 0 we have that If 𝛾 > 0, taking the infimum over 𝛼 > 𝛾 yields

Φ(𝑞) 𝛼 ≤ sup𝑢 ∈𝐾 Φ(𝑢).

Φ(𝑞) ≤ sup Φ(𝑢). 𝛾 𝑢 ∈𝐾 If 𝛾 = 0, then the same inequality holds for every 𝛼 > 0, and taking the (right-sided) limit as 𝛼 → 0+ gives Φ(𝑞) = 0, so the conclusion remains valid with the convention 0/0 := 0. For the reverse inequality, every 𝑢 ∈ 𝐾 lies in 𝐾 ↓S , so 𝛾𝐾 ↓S (𝑢) ≤ 1. Therefore for every 𝑢 ∈ 𝐾 \{0}, Φ(𝑢) ≥ Φ(𝑢). 𝛾𝐾 ↓S (𝑢) If 𝑢 = 0, then Φ(0) = 0 by positive homogeneity, so the same conclusion is consistent with 0/0 := 0. Taking the supremum over 𝑢 ∈ 𝐾 proves the reverse inequality. □ We are missing only one final piece of the puzzle. Positive homogeneity is essential in Lemma 4.5. It is what allows the scaling parameter from the gauge to appear as the normalising denominator, in particular in the step passing from Φ(𝑞) ≤ 𝛼 sup𝑢 ∈𝐾 Φ(𝑢) for all 𝛼 > 𝛾 to Φ(𝑞)/𝛾 ≤ sup𝑢 ∈𝐾 Φ(𝑢). Fortunately, 𝔅𝐻 indeed has this property. Lemma 4.6. 𝔅𝐻 is monotone and positively homogeneous of degree 1. Proof. If 𝑞 ≤ 𝑞 ′ , then every branch decomposition has 𝑞-width at most its 𝑞 ′ -width, hence 𝔅𝐻 (𝑞) ≤ 𝔅𝐻 (𝑞 ′ ). Also, for every 𝛼 ≥ 0, every branch decomposition has (𝛼𝑞)-width equal to 𝛼 times its 𝑞-width, so 𝔅𝐻 (𝛼𝑞) = 𝛼 𝔅𝐻 (𝑞). □ Theorem 4.7 (variational characterisation). For every hypergraph 𝐻 , 𝔅𝐻 (𝑞) , Sub 𝑞 ∈ S (𝐻 ) 𝛾𝐻 (𝑞)

subwlift (𝐻 ) = sup

with the convention that profiles with 𝛾𝐻Sub (𝑞) = +∞ contribute ratio 0. Proof. Let 𝐾 = Λ𝐻 (1-Sub(𝐻 )). By Proposition 3.2, the set 𝐾 is contained in S(𝐻 ). Since Λ𝐻 is continuous and 1-Sub(𝐻 ) is compact by Lemma 4.2, the set 𝐾 is compact. Its symmetric downward closure is 𝐾 ↓S = {𝑞 ∈ S(𝐻 ) | ∃𝑢 ∈ 𝐾, 𝑞 ≤ 𝑢} = 𝐾1Sub (𝐻 ) ∩ S(𝐻 ). Since 𝐾1Sub (𝐻 ) is downward closed, its gauge agrees on symmetric profiles with the gauge of its symmetric slice. Indeed, one direction is immediate because 𝐾1Sub (𝐻 ) ∩ S(𝐻 ) ⊆ 𝐾1Sub (𝐻 ). Conversely, if 𝑞 ∈ S(𝐻 ) and 𝑞 ∈ 𝛼𝐾1Sub (𝐻 ) with 𝛼 > 0, then 𝑞/𝛼 ∈ 𝐾1Sub (𝐻 ) ∩ S(𝐻 ). If 𝛼 = 0, then necessarily 𝑞 = 0 (recall that if 0 ∈ 𝐾, then 𝛾𝐾 (0) = 0). Hence 𝛾𝐾 ↓S (𝑞) = 𝛾𝐻Sub (𝑞)

∀𝑞 ∈ S(𝐻 ).

12

Matthias Lanzinger

The functional 𝔅𝐻 is monotone and degree-1 positively homogeneous on S(𝐻 ) by Lemma 4.6. Applying Lemma 4.5 with Φ = 𝔅𝐻 therefore gives 𝔅𝐻 (𝑞) . Sub 𝑞 ∈ S (𝐻 ) 𝛾𝐻 (𝑞)

sup 𝔅𝐻 (𝑢) = sup 𝑢 ∈𝐾

By Definition 3.3, the left-hand side is exactly subwlift (𝐻 ).

□

By combining Theorem 4.7 with Corollary 3.5, one immediately obtains a variational approximation of subw(𝐻 ) up to the factor 23 . One can also observe that the supremum in Theorem 4.7 is in fact a maximum. Theorem 4.7 is the starting point for later sections. It replaces direct reasoning about witnesses 𝑏 ∈ 1-Sub by the geometry of the associated symmetric boundary profiles on 2𝐸 . This is also where our move to lifted parameters and cut weightings pays off. The variational characterisation provides us with new technical freedom, in the sense that we can argue lower bounds by arguing over arbitrary functions in S(𝐻 ). We provide two examples to illustrate these new possibilities. The following sections then employ this in a more general way, where we construct useful 𝑞 ∈ S(𝐻 ) without consideration for their realisability in terms of functions in 1-Sub(𝐻 ). Example 4.8. Let 𝐻 have edges 𝑒 1, 𝑒 2, 𝑒 3, 𝑒 4 , all containing a common vertex 𝑣, and suppose that these are the only intersections among the edges. Then for every nontrivial proper set ∅ ⊊ 𝐹 ⊊ 𝐸 (𝐻 ), 𝜕𝐻 (𝐹 ) = {𝑣 }. Hence for every 𝑏 ∈ 1-Sub(𝐻 ), ( 0, 𝐹 ∈ {∅, 𝐸 (𝐻 )}, Λ𝐻 𝑏 (𝐹 ) = 𝑏 ({𝑣 }), ∅ ⊊ 𝐹 ⊊ 𝐸 (𝐻 ). Since {𝑣 } ⊆ 𝑒𝑖 for every 𝑖, the edge-domination constraint implies 𝑏 ({𝑣 }) ≤ 1. Thus every boundary lift considered in the definition of subwlift is constant on all nontrivial cuts, with value at most 1. Now define 𝑞(𝐹 ) := |𝐹 | · (4 − |𝐹 |) ∀𝐹 ⊆ 𝐸 (𝐻 ). Then 𝑞 ∈ S(𝐻 ), with value 3 on singleton cuts and value 4 on cuts with 2 edges on each side. We see that 𝑞 is not itself realisable, i.e., 𝑞 ∉ 𝐾1Sub (𝐻 ). In fact, 𝛾𝐻Sub (𝑞) = 4: if 𝑞 ∈ 𝛼𝐾1Sub (𝐻 ), then every nontrivial cut value of 𝑞 must be at most 𝛼, so necessarily 𝛼 ≥ 4. Conversely, equality is attained because 𝑞 ≤ 4Λ𝐻 𝑏, where 𝑏 is the modular function given by 𝑏 (𝑋 ) = 1[𝑣 ∈ 𝑋 ]. We see that symmetry is a far weaker requirement than submodular realisability. Example 4.9. The variational principle is useful even with profiles that are not themselves realisable. Let 𝐻 = 𝐾𝑛 be the complete graph on 𝑛 vertices, viewed as a hypergraph with 2-element edges, and define the following 𝑞 ∈ S(𝐻 ): ( 1 if min{|𝐹 |, |𝐸 (𝐻 ) \ 𝐹 |} ≥ |𝐸 (𝐻 )|/3, 𝑞(𝐹 ) := 0 otherwise. Observe that 𝔅𝐻 (𝑞) = 1 as every branch decomposition of 𝐸 (𝐻 ) has a cut with both sides containing at least one third of the leaves, so some cut has 𝑞-value 1, while trivially every cut has value at most 1. Now let 𝑏 (𝑋 ) := |𝑋 |/2. Since every edge of 𝐾𝑛 has size 2, we have 𝑏 ∈ 1-Mod(𝐻 ) ⊆ 1-Sub(𝐻 ), and hence Λ𝐻 𝑏 (𝐹 ) = |𝜕𝐻 2(𝐹 ) | . Now observe that for every 𝐹 ⊆ 𝐸 (𝐻 ) with min{|𝐹 |, |𝐸 (𝐻 ) \ 𝐹 |} ≥ |𝐸 (𝐻 )|/3, one has |𝜕𝐻 (𝐹 )| ≥ 𝑛6 . Write 𝑈 := 𝑉 (𝐻 ) \ 𝜕𝐻 (𝐹 ). Then every vertex of 𝑈 has all its incident edges contained either in 𝐹 or in 𝐸 (𝐻 ) \ 𝐹 . Since 𝐾𝑛 [𝑈 ] is complete, all vertices of 𝑈 must choose the same side, for

Cuts and Gauges for Submodular Width

13

otherwise an edge of 𝐾𝑛 [𝑈 ] would belong to both 𝐹 and 𝐸 (𝐻 ) \ 𝐹 , a contradiction. That is, one side of the partition is covered by 𝜕𝐻 (𝐹 ). As both 𝐹 and 𝐸 (𝐻 ) \ 𝐹 have size at least |𝐸 (𝐻 )|/3, this )| yields |𝜕𝐻 (𝐹 )|(𝑛 − 1) ≥ |𝐸 (𝐻 = 𝑛 (𝑛−1) , so |𝜕𝐻 (𝐹 )| ≥ 𝑛/6. 3 6 𝑛 Thus on every balanced cut, Λ𝐻 𝑏 (𝐹 ) = |𝜕𝐻 2(𝐹 ) | ≥ 12 , and equivalently, 𝑞 ≤ 12 𝑛 Λ𝐻 𝑏. That in particular means that 𝑞 has very small submodular gauge, namely 𝛾𝐻Sub (𝑞) ≤ 12 𝑛 . That is, 𝑞 lies Sub deep inside the realisable body 𝐾1 (𝐻 ). Intuitively, this implies it can be scaled up to a “heavier” realisable cut weighting. Looking at the definition of 𝑞 it is not clear how, but the convex nature of the induced geometry guarantees that it is. To conclude, combining the low gauge with 𝔅𝐻 (𝑞) = 1 gives subwlift (𝐻 ) ≥

𝔅𝐻 (𝑞) 𝑛 ≥ . Sub 12 𝛾𝐻 (𝑞)

Note that this is slightly below the actual submodular width 𝑛/2 of the clique. The point we wish to illustrate is how the variational perspective opens up entirely new approaches to proving lower bounds on subw. 4.1

An Antiblocker-Dual Interpretation

Sub (𝑞) asks for the smallest scaling factor by which a candidate cut weighting 𝑞 must The quantity 𝛾 1,𝐻 be divided before it becomes realisable by some submodular witness. One can then consider a pricing scheme on cuts as a kind of dual certificate for this question. That is, the scheme assigns a price 𝑤 (𝐹 ) to each bipartition (𝐹, 𝐸 \ 𝐹 ) and is valid if every realisable profile collects total price at most 1. Because the realisable body is coordinatewise downward closed inside the nonnegative orthant, this is precisely the setting of so-called antiblocking duality for convex corners. Antiblockers originate in combinatorial optimisation [9] and also play an important role in links between graph theory and information theory, for example in classical work of Csiszár et al. [7]. Intuitively, an antiblocker consists of all cut-pricing schemes that charge at most 1 to every realisable profile, and the gauge of 𝑞 is the maximum total charge that any such scheme can extract from 𝑞. 𝐸 Formally, for any set 𝐾 ⊆ R2≥0 , define its antiblocker by n o 𝐸 abl(𝐾) := 𝑤 ∈ R2≥0 ⟨𝑞, 𝑤⟩ ≤ 1 for all 𝑞 ∈ 𝐾 ,

where ⟨𝑞, 𝑤⟩ :=

∑︁

𝑞(𝐹 )𝑤 (𝐹 )

𝐹 ⊆𝐸

denotes the standard inner product on R2 . Thus abl(𝐾) consists of all nonnegative linear functionals which are bounded by 1 on 𝐾. In our case, this gives a dual description of the submodular gauge. 𝐸

Proposition 4.10. Let 𝐾 ⊆ R𝑑 be nonempty, compact, and convex, and for 𝑦 ∈ R𝑑 define ℎ𝐾 (𝑦) := max𝑥 ∈𝐾 ⟨𝑥, 𝑦⟩ . Then, for every 𝛼 ≥ 0, 𝑥 ∈ 𝛼𝐾

⇐⇒

⟨𝑥, 𝑦⟩ ≤ 𝛼 ℎ𝐾 (𝑦) for all 𝑦 ∈ R𝑑 .

Proof. The forward implication is immediate: if 𝑥 = 𝛼𝑧 with 𝑧 ∈ 𝐾, then for every 𝑦 ∈ R𝑑 , ⟨𝑥, 𝑦⟩ = 𝛼 ⟨𝑧, 𝑦⟩ ≤ 𝛼 ℎ𝐾 (𝑦). Conversely, suppose 𝑥 ∉ 𝛼𝐾. Since 𝛼𝐾 is compact and convex, hence closed and convex, Rockafellar [27, Theorem 11.5] implies that 𝛼𝐾 is the intersection of the closed half-spaces containing it.

14

Matthias Lanzinger

Therefore there exists a closed half-space 𝐻 = {𝑧 ∈ R𝑑 | ⟨𝑧, 𝑦⟩ ≤ 𝛽} such that 𝛼𝐾 ⊆ 𝐻 but 𝑥 ∉ 𝐻 . Then ℎ𝛼𝐾 (𝑦) = max𝑧 ∈𝛼𝐾 ⟨𝑧, 𝑦⟩ ≤ 𝛽 < ⟨𝑥, 𝑦⟩. Since ℎ𝛼𝐾 (𝑦) = 𝛼 ℎ𝐾 (𝑦), it follows that ⟨𝑥, 𝑦⟩ > 𝛼 ℎ𝐾 (𝑦). This proves the contrapositive of the reverse implication.

□

Theorem 4.11. For every hypergraph 𝐻 , every edge profile p, and every 𝑞 ∈ R2≥0 , 𝐸

Sub 𝛾 p,𝐻 (𝑞) =

sup

⟨𝑞, 𝑤⟩,

𝑤 ∈abl(𝐾pSub (𝐻 ) )

with the convention that the right-hand side may be +∞. Proof. Write 𝐾 := 𝐾pSub (𝐻 ). By Proposition 4.4, the set 𝐾 is nonempty, compact, convex, and coordinatewise downward closed. 𝐸 For 𝑦 ∈ R2 , write ℎ𝐾 (𝑦) := max𝑥 ∈𝐾 ⟨𝑥, 𝑦⟩ as in Proposition 4.10, and observe that abl(𝐾) = {𝑤 ∈ 𝐸 R2≥0 : ℎ𝐾 (𝑤) ≤ 1}. 𝐸 Define 𝑦+ (𝐹 ) := max{𝑦 (𝐹 ), 0}. We first claim that ℎ𝐾 (𝑦) = ℎ𝐾 (𝑦+ ) for all 𝑦 ∈ R2 . First, for 𝐸 𝑥 ∈ 𝐾, define 𝑥 ′ ∈ R2≥0 by ( 𝑥 (𝐹 ), 𝑦 (𝐹 ) ≥ 0, ′ 𝑥 (𝐹 ) := 0, 𝑦 (𝐹 ) < 0. Then 0 ≤ 𝑥 ′ ≤ 𝑥 coordinatewise, so 𝑥 ′ ∈ 𝐾, and ⟨𝑥, 𝑦+ ⟩ = ⟨𝑥 ′, 𝑦⟩ ≤ ℎ𝐾 (𝑦). Taking the maximum 𝐸 over 𝑥 ∈ 𝐾 gives ℎ𝐾 (𝑦+ ) ≤ ℎ𝐾 (𝑦). The reverse inequality is immediate from 𝑦 ≤ 𝑦+ and 𝐾 ⊆ R2≥0 : since every 𝑥 ∈ 𝐾 is nonnegative, also ⟨𝑥, 𝑦⟩ ≤ ⟨𝑥, 𝑦+ ⟩ for every 𝑥. 𝐸 Now fix 𝛼 ≥ 0 and 𝑞 ∈ R2≥0 . By Proposition 4.10, 𝑞 ∈ 𝛼𝐾

⇐⇒

⟨𝑞, 𝑦⟩ ≤ 𝛼 ℎ𝐾 (𝑦) for all 𝑦 ∈ R2 . 𝐸

Using 𝑞 ≥ 0 and ℎ𝐾 (𝑦) = ℎ𝐾 (𝑦+ ), this is equivalent to ⟨𝑞, 𝑢⟩ ≤ 𝛼 ℎ𝐾 (𝑢) for all 𝑢 ∈ R2≥0 . We claim that this is in turn equivalent to ⟨𝑞, 𝑤⟩ ≤ 𝛼 for all 𝑤 ∈ abl(𝐾). If ⟨𝑞, 𝑢⟩ ≤ 𝛼ℎ𝐾 (𝑢) for 𝐸 all 𝑢 ∈ R2≥0 and 𝑤 ∈ abl(𝐾), then ℎ𝐾 (𝑤) ≤ 1, so ⟨𝑞, 𝑤⟩ ≤ 𝛼 ℎ𝐾 (𝑤) ≤ 𝛼. 𝐸 Conversely, assume ⟨𝑞, 𝑤⟩ ≤ 𝛼 for all 𝑤 ∈ abl(𝐾), and fix 𝑢 ∈ R2≥0 . If ℎ𝐾 (𝑢) = 0, then 𝑡𝑢 ∈ abl(𝐾) for every 𝑡 > 0, hence 𝑡 ⟨𝑞, 𝑢⟩ = ⟨𝑞, 𝑡𝑢⟩ ≤ 𝛼 for all 𝑡 > 0, which forces ⟨𝑞, 𝑢⟩ = 0 = 𝛼ℎ𝐾 (𝑢). If ℎ𝐾 (𝑢) > 0, then 𝑢/ℎ𝐾 (𝑢) ∈ abl(𝐾), so ⟨𝑞, 𝑢⟩ D 𝑢 E = 𝑞, ≤ 𝛼, ℎ𝐾 (𝑢) ℎ𝐾 (𝑢) 𝐸

that is, ⟨𝑞, 𝑢⟩ ≤ 𝛼 ℎ𝐾 (𝑢). We have therefore shown that, for every 𝛼 ≥ 0, 𝑞 ∈ 𝛼𝐾

⇐⇒

⟨𝑞, 𝑤⟩ ≤ 𝛼 for all 𝑤 ∈ abl(𝐾).

Hence Sub 𝛾 p,𝐻 (𝑞) = inf {𝛼 ≥ 0 : ⟨𝑞, 𝑤⟩ ≤ 𝛼 for all 𝑤 ∈ abl(𝐾)} =

sup ⟨𝑞, 𝑤⟩. 𝑤 ∈abl(𝐾 )

□ Combining this with Theorem 4.7 yields an equivalent dual form of the lifted submodular width.

Cuts and Gauges for Submodular Width

15

Corollary 4.12 (Dual variational form). For every hypergraph 𝐻 , subwlift (𝐻 ) = sup 𝑞 ∈ S (𝐻 )

inf

𝑤 ∈abl(𝐾1Sub (𝐻 ) )

𝔅𝐻 (𝑞) , ⟨𝑞, 𝑤⟩

with the conventions that 𝑎/0 := +∞ for 𝑎 > 0, and 0/0 := 0. Proof. By Theorem 4.7 and Theorem 4.11, subwlift (𝐻 ) = sup

𝔅𝐻 (𝑞)

𝑞 ∈ S (𝐻 ) sup𝑤 ∈abl(𝐾1Sub (𝐻 ) ) ⟨𝑞, 𝑤⟩

.

For fixed 𝑞, the quantity 𝔅𝐻 (𝑞) is independent of 𝑤, while ⟨𝑞, 𝑤⟩ ≥ 0. Hence 𝔅𝐻 (𝑞) 𝔅𝐻 (𝑞) = inf , sup𝑤 ∈abl(𝐾 Sub (𝐻 ) ) ⟨𝑞, 𝑤⟩ 𝑤 ∈abl(𝐾1Sub (𝐻 ) ) ⟨𝑞, 𝑤⟩ 1

with the stated conventions. Taking the supremum over 𝑞 ∈ S(𝐻 ) gives the result.

□

We have thus obtained a dual description of the submodular gauge in terms of antiblockers. Although we do not make further use of this perspective in the present paper, it seems to us to provide a helpful alternative interpretation of the gauge. Instead of reasoning directly about realisability, one may test a profile against nonnegative cut-pricing schemes. We expect that this dual viewpoint may be useful both for proving lower bounds on 𝛾𝐻Sub and for showing tightness of upper bounds coming from explicit realisations. 5

General Cut Certificates from Treewidth

The variational formula in Section 4 reduces lower bounds on subwlift (𝐻 ), and hence on subw(𝐻 ), to constructing a symmetric edge-set function 𝑞 ∈ S(𝐻 ) with two properties. First, 𝑞 must be large on all sufficiently balanced cuts of 𝐸 (𝐻 ). Second, 𝑞 must admit a concrete representation as a cut profile that is induced by an edge profile 𝛼 on the line graph 𝑀 := 𝑃 (𝐻 ∗ ), defined as follows: ∑︁ 𝑞(𝐹 ) = 𝛼𝑒 ∀𝐹 ⊆ 𝐸 (𝐻 ). 𝑒 ∈cut𝑀 (𝐹 )

Moreover, we require the local incident load of 𝛼 on the line graph to be strictly controlled, so that the resulting cut profile can ultimately be realised with a small submodular gauge cost. In this section, we develop the core routing machinery to achieve the first half of this goal. We show that the treewidth of the line graph guarantees the existence of a balanced cut profile with a bounded local load. Later, in Section 6, we will establish the structural interfaces that allow us to efficiently translate this bounded line-graph load into a bounded submodular gauge on the hypergraph. 5.1

Balanced Edge Set Functions Force Large Cuts

Throughout this section, a probability measure on a finite set Ω is simply a weight function Í 𝜌 : Ω → R ≥0 with 𝑥 ∈Ω 𝜌 (𝑥) = 1, extended additively to subsets by ∑︁ 𝜌 (𝐹 ) := 𝜌 (𝑥) ∀𝐹 ⊆ Ω. 𝑥 ∈𝐹

In particular, saying that a point 𝑥 ∈ Ω has 𝜌-mass at most 1/2 means 𝜌 ({𝑥 }) ≤ 1/2. The following is an adaptation of standard arguments for balanced cuts in branch decompositions, adapted to the specifics we use later.

16

Matthias Lanzinger

Lemma 5.1. Let 𝑇 be a subcubic tree with leaf set Ω, and let 𝜌 be a probability measure on Ω. Assume that every leaf ℓ ∈ Ω has 𝜌-mass at most 1/2. Then some edge 𝑓 of 𝑇 induces a bipartition (𝑋 𝑓 , Ω \ 𝑋 𝑓 ) of Ω such that min{𝜌 (𝑋 𝑓 ), 𝜌 (Ω \ 𝑋 𝑓 )} ≥ 1/3. Proof. Assign weight 𝜌 (ℓ) to each leaf ℓ and weight 0 to every internal vertex. Start at an arbitrary vertex 𝑡 0 . If some component 𝐶 of 𝑇 − 𝑡 0 has total weight greater than 1/2, move to the unique neighbor 𝑡 1 of 𝑡 0 that lies in 𝐶, and continue similarly. This process is well defined, since two distinct components of 𝑇 − 𝑡 cannot both have weight greater than 1/2. Moreover, if we move from 𝑡𝑖 into a component 𝐶𝑖 of 𝑇 − 𝑡𝑖 with weight greater than 1/2, then in 𝑇 − 𝑡𝑖+1 the component containing 𝑡𝑖 has weight 1 − 𝜌 (𝐶𝑖 ) < 1/2, so the process cannot immediately return across the same edge. Since 𝑇 is acyclic, a walk that never immediately backtracks also never revisits a vertex, so the process must terminate. Hence it terminates at a vertex 𝑡 ∗ such that every component of 𝑇 − 𝑡 ∗ has total weight at most 1/2. If 𝑡 ∗ is a leaf, then the unique component of 𝑇 −𝑡 ∗ has weight 1 − 𝜌 ({𝑡 ∗ }) ≤ 1/2, so 𝜌 ({𝑡 ∗ }) ≥ 1/2. By hypothesis 𝜌 ({𝑡 ∗ }) ≤ 1/2, hence 𝜌 ({𝑡 ∗ }) = 1/2, and the incident edge gives a 1/2–1/2 cut. Assume now that 𝑡 ∗ is internal. Since 𝑇 is subcubic, deg𝑇 (𝑡 ∗ ) ∈ {2, 3}. If the component masses are 𝑎, 𝑏 in the degree-2 case, then 𝑎 + 𝑏 = 1 and 𝑎, 𝑏 ≤ 1/2, so 𝑎 = 𝑏 = 1/2. If the component masses are 𝑎, 𝑏, 𝑐 in the degree-3 case, then 𝑎 + 𝑏 + 𝑐 = 1 and each of 𝑎, 𝑏, 𝑐 is at most 1/2, so not all three can be less than 1/3. Thus in every case some incident edge induces a cut with both sides of mass at least 1/3. □ Lemma 5.2. Let 𝑞 ∈ S(𝐻 ), let 𝜌 be a probability measure on 𝐸 such that 𝜌 ({𝑒}) ≤ 1/2 for all 𝑒 ∈ 𝐸, and let 𝜙 : [0, 1/2] → R ≥0 be nondecreasing. If for all 𝐹 ⊆ 𝐸 it holds that
𝑞(𝐹 ) ≥ 𝜙 min{𝜌 (𝐹 ), 𝜌 (𝐸 \ 𝐹 )} , then 𝔅𝐻 (𝑞) ≥ 𝜙 (1/3). Proof. Let (𝑇 , 𝛿) be any branch decomposition of 𝐻 . By Lemma 5.1, some cut 𝑓 ∈ 𝐸 (𝑇 ) satisfies min{𝜌 (𝑋 𝑓 ), 𝜌 (𝐸 \ 𝑋 𝑓 )} ≥ 13 . Hence 𝑞(𝑋 𝑓 ) ≥ 𝜙 (1/3) for some cut in every branch decomposition of 𝐻. □ 5.2

From Treewidth to Multicommodity Flows

We now turn to the main technical step, constructing a symmetric cut weighting 𝑞 ∈ S(𝐻 ) that is simultaneously large on balanced cuts and induced by an edge profile on the line graph with small local incident load. To obtain such a profile, we follow an established path from treewidth, to well-linked sets, to multicommodity flow routing. Accordingly, this subsection is not a new routing theorem, but rather a tailored adaptation of results of Reed [26], Feige et al. [8], and Chekuri et al. [5], adapted to the particular form needed for our variational framework. From now on, let 𝑀 := 𝑃 (𝐻 ∗ ) be the line graph of 𝐻 . Thus every set 𝑋 ⊆ 𝑉 (𝑀) is identified with a subset 𝐹 ⊆ 𝐸 (𝐻 ). For such 𝐹 write cut𝑀 (𝐹 ) := {𝑥𝑦 ∈ 𝐸 (𝑀) | 𝑥 ∈ 𝐹, 𝑦 ∉ 𝐹 } for the set of edges in 𝑀 that cross the cut. Í Let 𝛼 ∈ R𝐸≥0(𝑀 ) be an edge profile on 𝑀. Define 𝑞𝑀,𝛼 (𝐹 ) := 𝑒 ∈cut𝑀 (𝐹 ) 𝛼𝑒 for all 𝐹 ⊆ 𝐸 (𝐻 ). Note that 𝑞𝑀,𝛼 ∈ S(𝐻 ), since cut𝑀 (𝐹 ) = cut𝑀 (𝐸 (𝐻 ) \ 𝐹 ). For ℎ ∈ 𝐸 (𝐻 ) = 𝑉 (𝑀), the total 𝛼-weight incident with ℎ in 𝑀 is 𝛼 (Inc𝑀 (ℎ)). Let P (𝑀) denote the set of simple paths in 𝑀. A path weighting on 𝑀 is a function 𝜔 : P (𝑀) → Í R ≥0 with total mass 𝑃 ∈ P (𝑀 ) 𝜔 (𝑃) = 1. It induces an edge profile 𝛼 𝜔 in the line graph 𝑀 with weights ∑︁ 𝛼𝑒𝜔 :=

𝜔 (𝑃)

𝑃 ∋𝑒

∀𝑒 ∈ 𝐸 (𝑀),

Cuts and Gauges for Submodular Width

17

and with it the symmetric edge set function 𝑞𝜔 := 𝑞𝑀,𝛼 𝜔 ∈ S(𝐻 ). Lemma 5.3. For every path weighting 𝜔 on 𝑀 and every 𝐹 ⊆ 𝐸 (𝐻 ), ∑︁ 𝑞𝜔 (𝐹 ) = 𝜔 (𝑃) |𝐸 (𝑃) ∩ cut𝑀 (𝐹 )| . 𝑃 ∈ P (𝑀 )

Proof. By the definition of 𝛼 𝜔 and by interchanging two finite sums, 𝑞𝜔 (𝐹 ) =

∑︁

∑︁

∑︁

𝜔 (𝑃) =

𝑒 ∈cut𝑀 (𝐹 ) 𝑃 ∋𝑒

𝜔 (𝑃) |𝐸 (𝑃) ∩ cut𝑀 (𝐹 )| .

𝑃 ∈ P (𝑀 )

□ The point of the path-weighting formalism is that 𝑞𝜔 (𝐹 ) is exactly the expected number of edges of cut𝑀 (𝐹 ) traversed by a random simple path drawn from 𝜔. Thus, if 𝜔 spreads mass uniformly over many terminal pairs, then every cut separating many of those terminals forces 𝑞𝜔 (𝐹 ) to be large. At the same time, when 𝜔 comes from a feasible node-capacitated multicommodity flow, the local incident load of the induced edge profile 𝛼 𝜔 is controlled by the vertex capacities. This is the mechanism that converts treewidth into a balanced cut profile induced by an edge weighting on the line graph. Let 𝐺 be a graph. A set 𝑈 ⊆ 𝑉 (𝐺) is node-well-linked if for every 𝐴, 𝐵 ⊆ 𝑈 with |𝐴| = |𝐵|, there exist |𝐴| pairwise internally vertex-disjoint 𝐴–𝐵 paths in 𝐺. When 𝐴 ∩ 𝐵 ≠ ∅, we allow trivial paths joining each vertex of 𝐴 ∩ 𝐵 to itself. Proposition 5.4 (Reed [26], see also Lemma 2.1 [4]). Let 𝐺 be a graph. Let 𝑘 be the size of the largest node-well-linked set in 𝐺. Then 𝑘 ≤ tw(𝐺) ≤ 4𝑘. For 𝑆 ⊆ 𝑉 (𝐺), write 𝑁𝐺 (𝑆) := {𝑥 ∈ 𝑉 (𝐺) \ 𝑆 | ∃𝑦 ∈ 𝑆 s.t. 𝑥𝑦 ∈ 𝐸 (𝐺)}. A set 𝑈 ⊆ 𝑉 (𝐺) is 1-node-cut-linked if, for every 𝑆 ⊆ 𝑉 (𝐺) with |𝑆 ∩ 𝑈 | ≤ |𝑈 |/2, one has |𝑁𝐺 (𝑆)| ≥ |𝑆 ∩ 𝑈 |. It is a standard consequence of Menger’s Theorem [24] that node-well-linked sets are also 1-node-cut-linked (see also [5, Section 1.3]). Proposition 5.5. Every node-well-linked set is also 1-node-cut-linked. Our goal will be to move from cut-linkedness to a technically pleasant function in S(𝐻 ). We do so through node-capacitated multicommodity flows.
For {𝑢, 𝑣 } ∈ 𝑈2 let P𝑢𝑣 (𝐺) denote the set of simple 𝑢–𝑣 paths in 𝐺. Let 𝐺 be a graph and let 𝑈 ⊆ 𝑉 (𝐺). A node-capacitated multicommodity flow on 𝑈 is a family
𝑓 = 𝑓𝑢𝑣 {𝑢,𝑣 } ∈ (𝑈 ) with 𝑓𝑢𝑣 : P𝑢𝑣 (𝐺) → R ≥0 . 2 The value of the {𝑢, 𝑣 }-commodity is ∑︁ ∥ 𝑓𝑢𝑣 ∥ 1 := 𝑓𝑢𝑣 (𝑃). 𝑃 ∈ P𝑢𝑣 (𝐺 )

For 𝑥 ∈ 𝑉 (𝐺), the internal load of 𝑥 is load 𝑓 (𝑥) :=

∑︁

∑︁

{𝑢,𝑣 } ∈ (𝑈2 )

𝑃 ∈ P𝑢𝑣 (𝐺 ) 𝑥 ∈𝑉 (𝑃 )\{𝑢,𝑣 }

𝑓𝑢𝑣 (𝑃).

The flow is feasible if load 𝑓 (𝑥) ≤ 1 for every 𝑥 ∈ 𝑉 (𝐺).
If ∥ 𝑓𝑢𝑣 ∥ 1 = 𝜗 for every {𝑢, 𝑣 } ∈ 𝑈2 , we say that 𝑓 routes 𝜗 units between every unordered terminal pair. We use the convention that only internal vertices count against capacity; using the alternative convention in which endpoints contribute weight 1/2 changes only constant differences.

18

Matthias Lanzinger

Proposition 5.6 (Feige, Hajiaghayi, and Lee, Theorem 4.1 [8]). There exists an universal constant 𝐶 > 0 such that for every graph 𝐺, every terminal set 𝑈 ⊆ 𝑉 (𝐺) with |𝑈 | = 𝑘 ≥ 2, and every product multicommodity demand supported on 𝑈 , the node-capacitated max-flow/min-cut gap is at most 𝐶 log(𝑘). Proposition 5.7. There exists a universal constant 𝐶 > 0 such that the following holds. Let 𝐺 be a graph, let 𝑈 ⊆ 𝑉 (𝐺) be a 1-node-cut-linked set with 𝑚 := |𝑈 | ≥ 2. Then 𝐺 admits a feasible node-capacitated
multicommodity flow routing at least 1/(𝐶𝑚 log 𝑚) units between every unordered pair {𝑢, 𝑣 } ∈ 𝑈2 . Proof. The result is due to Chekuri, Khanna, and Shepherd [5, Section 1.3]. They use the following terminology. For a nonnegative weight function 𝜋 : 𝑋 → R ≥0 on terminals, 𝑋 is 𝜋-flow-linked if the product demand 𝜋 (𝑢)𝜋 (𝑣) 𝜋 (𝑋 ) can be feasibly routed between every unordered terminal pair 𝑢, 𝑣 ∈ 𝑋 in the relevant edge- or node-capacitated sense. In the node case, 𝑋 is 𝜋-node-cut-linked if |𝑁𝐺 (𝑆)| ≥ 𝜋 (𝑆 ∩ 𝑋 ) whenever 𝜋 (𝑆 ∩ 𝑋 ) ≤ 𝜋 (𝑋 )/2. They state that if 𝑋 is 𝜋-cut-linked, then it is (𝜋/𝛽)-flow-linked, where 𝛽 is the worst-case max-flow/min-cut gap for product multicommodity flow instances in the graph. By Proposition 5.6, the worst-case node-capacitated max-flow/min-cut gap for product demands supported on 𝑈 is at most 𝐶 log 𝑚. Apply this with 𝑋 = 𝑈 and 𝜋 (𝑢) = 1 for every 𝑢 ∈ 𝑈 . Then, since 𝑈 is 1-node-cut-linked, it is (𝜋/𝛽)-flow-linked with 𝛽 ≤ 𝐶 log 𝑚. The corresponding product demand between each unordered pair is (1/𝛽) (1/𝛽) 1 1 = ≥ , 𝑚/𝛽 𝛽𝑚 𝐶𝑚 log 𝑚 as claimed. □ Lemma 5.8. There exists a universal constant 𝐶 > 0 with the following property. For every graph 𝐺 and every 1-node-cut-linked set 𝑈 ⊆ 𝑉 (𝐺) with 𝑚 := |𝑈 | ≥ 2, there is a feasible node-capacitated multicommodity flow in 𝐺 that routes 1 𝜗≥ 𝐶 𝑚 log(𝑚)
units between every unordered pair {𝑢, 𝑣 } ∈ 𝑈2 . Proof. This is exactly Proposition 5.7, after increasing the universal constant if necessary. □
Definition 5.9. Let 𝑈 ⊆ 𝐸 (𝐻 ) with |𝑈 | = 𝑚 ≥ 2, and let 𝑓 = 𝑓𝑢𝑣 {𝑢,𝑣 } ∈ (𝑈 ) be a feasible node2
capacitated multicommodity flow in 𝑀 such that ∥ 𝑓𝑢𝑣 ∥ 1 = 𝜗 for every {𝑢, 𝑣 } ∈ 𝑈2 . Define the normalised path weighting 𝜔 𝑓 as ∑︁ 1 𝜔 𝑓 (𝑃) := 𝑚
𝑓𝑢𝑣 (𝑃) (𝑃 ∈ P (𝑀)), 2 𝜗 {𝑢,𝑣 } ∈ (𝑈 ) 2 where 𝑓𝑢𝑣 (𝑃) = 0 for 𝑃 ∉ P𝑢𝑣 (𝑀). Lemma 5.10. With notation as in Definition 5.9, 𝜔 𝑓 is a normalised path weighting of total mass 1. Moreover:

Cuts and Gauges for Submodular Width

19

(1) for every {𝑢, 𝑣 } ∈ 𝑈2 , the total 𝜔 𝑓 -mass of 𝑢–𝑣 paths is exactly 1/ 𝑚2 ; (2) if 𝛼 𝜔 𝑓 is the induced edge weighting on the line graph, then 2 4 ∀ℎ ∈ 𝐸 (𝐻 ), 𝛼 𝜔 𝑓 (Inc𝑀 (ℎ)) ≤ + 𝑚
𝑚 2 𝜗 (3) in particular, if 𝜗 ≥ 1/(𝐶 𝑚 log 𝑚), then log 𝑚 𝑚 for some constant 𝐶 ′ depending only on 𝐶. 𝛼 𝜔 𝑓 (Inc𝑀 (ℎ)) ≤ 𝐶 ′

Proof. Write 𝜔 = 𝜔 𝑓 . The total mass of 𝜔 is ∑︁ 1 𝜔 (𝑃) = 𝑚
2 𝜗 𝑃 ∈ P (𝑀 )

∀ℎ ∈ 𝐸 (𝐻 )

∑︁

∑︁

𝑓𝑢𝑣 (𝑃) = 1.

{𝑢,𝑣 } ∈ (𝑈2 ) 𝑃

For a fixed terminal pair {𝑢, 𝑣 }, the total 𝜔-mass assigned to 𝑢–𝑣 paths is 𝜗/( 𝑚2 𝜗) = 1/ 𝑚2 . Fix 𝑔 ∈ 𝐸 (𝐻 ). The total 𝜔-mass of paths for which 𝑔 is an endpoint of the terminal pair is at most 2/𝑚, with equality only when 𝑔 ∈ 𝑈 . For internal use, let 𝜑𝑔 (𝑢, 𝑣) denote the total flow of the {𝑢, 𝑣 }-commodity through 𝑔 as an internal vertex. Then ∑︁ ∑︁ 1 𝜑𝑔 (𝑢, 𝑣). 𝜔 (𝑃) = 𝑚
2 𝜗 {𝑢,𝑣 } ∈ (𝑈 ) 𝑃 ∈ P (𝑀 ) 2 𝑔 internal in 𝑃 Í Feasibility of the node-capacitated flow gives {𝑢,𝑣 } ∈ (𝑈 ) 𝜑𝑔 (𝑢, 𝑣) ≤ 1, so the total 𝜔-mass of paths 2
that use 𝑔 internally is at most 1/( 𝑚2 𝜗). Since every path in the support is simple, ∑︁ ∑︁ 4 2 𝛼 𝜔 (Inc𝑀 (𝑔)) = 𝜔 (𝑃) deg𝑃 (𝑔) ≤ 2 𝜔 (𝑃)1[𝑔 ∈ 𝑉 (𝑃)] ≤ + 𝑚
. 𝑚 2 𝜗 𝑃 ∈ P (𝑀 ) 𝑃 ∈ P (𝑀 ) For the final statement, if 𝜗 ≥ 1/(𝐶𝑚 log 𝑚), then 2

𝑚
≤ 2 𝜗

4𝐶 log 𝑚 8𝐶 log 𝑚 ≤ . 𝑚−1 𝑚

The remaining term 4/𝑚 is also at most 𝐶 ′′ log 𝑚/𝑚 for all 𝑚 ≥ 2, after choosing 𝐶 ′′ large enough. This gives the desired constant 𝐶 ′ . □ 5.3 From Multicommodity Flows to Cut Weightings We now extract from the routed flow a concrete symmetric cut weighting. The previous subsection produced a path weighting 𝜔 that spreads mass uniformly over many terminal pairs while keeping the induced incident load small. The next lemma converts the first property into a lower bound on cut values; the second property will later allow us to realise the resulting profile with small gauge cost. Lemma 5.11. Let 𝑈 ⊆ 𝐸 (𝐻 ) have size 𝑚 ≥ 2, and let 𝜌 be 𝜌 (𝐹 ) :=

|𝐹 ∩ 𝑈 | |𝑈 |

∀𝐹 ⊆ 𝐸 (𝐻 ).

Let 𝜔 be a path weighting on 𝑀 such that, for every unordered pair {𝑢, 𝑣 } ∈ 𝑈2 , the total 𝜔-mass of
𝑢–𝑣 paths is exactly 1/ 𝑚2 . Then 𝑞𝜔 (𝐹 ) ≥ 2𝜌 (𝐹 )𝜌 (𝐸 (𝐻 ) \ 𝐹 )

∀𝐹 ⊆ 𝐸 (𝐻 ).

20

Matthias Lanzinger

Proof. Fix 𝐹 ⊆ 𝐸 (𝐻 ) and write 𝑎 := |𝑈 ∩ 𝐹 |, 𝑏 := |𝑈 \ 𝐹 | = |𝑈 ∩ (𝐸 (𝐻 ) \ 𝐹 )|. Every path whose endpoints lie on opposite sides of 𝐹 and 𝐸 (𝐻 ) \ 𝐹 contains at least one edge of cut𝑀 (𝐹 ). Hence, by Lemma 5.3, 𝑞𝜔 (𝐹 ) ≥

𝑎𝑏 𝑚
= 2

2𝑎𝑏 2𝑎𝑏 2|𝑈 ∩ 𝐹 | · |𝑈 ∩ (𝐸 (𝐻 ) \ 𝐹 )| = 2𝜌 (𝐹 )𝜌 (𝐸 (𝐻 ) \ 𝐹 ). ≥ 2 = 𝑚(𝑚 − 1) 𝑚 |𝑈 | 2 □

Lemma 5.12. There exists a universal constant 𝑐 sup > 0 with the following property. Let 𝐻 be a hypergraph, let 𝑀 be the line graph of 𝐻 , and assume that tw(𝑀) ≥ 8. Then there exist a subset 𝑈 ⊆ ∩𝑈 | 𝐸 (𝐻 ) of size 𝑚 := |𝑈 | ≥ tw(𝑀)/4, and an edge profile 𝛼 ∈ R𝐸≥0(𝑀 ) such that, writing 𝜌 (𝐹 ) := |𝐹 𝑚 for all 𝐹 ⊆ 𝐸 (𝐻 ), the induced symmetric edge set function 𝑞𝑀,𝛼 ∈ S(𝐻 ) satisfies 𝑞𝑀,𝛼 (𝐹 ) ≥ 2𝜌 (𝐹 )𝜌 (𝐸 (𝐻 ) \ 𝐹 )

∀𝐹 ⊆ 𝐸 (𝐻 ),

and

log 𝑚 ∀𝑒 ∈ 𝐸 (𝐻 ). 𝑚 In particular, 𝜌 is the uniform probability measure on 𝑈 , and every point of 𝑈 has 𝜌-mass exactly 1/𝑚 ≤ 1/2. 𝛼 (Inc𝑀 (𝑒)) ≤ 𝑐 sup

Proof. By Proposition 5.4, there is a node-well-linked set 𝑈 ⊆ 𝑉 (𝑀) = 𝐸 (𝐻 ) with 𝑚 := |𝑈 | ≥ tw(𝑀)/4. Since tw(𝑀) ≥ 8, we have 𝑚 ≥ 2. Let 𝜌 be the uniform probability measure on 𝐸 (𝐻 ) supported on 𝑈 . By Proposition 5.5, the set 𝑈 is 1-node-cut-linked. Hence by Lemma 5.8 there exists a feasible node-capacitated multicommodity flow routing 𝜗≥

1 𝐶 𝑚 log 𝑚

between every unordered pair in 𝑈2 . Construct the normalized path weighting 𝜔 = 𝜔 𝑓 from this flow as in Definition 5.9, and set 𝛼 to be 𝛼 𝜔 . Then, by Lemma 5.10, log 𝑚 ∀ℎ ∈ 𝐸 (𝐻 ). 𝑚 The balanced cut lower bound follows from Lemma 5.11. Since 𝑚 ≥ 2 and 𝜌 is uniform on 𝑈 , every point of 𝑈 has 𝜌-mass at most 1/2. □ 𝛼 (Inc𝑀 (ℎ)) ≤ 𝑐 sup

Theorem 5.13. There exists a universal constant 𝐶 > 0 such that the following holds. Let 𝐻 be a hypergraph and let 𝑀 := 𝑃 (𝐻 ∗ ). If tw(𝑀) ≥ 8, then there exists an edge profile 𝛼 ∈ R𝐸≥0(𝑀 ) such that 𝑞𝑀,𝛼 ∈ S(𝐻 ),

4 𝔅𝐻 (𝑞𝑀,𝛼 ) ≥ , 9

and

max 𝛼 (Inc𝑀 (𝑒)) ≤ 𝐶

𝑒 ∈𝐸 (𝐻 )

log tw(𝑀) . tw(𝑀)

Proof. Apply Lemma 5.12 to obtain 𝑈 , 𝑚, 𝜌, and 𝛼 with 𝑞𝑀,𝛼 (𝐹 ) ≥ 2𝜌 (𝐹 )𝜌 (𝐸 (𝐻 ) \ 𝐹 ) and

∀𝐹 ⊆ 𝐸 (𝐻 ),

log 𝑚 log tw(𝑀) ≤ 𝑐′ ∀𝑒 ∈ 𝐸 (𝐻 ). 𝑚 tw(𝑀) Now note that every point mass of 𝜌 from the lemma is at most 1/2. It is now sufficient to apply Lemma 5.2 with 𝜙 (𝑥) = 2𝑥 (1 − 𝑥) to directly obtain 𝔅𝐻 (𝑞𝑀,𝛼 ) ≥ 𝜙 (1/3) = 49 . □ 𝛼 (Inc𝑀 (𝑒)) ≤ 𝑐

Cuts and Gauges for Submodular Width

21

Connecting ghw and subw

6

We now apply the machinery of the previous sections by showing how submodular width and ghw are related under various structural conditions. We first present two natural structural conditions under which the submodular gauge for the 𝑞 from Theorem 5.13 is in 𝑂 (log ghw(𝐻 )/ghw(𝐻 )). This then directly yields the inverse lower bound for subw(𝐻 ) through the variational characterisation of subwlift (Theorem 4.7) combined with the transfer from subwlift to subw (Corollary 3.5). As a starting point we recall a result by Lanzinger [21] that states that PTIME and FPT CQ evaluation collapse for degree 2 (assuming 𝑊 [1] ≠ FPT). In a structural sense this implies that for every class of degree 2 hypergraphs H , ghw is bounded if and only if subw is bounded, although the proof in [21] does not produce any concrete bounds on how the measures are related. Here we show how to recover the complexity collapse through our framework, which also yields the first explicit bound relating the two measures in this class. In fact it turns out that the natural proof for the degree 2 case in our framework readily generalises to two (incomparable) significantly more general conditions. The strategy for the results in this section is simple, we demonstrate a general principle for converting edge profiles on the line graph 𝑀 = 𝑃 (𝐻 ∗ ) into functions 𝑏 ∈ 1-Sub(𝐻 ), such that 𝛾𝐻Sub (𝑞𝑀,𝛼 ) is very low. More precisely, we will apply the following principle to make use of Theorem 5.13. To simplfy the presentation, the following considers only hypergraphs 𝐻 where 𝑃 (𝐻 ∗ ) has at least one edge (i.e., there are two hyperedges that have non-empty intersection). Definition 6.1. For a hypergraph 𝐻 and 𝑀 := 𝑃 (𝐻 ∗ ), define its (submodular) gauge-routing ratio 𝛾𝐻Sub (𝑞𝑀,𝛼 ) 𝛼≠0 max𝑒 ∈𝐸 (𝐻 ) 𝛼 (Inc𝑀 (𝑒))

ℜ(𝐻 ) := sup

where the supremum ranges over all nonzero edge profiles 𝛼 : 𝐸 (𝑀) → R ≥0 . The submodular gauge-routing ratio simply measures how efficiently incident load in the line graph can be turned into submodular gauge. Combined with Theorem 5.13, it immediately yields lower bounds on subw(𝐻 ). Lemma 6.2. There exists a universal constant 𝐶 > 0 such that, for every hypergraph 𝐻 with ghw(𝐻 ) ≥ 9, ghw(𝐻 ) 𝐶 subw(𝐻 ) ≥ · . ℜ(𝐻 ) log ghw(𝐻 ) Proof. By Proposition 2.1, ghw(𝐻 ) ≤ tw(𝑃 (𝐻 ∗ ))+1, and therefore tw(𝑃 (𝐻 ∗ )) ≥ ghw(𝐻 )−1 ≥ 8. ∗ Hence Theorem 5.13 provides an edge profile 𝛼 ∈ R𝐸≥0(𝑃 (𝐻 ) ) such that 𝑞 := 𝑞𝑃 (𝐻 ∗ ),𝛼 ∈ S(𝐻 ), and

4 𝔅𝐻 (𝑞) ≥ , 9

𝜏 := max 𝛼 (Inc𝑃 (𝐻 ∗ ) (𝑒)) ≤ 𝐶 0 𝑒 ∈𝐸 (𝐻 )

log tw(𝑃 (𝐻 ∗ )) tw(𝑃 (𝐻 ∗ ))

for some universal constant 𝐶 0 > 0. By definition of ℜ(𝐻 ), 𝛾𝐻Sub (𝑞) ≤ 𝜏 ℜ(𝐻 ) ≤ 𝐶 0 ℜ(𝐻 )

log tw(𝑃 (𝐻 ∗ )) . tw(𝑃 (𝐻 ∗ ))

Therefore, by Theorem 4.7, subwlift (𝐻 ) ≥

𝔅𝐻 (𝑞) 4 tw(𝑃 (𝐻 ∗ )) ≥ · . 𝛾𝐻Sub (𝑞) 9 𝐶 0 ℜ(𝐻 ) log tw(𝑃 (𝐻 ∗ ))

22

Matthias Lanzinger

Since tw(𝑃 (𝐻 ∗ )) ≥ ghw(𝐻 ) − 1, this implies subwlift (𝐻 ) ≥

ghw(𝐻 ) 𝐶1 · ℜ(𝐻 ) log ghw(𝐻 )

for some universal constant 𝐶 1 > 0. Finally, Corollary 3.5 gives subw(𝐻 ) ≥ subwlift (𝐻 ).

□

On a technical level, the way we will bound ℜ(𝐻 ) is by constructing a 𝑏 ∈ 1-Sub(𝐻 ) from every 𝛼. This may raise the question why this technically differs from constructing 𝑏 right away. There are multiple subtle but important reasons. The developments from Section 5 construct technically very useful 𝑞 ∈ S(𝐻 ) for all hypergraphs. We can use this to bound subw in terms of ghw in those cases where this 𝑞 has small gauge (in particular, small ℜ(𝐻 )). Using the tools from Section 5 directly to construct a 𝑏 ∈ 1-Sub(𝐻 ) would require applying them directly under some constraints to the structure of 𝐻 , leading to much higher conceptual complexity. That is, the variational characterisation allows us to separate principles construction of 𝑞, from its application to bounding subw, leading to much simpler and arguably more natural arguments overall. Furthermore, the cut perspective made it much easier to construct our “canonical” 𝑞 ∈ S(𝐻 ), that guarantees a universal lower bound on 𝔅𝐻 . However, this implies high submodular width through Theorem 3.4 only when 𝑞 is a boundary lift of 𝑏 ∈ 1-Sub, a much stricter property than what we use to bound the gauges here. We now discuss two natural but general structural properties that imply bounded ℜ. The proofs are simple but instructive. We defer them to Appendix B. First, we consider the role of what we call the edge excess – the sum of degrees greater than 2 in an edge. That is, degree 2 vertices do not count towards the excess, and the total degree of the rest of the vertices must be low. In a database setting, where degree represents how many joins an attribute is involved in, low edge excess already covers most natural cases. For hypergraphs with maximum degree 2, the edge excess is 0. Definition 6.3. For a hypergraph 𝐻 , define its edge excess as ∑︁ ex(𝐻 ) := max max{deg𝐻 (𝑣) − 2, 0}. 𝑒 ∈𝐸 (𝐻 )

𝑣 ∈𝑒

Proposition 6.4. For every hypergraph 𝐻 , it holds that ℜ(𝐻 ) ≤ ex(𝐻 ) + 1. When we are only interested in the qualitative goal of observing when unbounded ghw implies unbounded subw on a class of hypergraphs, constant edge excess is not essential. Indeed, if a class H satisfies ex(𝐻 ) ∈ 𝑂 ((log ghw(𝐻 ))𝑐 ) for some fixed 𝑐 on all 𝐻 ∈ H , then Proposition 6.4 yields   ghw(𝐻 ) subw(𝐻 ) ∈ Ω . (log ghw(𝐻 ))𝑐+1 In particular, every such class with unbounded ghw also has unbounded subw. We illustrate an example of such a class in Appendix C. The second constraint that generalises maximum degree 2 is of a very different flavour. Rather than controlling the total amount of high-degree overlap, it merely requires that each pairwise intersection contain at least one degree-2 witness. In particular, it places no direct restriction on the rest of the hypergraph, and yet it is already strong enough to produce a strong asymptotic lower bound on subw in terms of ghw. Definition 6.5. We say that 𝐻 has the private intersections property if, for every distinct 𝑥, 𝑦 ∈ 𝐸 (𝐻 ) with 𝑥 ∩ 𝑦 ≠ ∅, there exists 𝑣 𝑥 𝑦 ∈ 𝑥 ∩ 𝑦 with deg𝐻 (𝑣 𝑥 𝑦 ) = 2. Proposition 6.6. Assume that 𝐻 has the private intersection property. Then ℜ(𝐻 ) ≤ 1.

Cuts and Gauges for Submodular Width

23

The private intersection property is in its own sense much more permissive than a global degree bound. A hypergraph may satisfy it while still having vertices of arbitrarily large degree, large pairwise intersections, or highly complicated higher-order overlap (e.g., high VC-dimension). The point is that our realisation argument needs only one degree-2 witness for each line-graph edge 𝑥𝑦, and once such a witness exists, all remaining intersection structure can be ignored. We consider this rather surprising, and given the later complexity consequences it may be worthwhile to study direct algorithmic consequences of this property further in a database context. That is, by combining these bounds with Lemma 6.2 we can observe   ghw(𝐻 ) 1 subw(𝐻 ) ∈ Ω · ex(𝐻 ) + 1 log ghw(𝐻 ) in general. And subw(𝐻 ) ∈ Ω(ghw(𝐻 )/log ghw(𝐻 )) for 𝐻 with private intersections. 6.1

A General Fractional Witness Principle

Abstracting one level, the two previous applications are instances of the same mechanism. For each line-graph edge 𝑥𝑦 ∈ 𝐸 (𝑃 (𝐻 ∗ )), one must assign one unit of witness mass to vertices of the intersection 𝑥 ∩𝑦. The core question then is how much total charge this induces on each hyperedge of 𝐻 . In the private-intersection case this assignment is integral and supported on a single degree 2 vertex, whereas in the bounded-excess case it is distributed over larger intersections. Allowing fractional assignments isolates the common optimisation problem and turns the resulting cost into a linear, hence modular, functional of the line graph. Definition 6.7. Let 𝐻 be a hypergraph, and let 𝑀 := 𝑃 (𝐻 ∗ ). An intersection capacity allocation on 𝐻 is a family 𝑝 of all 𝑝𝑥 𝑦,𝑣 ∈ R ≥0 where 𝑥𝑦 ∈ 𝐸 (𝑀) and 𝑣 ∈ 𝑥 ∩ 𝑦 such that ∑︁ 𝑝𝑥 𝑦,𝑣 = 1 ∀𝑥𝑦 ∈ 𝐸 (𝑀). 𝑣 ∈𝑥∩𝑦

For 𝑒 ∈ 𝐸 (𝐻 ) and 𝑥𝑦 ∈ 𝐸 (𝑀), define 𝑤𝑒 (𝑥𝑦) := 𝑝

∑︁

𝑝𝑥 𝑦,𝑣 .

𝑣 ∈𝑒∩𝑥∩𝑦

For an intersection capacity allocation we now want to measure the maximum fractional load it can induce on any individual hyperedge. We write n ∑︁ o 𝑝 𝜅𝑒 (𝑝) := max 𝑤𝑒 (𝑥𝑦)𝛽𝑥 𝑦 | 𝛽 ∈ R𝐸≥0(𝑀 ) , 𝛽 (Inc𝑀 (ℎ)) ≤ 1 ∀ℎ ∈ 𝐸 (𝐻 ) , 𝑥 𝑦 ∈𝐸 (𝑀 )

and 𝜅 (𝑝) := max𝑒 ∈𝐸 (𝐻 ) 𝜅𝑒 (𝑝). Finally, define 𝜅 (𝐻 ) := min𝑝 𝜅 (𝑝), where the minimum ranges over all intersection capacity allocations 𝑝 on 𝐻 . Lemma 6.8. Let 𝐻 be a hypergraph, let 𝑀 := 𝑃 (𝐻 ∗ ), let 𝛼 ∈ R𝐸≥0(𝑀 ) , and let 𝑝 be an intersection capacity allocation on 𝐻 . Then 𝛾𝐻Sub (𝑞𝑀,𝛼 ) ≤ 𝜅 (𝑝) max𝑒 ∈𝐸 (𝐻 ) 𝛼 (Inc𝑀 (𝑒)). In particular, ℜ(𝐻 ) ≤ 𝜅 (𝐻 ). Proof. Set 𝜏 := maxℎ∈𝐸 (𝐻 ) 𝛼 (Inc𝑀 (ℎ)), and define ∑︁ 𝜇 (𝑣) := 𝛼𝑥 𝑦 𝑝𝑥 𝑦,𝑣 , 𝑥 𝑦 ∈𝐸 (𝑀 ): 𝑣 ∈𝑥∩𝑦

Then 𝑏 is modular, hence also submodular.

𝑏 (𝑋 ) :=

∑︁ 𝑣 ∈𝑋

𝜇 (𝑣).

24

Matthias Lanzinger

We first show that 𝑞𝑀,𝛼 ≤ 𝜆𝑏 . Fix 𝐹 ⊆ 𝐸 (𝐻 ). If 𝑥𝑦 ∈ cut𝑀 (𝐹Í ), then 𝑥 and 𝑦 lie on opposite sides of the cut, so every vertex of 𝑥 ∩ 𝑦 belongs to 𝜕𝐻 (𝐹 ). Since 𝑣 ∈𝑥∩𝑦 𝑝𝑥 𝑦,𝑣 = 1, the full mass 𝛼𝑥 𝑦 contributes to 𝑏 (𝜕𝐻 (𝐹 )). Summing over all 𝑥𝑦 ∈ cut𝑀 (𝐹 ) gives 𝑞𝑀,𝛼 (𝐹 ) ≤ 𝑏 (𝜕𝐻 (𝐹 )) = 𝜆𝑏 (𝐹 ). It remains to bound 𝑏 on hyperedges. Fix 𝑒 ∈ 𝐸 (𝐻 ). Since 𝑒 is the hyperedge whose load we are measuring, we use ℎ for the generic hyperedge in the constraints defining 𝜅𝑒 (𝑝). By rearranging the sums, ∑︁ 𝑝 𝑏 (𝑒) = 𝛼𝑥 𝑦 𝑤𝑒 (𝑥𝑦). 𝑥 𝑦 ∈𝐸 (𝑀 )

If 𝜏 = 0, then 𝛼 = 0, hence 𝑞𝑀,𝛼 = 0, and there is nothing to prove. So assume 𝜏 > 0, and set 𝛽 := 𝛼/𝜏. Then 𝛽 (Inc𝑀 (ℎ)) ≤ 1 for every ℎ ∈ 𝐸 (𝐻 ). Therefore, by the definition of 𝜅𝑒 (𝑝), ∑︁ 𝑝 𝑏 (𝑒) = 𝜏 𝑤𝑒 (𝑥𝑦)𝛽𝑥 𝑦 ≤ 𝜏 𝜅𝑒 (𝑝) ≤ 𝜏 𝜅 (𝑝). 𝑥 𝑦 ∈𝐸 (𝑀 )

Since 𝑒 was arbitrary, we have 𝑏 (ℎ) ≤ 𝜏𝜅 (𝑝) for every ℎ ∈ 𝐸 (𝐻 ). If 𝜏𝜅 (𝑝) = 0, then 𝑏 = 0, and hence again 𝑞𝑀,𝛼 = 0. Otherwise define 1 𝑏b := 𝑏. 𝜏𝜅 (𝑝) Then 𝑏b ∈ 1-Mod(𝐻 ) ⊆ 1-Sub(𝐻 ), which implies 𝑞𝑀,𝛼 ≤ 𝜆𝑏 = 𝜏𝜅 (𝑝) 𝜆𝑏b, and therefore also 𝛾𝐻Sub (𝑞𝑀,𝛼 ) ≤ 𝜏𝜅 (𝑝). Since 𝑝 was arbitrary, taking the infimum over all intersection capacity allocations yields ℜ(𝐻 ) ≤ 𝜅 (𝐻 ). □ Corollary 6.9. There exists a universal constant 𝐶 > 0 such that, for every hypergraph 𝐻 with ghw(𝐻 ) ≥ 9, ghw(𝐻 ) 𝐶 · . subw(𝐻 ) ≥ 𝜅 (𝐻 ) log ghw(𝐻 ) Proof. Immediate from Lemma 6.2 and Lemma 6.8.

□

Note that previous applications can be recovered by choosing specific intersection capacity allocations analogous to the arguments in Section B. Under the private intersection property one has 𝜅 (𝐻 ) ≤ 1, while bounded edge excess gives 𝜅 (𝐻 ) ≤ ex(𝐻 ) + 1. There is a particularly interesting observation to make here that should be explored further. The direct argument for the ex(𝐻 ) + 1 bound proves the gauge is small relative to some coverage function. In the proof a coverage function is the natural choice and it is not clear how to relax this to show the gauge relative to a modular function. In contrast, Lemma 6.8 in fact always shows that Mod (the gauge relative to 𝐾 Mod ) is bounded in terms of 𝜅, as the bound comes from a the gauge 𝛾𝐻,1 1 modular 𝑏. That is, this more general principle implicitly translates our realisability argument for edge excess from one based on submodular functions, to one based on modular functions. Concretely, this implies the same lower bounds already for adaptive width. But on a higher level this hints at the opportunity for deeper insight into the connections between adaptive and submodular width. New insight into this connection might be gained through studying the relationship of submodular and modular gauges for the realisable body. 7

Complexity Consequences

We assume the reader to be familiar with conjunctive queries (CQs). We use the notation and terminology of [2]. In particular, for CQ 𝑞 and database 𝐷, we write 𝑞(𝐷) for the set of answers of 𝑞 over 𝐷. We write BCQ (H ) for the Boolean conjunctive query evaluation problem over hypergraph class H . Namely, given a CQ 𝑞 with 𝐻 (𝑞) ∈ H and a database 𝐷, is 𝑞(𝐷) ≠ ∅? We

Cuts and Gauges for Submodular Width

25

also write p-BCQ (H ) for the typical parameterisation of the problem studied in the context of parameterised complexity, with the same inputs and output as BCQ (H ), and parameter 𝑞. That is, we say p-BCQ (H ) ∈ FPT if there is an 𝑓 (𝑞) poly(𝐷) time algorithm for the problem, where 𝑓 is computable. Proposition 7.1 (Adler et al. [1], Gottlob et al. [11]). Let H be a class of hypergraphs with constantly bounded ghw. Then BCQ (H ) ∈ PTIME. Proposition 7.2 (Marx [23]). Let H be a recursively enumerable class of hypergraphs. Then, assuming ETH, p-BCQ (H ) ∈ FPT if and only if H has constantly bounded subw. We extend hypergraph parameters to classes of hypergraphs in the natural way. That is, for a class H we write 𝑓 (H ) to mean sup𝐻 ∈ H 𝑓 (𝐻 ). Moreover, we write 𝑓 (H ) < ∞ to state that there exists a constant 𝑐 ∈ R ≥0 such that 𝑓 (H ) ≤ 𝑐. We can now formulate our main consequence in terms of computational complexity. Analogous to the bounded rank dichotomy for CQ evaluation by Grohe [13] and the aforementioned degree 2 result [21], we observe a dichotomy where BCQ (H ) is either solvable in polynomial time, or p-BCQ (H ) is not fixed-parameter tractable. Theorem 7.3. Let H be a recursively enumerable class of hypergraphs with bounded submodular gauge-routing ratio, i.e., ℜ(H ) < ∞. Assuming ETH, the following are equivalent: (i) ghw(H ) < ∞. (ii) subw(H ) < ∞. (iii) subwlift (H ) < ∞. (iv) p-BCQ (H ) ∈ FPT. (v) BCQ (H ) ∈ PTIME. Proof. By Corollary 3.5 and Proposition 7.2, (ii) ⇐⇒ (iii) ⇐⇒ (iv). Assuming bounded ℜ, Proposition 2.2 and Lemma 6.2, also (i) is equivalent to those statements. To close the final loop, observe that (i) =⇒ (v) by Proposition 7.1, and (v) =⇒ (iv) trivially. □ Theorem 7.3 should be viewed as a meta-theorem. The previous sections identified several natural sufficient conditions for bounded gauge-routing ratio, including bounded edge excess, exclusive intersection structure, and the more general routing principles from Section 6.1. Taken together, these results clarify how tightly subw and ghw are linked on a broad family of hypergraph classes. So far we have focused our investigations on generalised hypertree width ghw, i.e., 𝜏𝑏 where 𝑏 is the (integral) edge cover number. Relaxing this to the case where 𝑏 is the fractional edge cover number defines the important notion of fractional hypertree width fhw [15], that is known to induce tractable classes for BCQ beyond bounded ghw. It is well-known that subw(𝐻 ) ≤ fhw(𝐻 ) ≤ ghw(𝐻 ). Hence ℜ(H ) < ∞ also implies that ghw(H ) < ∞ iff fhw(H ) < ∞. That is, for the classes investigated here the notions collapse in terms of boundedness. Lower bounds based particularly on fhw are a natural opportunity for future work. We discuss this matter in detail in Section 8. BCQ and p-BCQ are also studied in terms of restrictions by query classes rather than hypergraph classes. This introduces one extra step of complications, as queries might have structurally simple equivalent cores. Our results extend naturally to the setting of query classes by results of Chen et al. [6]; see also [21, Section 4.3] for details. 8 8.1

Conclusion & Outlook Conclusion

We propose a geometric reframing of submodular width. Instead of reasoning directly about tree decompositions for each admissible submodular function, we pass to symmetric edge-set

26

Matthias Lanzinger

functions and study their position inside the realisable submodular body 𝐾1Sub (𝐻 ). Our variational characterisation recasts submodular width as a geometric question about the hypergraph itself. Instead of treating each admissible submodular function separately, one studies the shape of the realisable submodular body and the extent to which symmetric cut functions can be accommodated within it. In this way, a problem originally phrased in terms of decompositions and adversarial submodular functions is recast as a finite-dimensional convex optimisation problem. This geometric reformulation presents us with a new task: one needs a systematic way of producing symmetric cut functions that are sufficiently well distributed to witness large width. We develop such a method by applying classical multicommodity-flow results on the line graph of the studied hypergraph. This yields symmetric cut functions with controlled incident load at each hyperedge. In a further step we show that small incident load also forces small gauge in the realisable body. Our applications show that this mechanism is rather robust and we are able to bound subw in terms of ghw under much looser conditions than previously known. Finally, these structural results have concrete consequences for the complexity of conjunctive query evaluation. In particular, on every recursively enumerable class with bounded gauge-routing ratio, polynomial-time solvability and fixed-parameter tractability coincide under ETH. 8.2

Directions for Future Research

The geometric framework developed in this paper recasts the study of submodular width as a collection of questions about a finite-dimensional convex body. This change in perspective opens up a broader landscape of problems, only a small part of which is explored here. On the more immediate side, the results of Section 3 and Section 4 extend naturally to other width measures in the spirit of adaptive or submodular width, for instance those defined using entropic or polymatroid functions. It is also natural to ask how this geometric viewpoint interacts with data-constraint-aware forms of conjunctive query evaluation, such as those studied in [18, 19]. Among these and many other possibilities, we highlight the following directions for further work. Computing Submodular Width. The geometric viewpoint suggests a new algorithmic approach to computing submodular width of a hypergraph. Historically, deciding or computing submodular width, or finding certificates for low width has been highly challenging. Recently, there has been some progress as Abo Khamis et al. [17] presented a general algorithm for computing the more general 𝜔-subw through finitely many linear programs, but it remains unclear whether this is practical. Rather than searching directly over tree decompositions and adversarial submodular witnesses, one could phrase the problem in terms of optimisation over the realisable body and its gauge. This shifts the difficulty into a finite-dimensional convex setting, where one may hope for separation procedures, approximation algorithms, or certificate systems that are more approachable than the original definition. From this perspective, the point is not only to ask whether submodular width can be computed exactly. More broadly, one can ask whether the variational description and the associated antiblocker duality can be turned into effective optimisation tools. The primal body describes which symmetric cut functions can be realised at a given scale, while the antiblocker offers a dual language for certifying when such realisation is impossible. If these two sides can be made algorithmic, then the geometric viewpoint could provide a practical way of estimating, certifying, and investigating submodular width. Technical Approaches Beyond Section 5. The route through the line graph 𝑃 (𝐻 ∗ ) is only one way of building on the variational characterisation. It is effective because multicommodity flow on the line graph produces balanced cut weightings with small incident load, but this is only one technical option towards identifying relevant cut weightings. In this sense, the line graph should be viewed

Cuts and Gauges for Submodular Width

27

as a particularly convenient first interface between routing and overlap, not as the unique setting in which the geometric method can operate. We believe there is room for several alternative approaches. One may try to construct good 𝑞 ∈ S(𝐻 ) directly from separators in the hypergraph or in the incidence graph, from metric or spectral relaxations, or from higher-order overlap structures that are not visible in the pairwise line graph alone. Another natural direction is to look for mechanisms for constructing symmetric cut functions that already reflect fractional cover structure to relate submodular width also more directly to fhw rather than only to ghw. Polyhedral Structure of the Realisable Submodular Body. For a fixed hypergraph 𝐻 , the set 𝐸 (𝐻 ) 𝐾1Sub (𝐻 ) ⊆ R2≥0 is a finite-dimensional polytope. The current framework shows that lower bounds on submodular width are governed by membership and scaling questions for a polyhedral body, but the geometry is still encoded implicitly through submodular witnesses. An explicit description in cut coordinates could turn existential representation into concrete optimisation, provide recognisable certificates of membership and non-membership, and make it possible to study approximation algorithms for the gauge in a more direct way. From the hypergraph point of view, the central issue is to relate the intersection structure of 𝐻 to the polyhedral structure of 𝐾1Sub (𝐻 ). Which overlap configurations force valid inequalities, and when do these become facet-defining? Which vertices of 𝐾1Sub (𝐻 ) can be described combinatorially? How does the polytope transform under natural operations on 𝐻 , such as gluing along separators, subdividing intersections, or adjoining vertices with controlled incidence? Clarifying these questions would make the geometry more explicit, and could help connect it more closely to the algorithmic theory of conjunctive query evaluation. Sparse Representations of Near-Optimal Symmetric Cut Functions. A related geometric question concerns the complexity of representing the symmetric cut functions that are relevant to submodular width. Since 𝐾1Sub (𝐻 ) ∩ S(𝐻 ) is a polytope, every element of this set can be written as a convex combination of finitely many extreme points. The ambient-dimensional bound on the complexity of this combination is immediate, but is likely to be far from sharp. This raises the question of whether symmetric cut functions that are near-optimal for subwlift (𝐻 ) always admit sparse representations. In our setting, such a result would have a concrete meaning. It would say that lower bounds relevant to submodular width can be witnessed by combining only a small number of basic realisable cut functions, rather than by a highly distributed convex combination. This would be particularly interesting if the required support size could be bounded in terms of structural parameters of 𝐻 , such as rank, intersection behaviour, or VC-dimension. This question also has a natural algorithmic interpretation. If near-optimal witnesses always admitted succinct decompositions, then one could hope to search for strong lower-bound certificates in a much smaller space, or to design hybrid evaluation procedures in which the more expensive submodular-width machinery is only invoked on parts of the query that genuinely require it. Fractional Witness Assignments as Structural Parameters. The parameter 𝜅 (𝐻 ) from Section 6.1 already subsumes the two main applications of this paper: private intersections give 𝜅 (𝐻 ) ≤ 1, while bounded edge excess gives 𝜅 (𝐻 ) ≤ ex(𝐻 ) + 1. In that sense, 𝜅 (𝐻 ) is not merely an auxiliary quantity, but a general structural parameter extracted from the realisability argument itself. What is still missing is a theory explaining when 𝜅 (𝐻 ) is small and how sharply it captures the gauge-routing ratio. For fixed 𝑝 and 𝑒, the quantity 𝜅𝑒 (𝑝) is a linear-programming optimum, and LP duality gives it the flavour of a weighted fractional cover problem on the line graph 𝑃 (𝐻 ∗ ). This

28

Matthias Lanzinger

suggests that 𝜅 (𝐻 ) should admit a more transparent combinatorial interpretation than is currently visible from the definition. References [1] Isolde Adler, Georg Gottlob, and Martin Grohe. 2007. Hypertree width and related hypergraph invariants. Eur. J. Comb. 28, 8 (2007), 2167–2181. doi:10.1016/j.ejc.2007.04.013 [2] Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris. 2022. Database Theory. Open source at https://github.com/pdm-book/community. [3] Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 319–330. doi:10.1109/FOCS.2017.37 [4] Chandra Chekuri and Julia Chuzhoy. 2013. Large-treewidth graph decompositions and applications. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing Conference, STOC 2013. ACM, 291–300. doi:10.1145/2488608. 2488645 [5] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. 2005. Multicommodity flow, well-linked terminals, and routing problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computin, STOC 2005. ACM, 183–192. doi:10.1145/1060590.1060618 [6] Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler. 2020. Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. ijcai.org, 1726–1733. doi:10.24963/IJCAI.2020/239 [7] Imre Csiszár, János Körner, László Lovász, Katalin Marton, and Gábor Simonyi. 1990. Entropy splitting for antiblocking corners and perfect graphs. Comb. 10, 1 (1990), 27–40. doi:10.1007/BF02122693 [8] Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. 2008. Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38, 2 (2008), 629–657. doi:10.1137/05064299X [9] Delbert R Fulkerson. 1972. Anti-blocking polyhedra. Journal of Combinatorial Theory, Series B 12, 1 (1972), 50–71. [10] Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. 2021. Complexity Analysis of Generalized and Fractional Hypertree Decompositions. J. ACM 68, 5 (2021), 38:1–38:50. doi:10.1145/3457374 [11] Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2002. Hypertree Decompositions and Tractable Queries. J. Comput. Syst. Sci. 64, 3 (2002), 579–627. doi:10.1006/jcss.2001.1809 [12] Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. 2009. Generalized hypertree decompositions: NP-hardness and tractable variants. J. ACM 56, 6 (2009), 30:1–30:32. doi:10.1145/1568318.1568320 [13] Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1 (2007), 1:1–1:24. doi:10.1145/1206035.1206036 [14] Martin Grohe. 2016. Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles). CoRR abs/1605.06704 (2016). arXiv:1605.06704 http://arxiv.org/abs/1605.06704 [15] Martin Grohe and Dániel Marx. 2006. Constraint solving via fractional edge covers. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006. ACM Press, 289–298. http://dl.acm.org/citation. cfm?id=1109557.1109590 [16] Mahmoud Abo Khamis and Hubie Chen. 2026. Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time. CoRR abs/2603.13624 (2026). doi:10.48550/ARXIV.2603.13624 arXiv:2603.13624 [17] Mahmoud Abo Khamis, Xiao Hu, and Dan Suciu. 2025. Fast Matrix Multiplication meets the Submodular Width. Proc. ACM Manag. Data 3, 2 (2025), 98:1–98:26. doi:10.1145/3725235 [18] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2017. What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017. ACM, 429–444. doi:10.1145/3034786.3056105 [19] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2025. PANDA: Query Evaluation in Submodular Width. TheoretiCS 4, Article 12 (2025). doi:10.46298/THEORETICS.25.12 [20] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2025. PANDAExpress: a Simpler and Faster PANDA Algorithm. CoRR abs/2512.10217 (2025). doi:10.48550/ARXIV.2512.10217 arXiv:2512.10217 [21] Matthias Lanzinger. 2022. The Complexity of Conjunctive Queries with Degree 2. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022. ACM, 91–102. doi:10.1145/3517804. 3524152 [22] Dániel Marx. 2011. Tractable Structures for Constraint Satisfaction with Truth Tables. Theory Comput. Syst. 48, 3 (2011), 444–464. doi:10.1007/S00224-009-9248-9 [23] Dániel Marx. 2013. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. J. ACM 60, 6 (2013), 42:1–42:51. doi:10.1145/2535926

Cuts and Gauges for Submodular Width

29

[24] Karl Menger. 1927. Zur allgemeinen kurventheorie. Fundamenta mathematicae 10, 1 (1927), 96–115. [25] Sang-il Oum and Paul D. Seymour. 2006. Approximating clique-width and branch-width. J. Comb. Theory B 96, 4 (2006), 514–528. doi:10.1016/J.JCTB.2005.10.006 [26] B. A. Reed. 1997. Tree Width and Tangles: A New Connectivity Measure and Some Applications. In Surveys in Combinatorics, 1997, R. A. Bailey (Ed.). London Mathematical Society Lecture Note Series, Vol. 241. Cambridge University Press, 87–162. doi:10.1017/CBO9780511662119.006 [27] R Tyrrell Rockafellar. 1997. Convex analysis. Vol. 28. Princeton university press. [28] Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture. J. ACM 67, 5 (2020), 30:1–30:78. doi:10.1145/3402029

A

A Direct Lifted Submodular Width Lower Bound

We demonstrate a simple mechanism for constructing symmetric edge-set profiles with large cut value and small submodular gauge. Lemma A.1 (Orthogonal Partitions Lemma). Let 𝐻 be a hypergraph, and let A = {𝐴𝑖 | 𝑖 ∈ 𝐼 },

B = {𝐵 𝑗 | 𝑗 ∈ 𝐽 }

be two families of edges of 𝐻 , each of which is a partition of 𝑉 (𝐻 ). Let 𝜇 be a probability measure on 𝑉 (𝐻 ) such that 𝜇 (𝐴𝑖 ∩ 𝐵 𝑗 ) = 𝜇 (𝐴𝑖 )𝜇 (𝐵 𝑗 ) for all 𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽 . Set 𝜃 := max𝑒 ∈𝐸 (𝐻 ) 𝜇 (𝑒), and assume that 𝜇 (𝐴𝑖 ) ≤ 21 for all 𝑖 ∈ 𝐼 . Then subw(𝐻 ) ≥ 3𝜃1 . Proof. Set 𝑏 (𝑋 ) := 𝜇 (𝑋 )/𝜃 for 𝑋 ⊆ 𝑉 (𝐻 ). Since 𝑏 is modular and 𝑏 (𝑋 ) ≤ 1 whenever 𝑋 ⊆ 𝑒 ∈ 𝐸 (𝐻 ), we have 𝑏 ∈ 1-Mod(𝐻 ) ⊆ 1-Sub(𝐻 ). Let 𝑞 := 𝜆𝑏 , so 𝑞(𝐹 ) = 𝜇 (𝜕𝐻 (𝐹 ))/𝜃 for every 𝐹 ⊆ 𝐸 (𝐻 ). Define a probability measure 𝜌 on 𝐸 (𝐻 ) by ( 𝜇 (𝑒), 𝑒 ∈ A, 𝜌 (𝑒) := 0, 𝑒 ∉ A. Since A is a partition of 𝑉 (𝐻 ), 𝜌 is a probability measure on 𝐸 (𝐻 ), and 𝜌 (𝑒) ≤ 12 for every 𝑒 ∈ 𝐸 (𝐻 ). Fix 𝐹 ⊆ 𝐸 (𝐻 ), and set Ø Ø 𝐴𝐹 := (A ∩ 𝐹 ), 𝐵 𝐹 := (B ∩ 𝐹 ). If 𝑥 ∈ 𝐴𝐹 △𝐵 𝐹 (△ being the symmetric set difference), then one of the two partition-edges containing 𝑥 lies in 𝐹 and the other in 𝐸 (𝐻 ) \ 𝐹 . Thus 𝑥 ∈ 𝜕𝐻 (𝐹 ), and hence 𝜇 (𝜕𝐻 (𝐹 )) ≥ 𝜇 (𝐴𝐹 △𝐵 𝐹 ). Because A and B are partitions and 𝜇 (𝐴𝑖 ∩ 𝐵 𝑗 ) = 𝜇 (𝐴𝑖 )𝜇 (𝐵 𝑗 ) for all 𝑖, 𝑗, the events 𝑥 ∈ 𝐴𝐹 and 𝑥 ∈ 𝐵 𝐹 are independent under 𝜇. Moreover, 𝜇 (𝐴𝐹 ) = 𝜌 (𝐹 ) and we have 𝜇 (𝐴𝐹 △𝐵 𝐹 ) = 𝜇 (𝐴𝐹 ) + 𝜇 (𝐵 𝐹 ) − 2𝜇 (𝐴𝐹 )𝜇 (𝐵 𝐹 ) = 𝜌 (𝐹 ) + 𝜇 (𝐵 𝐹 ) (1 − 2𝜌 (𝐹 )). Therefore, whenever 𝜌 (𝐹 ) ≤ 12 , we also have 𝜇 (𝜕𝐻 (𝐹 )) ≥ 𝜌 (𝐹 ). By symmetry of 𝑞 it follows that

1 min{𝜌 (𝐹 ), 𝜌 (𝐸 (𝐻 ) \ 𝐹 )} ∀𝐹 ⊆ 𝐸 (𝐻 ). 𝜃 Applying Lemma 5.2 with 𝜙 (𝑥) = 𝑥/𝜃 yields 𝔅𝐻 (𝑞) ≥ 1/(3𝜃 ). Since 𝑞 = 𝜆𝑏 with 𝑏 ∈ 1-Sub(𝐻 ), we get subwlift (𝐻 ) ≥ 𝔅𝐻 (𝑞) ≥ 1/(3𝜃 ). Finally, by Corollary 3.5 also subw(𝐻 ) ≥ subwlift (𝐻 ). □ 𝑞(𝐹 ) ≥

A simple example is the row/column hypergraph of an 𝑚×𝑛 grid. Its vertex set is [𝑚] × [𝑛], and its hyperedges are the rows 𝑅𝑖 = {(𝑖, 𝑗) | 𝑗 ∈ [𝑛]} for 𝑖 ∈ [𝑚], and the columns 𝐶 𝑗 = {(𝑖, 𝑗) | 𝑖 ∈ [𝑚]} for 𝑗 ∈ [𝑛]. Taking A = {𝑅𝑖 | 𝑖 ∈ [𝑚]} and B = {𝐶 𝑗 | 𝑗 ∈ [𝑛]}, we obtain two partitions of the vertex set. If 𝜇 is the uniform measure on [𝑚] × [𝑛], then 1 1 1 𝜇 (𝑅𝑖 ) = , 𝜇 (𝐶 𝑗 ) = , 𝜇 (𝑅𝑖 ∩ 𝐶 𝑗 ) = = 𝜇 (𝑅𝑖 )𝜇 (𝐶 𝑗 ), 𝑚 𝑛 𝑚𝑛

30

Matthias Lanzinger

so the two partitions are orthogonal in the sense of Lemma A.1. Moreover, n 1 1o 1 max 𝜇 (𝑒) = max , = , 𝑚 𝑛 min{𝑚, 𝑛} 𝑒 ∈𝐸 (𝐻 ) and if 𝑚, 𝑛 ≥ 2, then in particular each row has measure at most 1/2. Thus Lemma A.1 applies and yields min{𝑚, 𝑛} subw(𝐻 ) ≥ . 3 Somewhat surprisingly, Lemma A.1 also tells us that the same lower bound holds if we add arbitrary additional hyperedges on the same vertex set, as long as they all have rank at most max{𝑚, 𝑛}. B

Additional Details for Section 6

We give individual proofs for the bounds on ℜ in terms of excess and private edge intersections. While both cases are covered by the more general argument in Section 6.1 we believe the more specific arguments here can be instructive. Both proofs apply the following principle. Lemma B.1. Let 𝐻 be a hypergraph, let 𝑀 := 𝑃 (𝐻 ∗ ), and let 𝛼 ∈ R𝐸≥0(𝑀 ) . For each edge 𝑥𝑦 ∈ 𝐸 (𝑀), let 𝐴𝑥 𝑦 ⊆ 𝑥 ∩ 𝑦 be nonempty. Define ∑︁ 𝐿𝐴 (𝛼) := max 𝛼𝑥 𝑦 . 𝑒 ∈𝐸 (𝐻 )

𝑥 𝑦 ∈𝐸 (𝑀 ) 𝐴𝑥 𝑦 ∩𝑒≠∅

Then 𝛾𝐻Sub (𝑞𝑀,𝛼 ) ≤ 𝐿𝐴 (𝛼). Proof. Our goal is to show that for every 𝛼, there is a 𝑏 ∈ Sub(𝐻 ) with 𝑞𝑀,𝛼 ≤ 𝜆𝑏 and 𝜆𝑏 ∈ 𝐿𝐴 (𝛼) · 𝐾1Sub . To this end, define ∑︁ 𝑏 (𝑋 ) := 𝛼𝑥 𝑦 1[𝐴𝑥 𝑦 ∩ 𝑋 ≠ ∅] ∀𝑋 ⊆ 𝑉 (𝐻 ) 𝑥 𝑦 ∈𝐸 (𝑀 )

where 1[𝜑] is 1 if 𝜑 is true, and 0 otherwise. This is a coverage function, hence 𝑏 ∈ Sub(𝐻 ). Fix 𝐹 ⊆ 𝐸 (𝐻 ). If 𝑥𝑦 ∈ cut𝑀 (𝐹 ), then 𝑥 and 𝑦 lie on opposite sides of the cut, so every vertex of 𝑥 ∩ 𝑦, and therefore every vertex of 𝐴𝑥 𝑦 , belongs to 𝜕𝐻 (𝐹 ). Hence ∑︁ 𝑞𝑀,𝛼 (𝐹 ) = 𝛼𝑥 𝑦 ≤ 𝑏 (𝜕𝐻 (𝐹 )) = 𝜆𝑏 (𝐹 ). 𝑥 𝑦 ∈cut𝑀 (𝐹 )

What is left to show is that 𝜆𝑏 ∈ 𝐿𝐴 (𝛼) ·𝐾1Sub . Towards this claim, observe that for every 𝑒 ∈ 𝐸 (𝐻 ), ∑︁ ∑︁ 𝑏 (𝑒) = 𝛼𝑥 𝑦 1[𝐴𝑥 𝑦 ∩ 𝑒 ≠ ∅] = 𝛼𝑥 𝑦 ≤ 𝐿𝐴 (𝛼). 𝑥 𝑦 ∈𝐸 (𝑀 )

𝑥 𝑦 ∈𝐸 (𝑀 ) 𝐴𝑥 𝑦 ∩𝑒≠∅

If 𝐿𝐴 (𝛼) = 0, then 𝑞𝑀,𝛼 = 0 and there is nothing to prove. Otherwise, 𝑏˜ := 𝐿𝐴 (𝛼) −1𝑏 lies in 1-Sub(𝐻 ), and 𝑞𝑀,𝛼 ≤ 𝜆𝑏 = 𝐿𝐴 (𝛼)𝜆𝑏˜ . Thus 𝑞𝑀,𝛼 ∈ 𝐿𝐴 (𝛼) 𝐾1Sub (𝐻 ), which means 𝛾𝐻Sub (𝑞𝑀,𝛼 ) ≤ 𝐿𝐴 (𝛼). □ Proposition B.2. Assume that 𝐻 has the private intersections property. Let 𝑀 := 𝑃 (𝐻 ∗ ), and let 𝛼 ∈ R𝐸≥0(𝑀 ) . Then 𝛾𝐻Sub (𝑞𝑀,𝛼 ) ≤ max𝑒 ∈𝐸 (𝐻 ) 𝛼 (Inc𝑀 (𝑒)).

Cuts and Gauges for Submodular Width

31

Proof. For each edge 𝑥𝑦 ∈ 𝐸 (𝑀), fix a witness vertex 𝑣 𝑥 𝑦 ∈ 𝑥 ∩ 𝑦 with deg𝐻 (𝑣 𝑥 𝑦 ) = 2, and set 𝐴𝑥 𝑦 := {𝑣 𝑥 𝑦 }. Set 𝜏 := max𝑒 ∈𝐸 (𝐻 ) 𝛼 (Inc𝑀 (𝑒)). Our goal will be to show that 𝐿𝐴 (𝛼) ≤ 𝜏 — in the sense of Lemma B.1 — for these 𝐴𝑥 𝑦 . Fix 𝑒 ∈ 𝐸 (𝐻 ). We want to understand which terms can contribute to the load at 𝑒, that is, for which edges 𝑥𝑦 ∈ 𝐸 (𝑀) we have 𝐴𝑥 𝑦 ∩ 𝑒 ≠ ∅. Since 𝐴𝑥 𝑦 = {𝑣 𝑥 𝑦 }, this simply means that the witness vertex 𝑣 𝑥 𝑦 lies in 𝑒. Now 𝑣 𝑥 𝑦 was chosen from 𝑥 ∩ 𝑦, so it already lies in the two hyperedges 𝑥 and 𝑦. Moreover, by assumption deg𝐻 (𝑣 𝑥 𝑦 ) = 2, so these are the only two hyperedges of 𝐻 containing 𝑣 𝑥 𝑦 . Therefore, if 𝑣 𝑥 𝑦 ∈ 𝑒, then necessarily 𝑒 = 𝑥 or 𝑒 = 𝑦. In other words, a witness vertex can only be seen by the two hyperedges that gave rise to it. Hence every term counted in ∑︁ 𝛼𝑥 𝑦 𝑥 𝑦 ∈𝐸 (𝑀 ) 𝐴𝑥 𝑦 ∩𝑒≠∅

comes from an edge 𝑥𝑦 of the line graph 𝑀 that is incident with 𝑒. It follows that ∑︁ 𝛼𝑥 𝑦 ≤ 𝛼 (Inc𝑀 (𝑒)) ≤ 𝜏 . 𝑥 𝑦 ∈𝐸 (𝑀 ) 𝐴𝑥 𝑦 ∩𝑒≠∅

Therefore 𝐿𝐴 (𝛼) ≤ 𝜏, and the claim follows from Lemma B.1.

□

Proposition B.3. Let 𝐻 be a hypergraph, let 𝑀 := 𝑃 (𝐻 ∗ ), and let 𝛼 ∈ R𝐸≥0(𝑀 ) . Then 𝛾𝐻Sub (𝑞𝑀,𝛼 ) ≤ (ex(𝐻 ) + 1) max 𝛼 (Inc𝑀 (𝑒)). 𝑒 ∈𝐸 (𝐻 )

Proof. Our goal will be to apply Lemma B.1 with 𝐴𝑥 𝑦 := 𝑥 ∩ 𝑦 for all edges 𝑥𝑦 ∈ 𝐸 (𝑀). Set 𝜏 := max𝑒 ∈𝐸 (𝐻 ) 𝛼 (Inc𝑀 (𝑒)). We will show that 𝐿𝐴 (𝛼) ≤ (ex(𝐻 ) + 1)𝜏 in the sense of Lemma B.1. Fix an 𝑒 ∈ 𝐸 (𝐻 ), write ∑︁ 𝐿𝑒 := 𝛼𝑥 𝑦 . 𝑥 𝑦 ∈𝐸 (𝑀 ) (𝑥∩𝑦)∩𝑒≠∅

Observe that the edges of the line graph incident with 𝑒, i.e., Inc𝑀 (𝑒) contribute at most 𝛼 (Inc𝑀 (𝑒)) ≤ 𝜏. For the remaining edges of the line graph, namely any 𝑥𝑦 ∈ 𝐸 (𝑀) \ Inc𝑀 (𝑒), if (𝑥 ∩ 𝑦) ∩ 𝑒 ≠ ∅, then there exists a vertex 𝑣 ∈ 𝑉 (𝐻 ) such that 𝑣 ∈ 𝑒 ∩ 𝑥 ∩ 𝑦. Define 𝑆 𝑣 := {ℎ ∈ 𝐸 (𝐻 ) \ {𝑒} | 𝑣 ∈ ℎ}. Then 𝑥, 𝑦 ∈ 𝑆 𝑣 , so 𝑥𝑦 ∈ 𝐸 (𝑀 [𝑆 𝑣 ]). Hence ∑︁ ∑︁ 𝐿𝑒 ≤ 𝜏 + 𝛼𝑥 𝑦 . (∗) 𝑣 ∈𝑒 𝑥 𝑦 ∈𝐸 (𝑀 [𝑆 𝑣 ] )

If deg𝐻 (𝑣) ≤ 2, then |𝑆 𝑣 | ≤ 1, so 𝐸 (𝑀 [𝑆 𝑣 ]) = ∅. That is, there is no 𝑥𝑦 ∈ 𝐸 (𝑀) \ Inc𝑀 (𝑒) with 𝑣 ∈ 𝑒 ∩ 𝑥 ∩ 𝑦. Alternatively, since 𝑒, 𝑥, 𝑦 are distinct, 𝑣 in their intersection would imply that 𝑣 has degree 3. Thus, only vertices with degree at least 3 contribute to the sum in (∗). Suppose that deg𝐻 (𝑣) ≥ 3, then by standard double counting ∑︁ ∑︁ 2 𝛼𝑥 𝑦 ≤ 𝛼 (Inc𝑀 (ℎ)) ≤ |𝑆 𝑣 |𝜏 = (deg𝐻 (𝑣) − 1)𝜏 . 𝑥 𝑦 ∈𝐸 (𝑀 [𝑆 𝑣 ] )

ℎ∈𝑆 𝑣

32

Matthias Lanzinger

𝑀 [𝑆 𝑣 ]

𝐻

𝛼𝑒 𝑓 𝑒

𝑓

𝛼𝑒𝑔

𝛼𝑓 𝑔

𝑒 𝑀 [𝑆 𝑣 ]

𝑓 𝑣

𝑔 𝑔 For every 𝑥𝑦 ∈ 𝐸 (𝑀 [𝑆 𝑣 ]), one has 𝑥 ∩ 𝑦 = {𝑣 }, hence 𝐴𝑥 𝑦 = 𝑥 ∩ 𝑦 = {𝑣 }.

𝑆 𝑣 = {𝑒, 𝑓 , 𝑔}

Fig. 1. Illustration for the bounded-excess proof for a vertex 𝑣 of degree 3. In the bound of 𝐿𝑒 , 𝛼𝑒 𝑓 + 𝛼𝑒𝑔 is bounded by 𝛼 (Inc𝑀 (𝑒)), whereas the dashed edge 𝑓 𝑔 also has 𝐴 𝑓 𝑔 ∩ 𝑒 ≠ ∅ and thus also additionally affects the constructed submodular witness in Lemma B.1.

Dividing by 2, we obtain ∑︁

𝛼𝑥 𝑦 ≤ 𝜏

𝑥 𝑦 ∈𝐸 (𝑀 [𝑆 𝑣 ] )

deg𝐻 (𝑣) − 1 ≤ 𝜏 max{deg𝐻 (𝑣) − 2, 0}. 2

Then combining with (∗) from above we get the final inequality, ∑︁ 𝐿𝑒 ≤ 𝜏 + 𝜏 max{deg𝐻 (𝑣) − 2, 0} ≤ (ex(𝐻 ) + 1)𝜏 . 𝑣 ∈𝑒

Taking the maximum over 𝑒 gives 𝐿𝐴 (𝛼) ≤ (ex(𝐻 ) +1)𝜏, and the claim follows from Lemma B.1. □ C

A Natural Family with Logarithmic Edge Excess

We present a natural family of hypergraphs with edge excess 𝑂 (log ghw), illustrating that even superconstant edge excess suffices to obtain a strong lower bound on subw in terms of ghw. For 𝑟 ≥ 2, let 𝑄𝑟 be the 𝑟 -dimensional cube on vertex set (F2 )𝑟 . We define a hypergraph 𝐻𝑟 as follows. (1) The vertices of 𝐻𝑟 are the edges of 𝑄𝑟 . (2) For each cube vertex 𝑥 ∈ (F2 )𝑟 , we add the star 𝑆𝑥 := {𝑓 ∈ 𝐸 (𝑄𝑟 ) | 𝑥 ∈ 𝑓 }. (3) For each 𝑖 ∈ {2, . . . , 𝑟 } and each 𝑥 ∈ (F2 )𝑟 with 𝑥 1 = 𝑥𝑖 = 0, we add the square
𝐶𝑥,𝑖 := 𝐸 𝑄𝑟 [{𝑥, 𝑥 + 𝑒 1, 𝑥 + 𝑒𝑖 , 𝑥 + 𝑒 1 + 𝑒𝑖 }] . So 𝐻𝑟 has one hyperedge for every star of the cube, and one hyperedge for every 2-dimensional face in the directions (𝑒 1, 𝑒𝑖 ). We use the following terminology of Adler, Gottlob, and Grohe [1]. For a hypergraph 𝐻 , a connected set 𝐶 ⊆ 𝑉 (𝐻 ), and a set 𝑀 ⊆ 𝐸 (𝐻 ), we say that 𝐶 is 𝑀-big if |𝑀 | . 2 For 𝑘 ≥ 0, a set 𝑀 ⊆ 𝐸 (𝐻 ) is 𝑘-hyperlinked if for every 𝑆 ⊆ 𝐸 (𝐻 ) with |𝑆 | < 𝑘, the hypergraph Ø Ø   𝐻\ 𝑆 := 𝐻 𝑉 (𝐻 ) \ 𝑒 {𝑒 ∈ 𝑀 | 𝑒 ∩ 𝐶 ≠ ∅} >

𝑒 ∈𝑆

Cuts and Gauges for Submodular Width

33

has an 𝑀-big connected component. The hyperlinkedness hlink(𝐻 ) is the largest 𝑘 such that 𝐻 contains a 𝑘-hyperlinked set. It was shown in [1] that always hlink(𝐻 ) ≤ ghw(𝐻 ). Proposition C.1. For every 𝑟 ≥ 4, ex(𝐻𝑟 ) ≤ 2𝑟

and

 𝑟 2 . ghw(𝐻𝑟 ) ∈ Ω 𝑟

Hence ex(𝐻𝑟 ) = 𝑂 (log ghw(𝐻𝑟 )), and therefore subw(𝐻𝑟 ) ≥ 𝐶

ghw(𝐻𝑟 ) log2 ghw(𝐻𝑟 )

for all sufficiently large 𝑟 . Proof. We first compute the edge excess. A cube edge in direction 𝑒 1 lies in its two endpoint stars and in one square of type (𝑒 1, 𝑒𝑖 ) for each 𝑖 = 2, . . . , 𝑟 , so its degree in 𝐻𝑟 is 𝑟 + 1. A cube edge in direction 𝑒𝑖 with 𝑖 ≥ 2 lies in its two endpoint stars and in exactly one square, so its degree is 3. Therefore, for every 𝑥 ∈ (F2 )𝑟 , ∑︁ max{deg𝐻𝑟 (𝑓 ) − 2, 0} = (𝑟 + 1 − 2) + (𝑟 − 1) (3 − 2) = 2𝑟 − 2, 𝑓 ∈𝑆𝑥

and for every square 𝐶𝑥,𝑖 , ∑︁ max{deg𝐻𝑟 (𝑓 ) − 2, 0} = 2(𝑟 + 1 − 2) + 2(3 − 2) = 2𝑟 . 𝑓 ∈𝐶𝑥,𝑖

Hence ex(𝐻𝑟 ) ≤ 2𝑟 . 𝑟 𝑟 We move  𝑟 −2on to the lower bound on ghw(𝐻𝑟 ). Let 𝑀 := {𝑆𝑥 | 𝑥 ∈ (F2 ) },(so |𝑀 | = 2 ), and let 𝑘 := 2 /𝑟 . We claim that 𝑀 is 𝑘-hyperlinked. Since hlink(𝐻𝑟 ) ≤ ghw(𝐻𝑟 ), this will imply ghw(𝐻𝑟 ) ≥ 𝑘. Fix 𝑆 ⊆ 𝐸 (𝐻𝑟 ) with |𝑆 | < 𝑘. Recall that the vertices of 𝐻𝑟 are the cube edges of 𝑄𝑟 . Thus Ð 𝑆 ⊆ 𝑉 (𝐻𝑟 ) = 𝐸 (𝑄𝑟 ) is exactly the set of cube edges that lie in one of the selected hyperedges of 𝑆. Since every hyperedge of 𝐻𝑟 has size at most 𝑟 (stars have size 𝑟 , squares have size 4), we have Ø ∑︁ 𝑆 ≤ |ℎ| ≤ 𝑟 |𝑆 | < 𝑘𝑟 ≤ 2𝑟 −2 . ℎ∈𝑆

Equivalently, fewer than 2𝑟 −2 cube edges are deleted. Ð Let 𝐺 be the spanning subgraph of 𝑄𝑟 whose edge set is 𝐸 (𝐺) = 𝐸 (𝑄𝑟 ) \ 𝑆. Claim 1. 𝐺 has a connected component 𝑈 with |𝑈 | > 2𝑟 −1 . Proof of Claim 1. Suppose not. Then every connected component of 𝐺 has size at most 2𝑟 −1 . Choose a union 𝑋 of connected components of 𝐺 with 2𝑟 −2 ≤ |𝑋 | ≤ 2𝑟 −1 : either one component already has size in this range, or all components have size less than 2𝑟 −2 , in which case such an 𝑋 can be built greedily. Because 𝑋 is a union of connected components, every cube edge in 𝛿𝑄𝑟 (𝑋 ) was deleted. Hence |𝛿𝑄𝑟 (𝑋 )| < 2𝑟 −2 . On the other hand, the edge-isoperimetric inequality for the cube gives  𝑟  2 ≥ 2𝑟 −2, |𝛿𝑄𝑟 (𝑋 )| ≥ |𝑋 | log2 |𝑋 | a contradiction. Ð Claim 2. 𝐻𝑟 \ 𝑆 has a connected component 𝐶 that meets every star 𝑆𝑥 with 𝑥 ∈ 𝑈 .

▲

34

Matthias Lanzinger

Proof of Claim 2. Let 𝑊 be the set of cube edges of 𝐺 with both endpoints in 𝑈 . Because 𝑈 is a connected component of 𝐺 and |𝑈 | > 2𝑟 −1 , the graph 𝐺 [𝑈 ] is nontrivial, so every 𝑥 ∈ 𝑈 is incident with some edge of 𝑊 . In particular, 𝑆𝑥 ∉ 𝑆 for every 𝑥 ∈ 𝑈 . Ð We claim that 𝑊 lies in a single connected component of 𝐻𝑟 \ 𝑆. Indeed, let 𝑒, 𝑓 ∈ 𝑊 . Since 𝐺 [𝑈 ] is connected, there is a sequence of cube edges 𝑒 = 𝑒 0 , 𝑒 1 , . . . , 𝑒𝑡 = 𝑓 in 𝑊 such that consecutive edges 𝑒𝑖 −1, 𝑒𝑖 share a cube vertex 𝑥𝑖 ∈ 𝑈 . Then Ð both 𝑒𝑖 −1 and 𝑒𝑖 belong to the star 𝑆𝑥𝑖 , and since 𝑆𝑥𝑖 ∉ 𝑆, the hyperedge 𝑆 survives in 𝐻 \ 𝑆. Hence 𝑒𝑖 −1 and 𝑒𝑖 are 𝑥𝑖 𝑟 Ð adjacent inÐthe primal graph of 𝐻𝑟 \ 𝑆. Therefore all edges in 𝑊 lie in one connected component 𝐶 of 𝐻𝑟 \ 𝑆. Finally, for each 𝑥 ∈ 𝑈 , some edge of 𝑊 is incident with 𝑥, so that edge belongs to 𝐶 ∩ 𝑆𝑥 . Thus 𝐶 meets every star 𝑆𝑥 with 𝑥 ∈ 𝑈 . ▲ ByÐClaim 1, we have |𝑈 | > 2𝑟 −1 = |𝑀 |/2. By Claim 2, there is a connected component 𝐶 of 𝐻𝑟 \ 𝑆 meeting every star 𝑆𝑥 with 𝑥 ∈ 𝑈 . Since the stars 𝑆𝑥 are pairwise distinct, 𝐶 meets more than half of the hyperedges in 𝑀. Hence 𝐶 is 𝑀-big. Ð We have proved that for every 𝑆 ⊆ 𝐸 (𝐻𝑟 ) with |𝑆 | < 𝑘, the hypergraph 𝐻𝑟 \ 𝑆 has an 𝑀-big connected component. Therefore 𝑀 is 𝑘-hyperlinked, so hlink(𝐻𝑟 ) ≥ 𝑘 and therefore  𝑟 −2   𝑟 2 2 ghw(𝐻𝑟 ) ≥ 𝑘 = ∈Ω . 𝑟 𝑟 Therefore ex(𝐻𝑟 ) ≤ 2𝑟 = 𝑂 (log ghw(𝐻𝑟 )) and applying Proposition 6.4 and Lemma 6.2 yields ghw(𝐻𝑟 ) subw(𝐻𝑟 ) ≥ 𝐶 log2 ghw(𝐻𝑟 ) for some universal constant 𝐶 > 0 and all sufficiently large 𝑟 . □ Note that the rank of 𝐻𝑟 is 𝑟 , since each star 𝑆𝑥 has size 𝑟 . That is, the family of hypergraphs studied here has unbounded rank and edge excess.

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181