Cuts and Gauges for Submodular Width

Matthias Lanzinger

arxiv: 2604.22663 · v1 · submitted 2026-04-24 · 💻 cs.DS · cs.DB· cs.DM

Cuts and Gauges for Submodular Width

Matthias Lanzinger This is my paper

Pith reviewed 2026-05-08 10:15 UTC · model grok-4.3

classification 💻 cs.DS cs.DBcs.DM

keywords submodular widthhypergraph widthbranchwidthgeneralized hypertree widthconjunctive query evaluationconvex body characterization

0 comments

The pith

Submodular width can be approximated within a factor of 3/2 by a branchwidth based on hypergraph edge separations and submodular costs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper recasts submodular width geometrically to show it is approximable by a new branchwidth parameter up to 3/2. This parameter uses edge separations in the hypergraph whose costs are set by admissible submodular functions. The reformulation converts questions about lower bounds into finding balanced separations with low cost, which is then captured variationally by a convex body. This allows relating submodular width to line-graph treewidth, multicommodity flow, and generalized hypertree width, yielding that submodular width is at least generalized hypertree width divided by its logarithm under natural conditions. A reader would care because submodular width determines the tractability of evaluating conjunctive queries on databases.

Core claim

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, which is expressed through a variational characterisation in terms of a convex body. Using these tools, submodular width relates to line-graph treewidth and multicommodity flow, and under various natural conditions subw(H) is Omega(ghw(H)/log ghw(H)).

What carries the argument

The new branchwidth parameter defined via edge separations and induced costs from admissible submodular functions, together with its variational characterization as the gauge of a convex body.

If this is right

Lower bounds for submodular width reduce to finding well-balanced low-cost edge separations.
Submodular width is connected to line-graph treewidth and multicommodity flow problems.
Under natural conditions, generalized hypertree width upper-bounds submodular width up to a logarithmic factor.
Conjunctive query evaluation complexity can be bounded using this approximable width measure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The approximation may enable new algorithms for computing or approximating submodular width in practice for query optimization.
The link to multicommodity flow suggests potential use of network flow techniques to bound query complexity.
The Omega relation implies that in many hypergraphs, the two widths are within logarithmic factors, tightening known separations.
The convex body characterization could generalize to other width parameters in hypergraph theory.

Load-bearing premise

The submodular functions must be admissible, and the hypergraph must meet the unspecified natural conditions for the lower bound relating it to generalized hypertree width to hold; the variational characterization via the convex body must exactly capture the submodular width.

What would settle it

A hypergraph where the ratio between the new branchwidth and submodular width exceeds 3/2, or a counterexample hypergraph satisfying the natural conditions where submodular width is smaller than generalized hypertree width divided by the log of the latter.

Figures

Figures reproduced from arXiv: 2604.22663 by Matthias Lanzinger.

**Figure 1.** Figure 1: Illustration for the bounded-excess proof for a vertex view at source ↗

read the original abstract

Submodular width is a central structural measure governing the complexity of conjunctive query evaluation. In this paper we recast submodular width in geometric terms. We how that submodular width can be approximated, up to a factor $3/2$, by a new branchwidth parameter defined in terms of edge separations in the hypergraph and the costs induced on them by admissible submodular functions. This reformulation turns lower bounds on submodular width into the problem of constructing well-balanced edge separations whose induced cost remains small. We then express this connection through a variational characterisation in terms of a convex body. Using these tools, we relate submodular width to more familiar graph-theoretic notions, including line-graph treewidth and multicommodity flow, and obtain general conditions under which submodular width is tightly linked to generalised hypertree width. In particular, under various natural conditions we show that \[ subw(H) \in \Omega \left(\frac{ghw(H)}{\log ghw(H)} \right). \]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Geometric recasting gives 3/2-approx for submodular width via new branchwidth on separations plus Omega(ghw/log ghw) link, but rests on exact convex-body match.

read the letter

This paper recasts submodular width in geometric terms using cuts and gauges, and shows it can be approximated to within a factor of 3/2 by a new branchwidth parameter based on edge separations in the hypergraph. It also gives conditions under which submodular width is Omega of generalized hypertree width divided by log of that width. The geometric approach is the main novelty here. By defining costs on separations induced by admissible submodular functions and linking it to a convex body variational characterization, the work turns lower bound questions into finding well-balanced separations with small cost. This also lets them relate the parameter to line-graph treewidth and multicommodity flow, which opens up some cross-area tools. If the proofs hold, this could be a useful addition for analyzing conjunctive query complexity. The 3/2 approximation seems technically interesting because it comes from the branchwidth on those separations. The lower bound absorbs a log factor, which is common in these width parameters but still gives a meaningful relation under the stated conditions. The soft spots are around the assumptions. The claims depend on the convex body exactly capturing submodular width for the admissible functions, and the various natural conditions for the Omega bound are not detailed in the abstract. If those conditions turn out to be restrictive or if the variational form has some gap, the results become more conditional. I would check the full paper for how they construct the separations and whether the admissible functions impose extra constraints like symmetry or monotonicity. This is for people working on structural parameters in databases and hypergraphs. A reader interested in new ways to bound query evaluation time or in bridging submodular width to classical graph widths would get value from the reformulation. It deserves peer review. The ideas are fresh enough and the connections are worth checking in detail, even if revisions might be needed to clarify the conditions.

Referee Report

3 major / 2 minor

Summary. The paper recasts submodular width geometrically by introducing a new branchwidth parameter on hypergraph edge separations whose costs are induced by admissible submodular functions. It claims this parameter approximates submodular width to within a factor of 3/2, provides a variational characterization of the width via a convex body, and uses these tools to relate submodular width to line-graph treewidth and multicommodity flow. Under various natural conditions the paper derives the lower bound subw(H) ∈ Ω(ghw(H)/log ghw(H)).

Significance. If the claims hold, the geometric reformulation supplies new tools for constructing well-balanced separations and for converting lower bounds on submodular width into concrete separation problems. The 3/2-approximation and the Ω(ghw/log ghw) relation would tighten the connection between submodular width and classical hypergraph parameters, which is relevant for conjunctive-query complexity. The convex-body view may also enable flow-based or convex-optimization techniques for width computation.

major comments (3)

[variational characterisation section (likely §4)] The central 3/2-approximation and the Ω(ghw/log ghw) lower bound both rely on the variational characterization via the convex body exactly equaling (not merely lower-bounding) submodular width for admissible functions. The manuscript must explicitly prove that the convex body formulation captures the width with no hidden integrality gap; otherwise both the approximation guarantee and the logarithmic factor in the lower bound become conditional on an unstated approximation ratio.
[lower-bound theorem (likely §5)] The lower-bound statement is qualified by 'various natural conditions' that are never enumerated. The manuscript must list the precise assumptions on the hypergraph H and on the admissible submodular functions (e.g., monotonicity, symmetry, marginal constraints) under which subw(H) ∈ Ω(ghw(H)/log ghw(H)) holds; without this list the claim cannot be verified or applied.
[definition of the branchwidth parameter (likely §3)] The definition of the new branchwidth parameter (edge separations with submodular costs) must be shown to be independent of the original submodular-width definition; otherwise the claimed 3/2-approximation risks circularity when the admissible functions are chosen to match the width exactly.

minor comments (2)

[abstract] Abstract contains the typo 'We how that' instead of 'We show that'.
[abstract] The abstract states the approximation and lower-bound claims but the manuscript should include a short proof sketch or reference to the key lemma for each, even if full details appear later.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments identify areas where the presentation can be strengthened, particularly around explicit proofs, enumeration of conditions, and clarification of definitions. We will revise the manuscript accordingly and address each major comment below.

read point-by-point responses

Referee: [variational characterisation section (likely §4)] The central 3/2-approximation and the Ω(ghw/log ghw) lower bound both rely on the variational characterization via the convex body exactly equaling (not merely lower-bounding) submodular width for admissible functions. The manuscript must explicitly prove that the convex body formulation captures the width with no hidden integrality gap; otherwise both the approximation guarantee and the logarithmic factor in the lower bound become conditional on an unstated approximation ratio.

Authors: We agree that an explicit proof of exact equality is necessary to fully support the claims. The convex body in Section 4 is constructed directly from the admissible submodular functions and the separation costs so that its support function equals submodular width; however, to eliminate any ambiguity about a possible integrality gap, we will insert a new lemma (with proof) establishing that the variational minimum over the convex body coincides exactly with the submodular-width definition for admissible functions. This lemma will be placed immediately before the 3/2-approximation theorem. revision: yes
Referee: [lower-bound theorem (likely §5)] The lower-bound statement is qualified by 'various natural conditions' that are never enumerated. The manuscript must list the precise assumptions on the hypergraph H and on the admissible submodular functions (e.g., monotonicity, symmetry, marginal constraints) under which subw(H) ∈ Ω(ghw(H)/log ghw(H)) holds; without this list the claim cannot be verified or applied.

Authors: We accept that the conditions must be stated explicitly. The lower bound holds when the admissible submodular functions are monotone and symmetric, the hypergraph has bounded maximum degree, and the marginals satisfy a uniform expansion condition that controls the flow-cut gap. In the revised Section 5 we will replace the phrase 'various natural conditions' with a numbered list of these four assumptions, each accompanied by a one-sentence justification and a reference to the relevant lemma. revision: yes
Referee: [definition of the branchwidth parameter (likely §3)] The definition of the new branchwidth parameter (edge separations with submodular costs) must be shown to be independent of the original submodular-width definition; otherwise the claimed 3/2-approximation risks circularity when the admissible functions are chosen to match the width exactly.

Authors: The branchwidth parameter is defined independently: admissibility is a syntactic property (submodularity, monotonicity, normalization to 1 on singletons) fixed before any optimization, while submodular width is the infimum of the same class of functions. The 3/2-approximation proceeds by exhibiting, for every admissible function f, a balanced edge separation whose cost under f is at most 3/2 times the width contribution of f; the argument never assumes that f itself attains the global minimum. We will add a short clarifying paragraph at the end of Section 3 that spells out this separation of definitions and notes that the approximation holds uniformly over the admissible class. revision: yes

Circularity Check

0 steps flagged

No circularity: new branchwidth parameter and variational characterization are defined independently

full rationale

The paper introduces a new branchwidth parameter defined directly from edge separations in the hypergraph and costs from admissible submodular functions. This is used to approximate submodular width up to 3/2. The variational characterization via convex body is presented as a derived tool from the reformulation, not presupposed to equal the width. The Omega(ghw/log ghw) relation is stated as obtained under various natural conditions rather than by construction or self-citation. No quoted step reduces a prediction or central claim to a fitted input or prior self-result by definition. The derivation chain remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the prior definition of submodular width and the notion of admissible submodular functions; the paper introduces one new parameter but does not postulate new physical entities.

axioms (2)

domain assumption Admissible submodular functions exist and induce well-defined costs on hypergraph edge separations
Invoked to define the new branchwidth parameter and the approximation.
domain assumption Various natural conditions on the hypergraph hold for the Omega lower bound
Stated in the abstract as prerequisite for subw(H) ∈ Ω(ghw(H)/log ghw(H)).

invented entities (1)

New branchwidth parameter defined via edge separations and submodular costs no independent evidence
purpose: To approximate submodular width within 3/2 factor
Introduced as the central geometric reformulation tool.

pith-pipeline@v0.9.0 · 5473 in / 1434 out tokens · 38590 ms · 2026-05-08T10:15:01.580819+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 2 internal anchors

[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

work page doi:10.1016/j.ejc.2007.04.013 2007
[2]

2022.Database Theory

Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris. 2022.Database Theory. Open source at https://github.com/pdm-book/community

work page 2022
[3]

Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In58th 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

work page doi:10.1109/focs.2017.37 2017
[4]

Chandra Chekuri and Julia Chuzhoy. 2013. Large-treewidth graph decompositions and applications. InProceedings of the 45th Annual ACM Symposium on Theory of Computing Conference, STOC 2013. ACM, 291–300. doi:10.1145/2488608. 2488645

work page doi:10.1145/2488608 2013
[5]

Bruce Shepherd

Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. 2005. Multicommodity flow, well-linked terminals, and routing problems. InProceedings of the 37th Annual ACM Symposium on Theory of Computin, STOC 2005. ACM, 183–192. doi:10.1145/1060590.1060618

work page doi:10.1145/1060590.1060618 2005
[6]

Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler. 2020. Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems. InProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. ijcai.org, 1726–1733. doi:10.24963/IJCAI.2020/239

work page doi:10.24963/ijcai.2020/239 2020
[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

work page doi:10.1007/bf02122693 1990
[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

work page doi:10.1137/05064299x 2008
[9]

Delbert R Fulkerson. 1972. Anti-blocking polyhedra.Journal of Combinatorial Theory, Series B12, 1 (1972), 50–71

work page 1972
[10]

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. 2021. Complexity Analysis of Generalized and Fractional Hypertree Decompositions.J. ACM68, 5 (2021), 38:1–38:50. doi:10.1145/3457374

work page doi:10.1145/3457374 2021
[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

work page doi:10.1006/jcss.2001.1809 2002
[12]

Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. 2009. Generalized hypertree decompositions: NP-hardness and tractable variants.J. ACM56, 6 (2009), 30:1–30:32. doi:10.1145/1568318.1568320

work page doi:10.1145/1568318.1568320 2009
[13]

Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM54, 1 (2007), 1:1–1:24. doi:10.1145/1206035.1206036

work page doi:10.1145/1206035.1206036 2007
[14]

Martin Grohe. 2016. Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles).CoRRabs/1605.06704 (2016). arXiv:1605.06704 http://arxiv.org/abs/1605.06704

work page arXiv 2016
[15]

Martin Grohe and Dániel Marx. 2006. Constraint solving via fractional edge covers. InProceedings 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

work page arXiv 2006
[16]

Mahmoud Abo Khamis and Hubie Chen. 2026. Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time.CoRRabs/2603.13624 (2026). doi:10.48550/ARXIV.2603.13624 arXiv:2603.13624

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2603.13624 2026
[17]

Mahmoud Abo Khamis, Xiao Hu, and Dan Suciu. 2025. Fast Matrix Multiplication meets the Submodular Width.Proc. ACM Manag. Data3, 2 (2025), 98:1–98:26. doi:10.1145/3725235

work page doi:10.1145/3725235 2025
[18]

Ngo, and Dan Suciu

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?. InProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017. ACM, 429–444. doi:10.1145/3034786.3056105

work page doi:10.1145/3034786.3056105 2017
[19]

Ngo, and Dan Suciu

Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2025. PANDA: Query Evaluation in Submodular Width. TheoretiCS4, Article 12 (2025). doi:10.46298/THEORETICS.25.12

work page doi:10.46298/theoretics.25.12 2025
[20]

PANDAExpress: a Simpler and Faster PANDA Algorithm

Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2025. PANDAExpress: a Simpler and Faster PANDA Algorithm. CoRRabs/2512.10217 (2025). doi:10.48550/ARXIV.2512.10217 arXiv:2512.10217

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2512.10217 2025
[21]

Matthias Lanzinger. 2022. The Complexity of Conjunctive Queries with Degree 2. InProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022. ACM, 91–102. doi:10.1145/3517804. 3524152

work page doi:10.1145/3517804 2022
[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

work page doi:10.1007/s00224-009-9248-9 2011
[23]

Dániel Marx. 2013. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries.J. ACM60, 6 (2013), 42:1–42:51. doi:10.1145/2535926 Cuts and Gauges for Submodular Width 29

work page doi:10.1145/2535926 2013
[24]

Karl Menger. 1927. Zur allgemeinen kurventheorie.Fundamenta mathematicae10, 1 (1927), 96–115

work page 1927
[25]

Sang-il Oum and Paul D. Seymour. 2006. Approximating clique-width and branch-width.J. Comb. Theory B96, 4 (2006), 514–528. doi:10.1016/J.JCTB.2005.10.006

work page doi:10.1016/j.jctb.2005.10.006 2006
[26]

B. A. Reed. 1997. Tree Width and Tangles: A New Connectivity Measure and Some Applications. InSurveys 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

work page doi:10.1017/cbo9780511662119.006 1997
[27]

1997.Convex analysis

R Tyrrell Rockafellar. 1997.Convex analysis. Vol. 28. Princeton university press

work page 1997
[28]

Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture.J. ACM67, 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...

work page doi:10.1145/3402029 2020

[1] [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

work page doi:10.1016/j.ejc.2007.04.013 2007

[2] [2]

2022.Database Theory

Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris. 2022.Database Theory. Open source at https://github.com/pdm-book/community

work page 2022

[3] [3]

Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In58th 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

work page doi:10.1109/focs.2017.37 2017

[4] [4]

Chandra Chekuri and Julia Chuzhoy. 2013. Large-treewidth graph decompositions and applications. InProceedings of the 45th Annual ACM Symposium on Theory of Computing Conference, STOC 2013. ACM, 291–300. doi:10.1145/2488608. 2488645

work page doi:10.1145/2488608 2013

[5] [5]

Bruce Shepherd

Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. 2005. Multicommodity flow, well-linked terminals, and routing problems. InProceedings of the 37th Annual ACM Symposium on Theory of Computin, STOC 2005. ACM, 183–192. doi:10.1145/1060590.1060618

work page doi:10.1145/1060590.1060618 2005

[6] [6]

Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler. 2020. Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems. InProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. ijcai.org, 1726–1733. doi:10.24963/IJCAI.2020/239

work page doi:10.24963/ijcai.2020/239 2020

[7] [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

work page doi:10.1007/bf02122693 1990

[8] [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

work page doi:10.1137/05064299x 2008

[9] [9]

Delbert R Fulkerson. 1972. Anti-blocking polyhedra.Journal of Combinatorial Theory, Series B12, 1 (1972), 50–71

work page 1972

[10] [10]

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. 2021. Complexity Analysis of Generalized and Fractional Hypertree Decompositions.J. ACM68, 5 (2021), 38:1–38:50. doi:10.1145/3457374

work page doi:10.1145/3457374 2021

[11] [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

work page doi:10.1006/jcss.2001.1809 2002

[12] [12]

Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. 2009. Generalized hypertree decompositions: NP-hardness and tractable variants.J. ACM56, 6 (2009), 30:1–30:32. doi:10.1145/1568318.1568320

work page doi:10.1145/1568318.1568320 2009

[13] [13]

Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM54, 1 (2007), 1:1–1:24. doi:10.1145/1206035.1206036

work page doi:10.1145/1206035.1206036 2007

[14] [14]

Martin Grohe. 2016. Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles).CoRRabs/1605.06704 (2016). arXiv:1605.06704 http://arxiv.org/abs/1605.06704

work page arXiv 2016

[15] [15]

Martin Grohe and Dániel Marx. 2006. Constraint solving via fractional edge covers. InProceedings 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

work page arXiv 2006

[16] [16]

Mahmoud Abo Khamis and Hubie Chen. 2026. Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time.CoRRabs/2603.13624 (2026). doi:10.48550/ARXIV.2603.13624 arXiv:2603.13624

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2603.13624 2026

[17] [17]

Mahmoud Abo Khamis, Xiao Hu, and Dan Suciu. 2025. Fast Matrix Multiplication meets the Submodular Width.Proc. ACM Manag. Data3, 2 (2025), 98:1–98:26. doi:10.1145/3725235

work page doi:10.1145/3725235 2025

[18] [18]

Ngo, and Dan Suciu

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?. InProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017. ACM, 429–444. doi:10.1145/3034786.3056105

work page doi:10.1145/3034786.3056105 2017

[19] [19]

Ngo, and Dan Suciu

Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2025. PANDA: Query Evaluation in Submodular Width. TheoretiCS4, Article 12 (2025). doi:10.46298/THEORETICS.25.12

work page doi:10.46298/theoretics.25.12 2025

[20] [20]

PANDAExpress: a Simpler and Faster PANDA Algorithm

Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2025. PANDAExpress: a Simpler and Faster PANDA Algorithm. CoRRabs/2512.10217 (2025). doi:10.48550/ARXIV.2512.10217 arXiv:2512.10217

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2512.10217 2025

[21] [21]

Matthias Lanzinger. 2022. The Complexity of Conjunctive Queries with Degree 2. InProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022. ACM, 91–102. doi:10.1145/3517804. 3524152

work page doi:10.1145/3517804 2022

[22] [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

work page doi:10.1007/s00224-009-9248-9 2011

[23] [23]

Dániel Marx. 2013. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries.J. ACM60, 6 (2013), 42:1–42:51. doi:10.1145/2535926 Cuts and Gauges for Submodular Width 29

work page doi:10.1145/2535926 2013

[24] [24]

Karl Menger. 1927. Zur allgemeinen kurventheorie.Fundamenta mathematicae10, 1 (1927), 96–115

work page 1927

[25] [25]

Sang-il Oum and Paul D. Seymour. 2006. Approximating clique-width and branch-width.J. Comb. Theory B96, 4 (2006), 514–528. doi:10.1016/J.JCTB.2005.10.006

work page doi:10.1016/j.jctb.2005.10.006 2006

[26] [26]

B. A. Reed. 1997. Tree Width and Tangles: A New Connectivity Measure and Some Applications. InSurveys 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

work page doi:10.1017/cbo9780511662119.006 1997

[27] [27]

1997.Convex analysis

R Tyrrell Rockafellar. 1997.Convex analysis. Vol. 28. Princeton university press

work page 1997

[28] [28]

Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture.J. ACM67, 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...

work page doi:10.1145/3402029 2020