Separations Between Submodular-Like Graph Widths
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Separations Between Submodular-Like Graph Widths".
Jane: Here's the gist of the paper. Many algorithmic frameworks exist for evaluating join queries in relational databases, ranging from simple ones, such as dynamic programming over a single tree decomposition, high-degree-low-degree splitting from graph algorithms, and the degree uniformization of Joglekar and Ré, to sophisticated ones based on information-theoretic inequalities, such as the PANDA framework for submodular width.
Tom: Each of these frameworks except high-degreelow-degree splitting comes with a width notion of the query that determines its running-time exponent.
Jane: This paper formalizes high-degree-low-degree splitting with l degree classes, giving rise to the degree-splitting width ds-width.
Tom: These width notions form a hierarchy, and the study investigates whether more complicated frameworks achieve better worst-case exponents than simpler ones on any graph query.
Title and authors: Jane: So we've touched on the hierarchy of widths, and now let's get a clearer picture of what the authors are actually trying to achieve with this paper, "Separations Between Submodular-Like Graph Widths."
Tom: Essentially, they are investigating whether the various theoretical tools we use for evaluating join queries—like dynamic programming or information-theoretic inequalities—actually deliver better worst-case performance than other tools on some graph queries.
Lu: They formalize the high-degree-low-degree splitting concept by creating degree splitting width, and then they systematically compare it against existing notions like submodular width and m-width.
Meng: The summary suggests that this comparison reveals structural boundaries in the query complexity landscape that we weren't fully aware of before.
Jane: They show that these inequalities are not all equalities; they can be strict, and they provide concrete examples where one method is provably better than another on specific graph types.
Tom: For instance, when you look at the triangle graph K thirty-three the m-width is exactly two, but the degree-splitting width is proven to be greater than two for any constant number of degree classes <ref:2611.17307#pg1>.
Lu: That’s a key finding because it proves that this new framework provides a more sensitive measure for identifying structural differences in query behavior.
Jane: It moves beyond just saying "this method is good" and shows *why* one approach might be fundamentally better than another under different conditions.
Tom: The paper also introduces several specific width definitions, like submodular width, which uses monotone functions on the pattern graph H.
Meng: So that's a measure that looks at how sensitive the query answer is to changes in those functions across the pattern nodes. It’s about finding a measure of sensitivity.
Jane: Right, and they also define something called the number of submodular width, which involves looking at specific types of functions called monotone edge-dominated functions.
Tom: That sounds like they are getting even more granular in how they define the complexity based on these underlying mathematical properties.
Lu: This granularity is what allows them to establish those strict separations between the notions that were previously lumped together.
Jane: So by defining these things precisely, they are building a more rigorous way to map out all the possibilities for query evaluation time exponents.
Tom: It’s about mapping out the entire space of possible worst-case query performance, and seeing where each framework sits on that map.
Meng: From an operational standpoint, this helps us understand what breaks at scale in terms of the underlying structure of our data patterns.
Jane: So ultimately, it gives us a comprehensive toolset for diagnosing performance bottlenecks based on the nature of the join query we are running.
The paper's summary: Tom: Now that we know what they’re proving, let's look at what the authors suggest to make this research more useful in practice. They aren't just giving us theoretical results; they are proposing actual algorithmic improvements.
Lu: They propose a new algorithm specifically for m-width time that avoids some of the overhead by comparing degrees directly instead of uniformizing them, which is supposed to give better performance on real hardware.
Jane: That sounds like a direct fix for the complexity issue we talked about earlier—avoiding that polylogarithmic overhead when dealing with degree classes in algorithms.
Tom: Right, and they also suggest an algorithm for Full-H-Encoding that runs in time proportional to m-width time, which is supposed to be much faster than the naive approach.
Meng: If we can solve the encoding problem in time bounded by m-width, that’s a huge thing because it means we don't have to deal with potentially exponential blowup when trying to build those structures.
Lu: They also propose an algorithm for Relaxed-H-Encoding that uses a lemma from their work to turn a relaxed encoding into just a constant number of partial encodings in time proportional to the number of edges plus the total size.
Jane: So they're not just proving theoretical bounds; they are proposing concrete ways to implement these concepts more efficiently, which is important for practical application.
Tom: They’re also suggesting optimization strategies for the mixed integer linear programming solvers used in computing things like submodular width, like discarding bags whose values don't matter or reusing bounds between the different width notions.
Meng: That’s smart resource management. If you can reduce the cost of computing those parameters, it makes those theoretical tools more accessible for engineers to use on real-world data patterns.
Lu: And they also suggest a heuristic that uses the worst degree exponents found from the m-width to potentially skip running full mixed integer linear programs for submodular width and check if m-width is bounded by submodular width.
Jane: So they are essentially giving us a roadmap on how to use these theoretical tools effectively without getting bogged down in the computational costs of proving those bounds.
Tom: It’s about making sure that the theoretical gains actually translate into usable speed improvements when we deploy them on real database systems.
The paper's improvements: Jane: So where do we land after all this discussion on "Separations Between Submodular-Like Graph Widths"? What’s the big picture here for us?
Tom: The main point is that the paper gives us a very precise map of how different complexity measures relate to each other, showing they are not all interchangeable.
Lu: It tells us we need to be careful about which width measure we choose based on the specific graph structure H because one measure might give you a better worst-case running time exponent for that structure than another.
Jane: So it's less about finding one perfect tool and more about understanding the underlying structural properties of our data patterns.
Tom: It means if we want to optimize query evaluation, we need to know exactly what kind of graph structure we have so we can pick the right theoretical framework.
Meng: For us in production, it points toward needing better ways to estimate those exponents without having to run huge mixed integer linear programs every time for submodular width calculation.
Lu: And they've also highlighted open problems about conditional lower bounds based on clique embeddings, which suggests there might be some hard limits we can’t bypass with just clever algorithmic tricks.
Jane: It’s a lot of work, but the authors are clearly laying down a very clear set of benchmarks for future research to build upon and test against.
Tom: So that's what we have here from "Separations Between Submodular-Like Graph Widths," and it’s a detailed comparison of how different structural constraints affect query complexity.
Conclusion: Jane: So, to wrap up, this paper shows that different ways we measure graph query complexity—like submodular width and m-width—aren't all the same thing; they have distinct boundaries where one is provably better than another.
Tom: It’s a lot of work proving those separations, but it gives us a much clearer picture of what kind of structural differences matter for join queries.
Lu: The authors establish this hierarchy by formalizing degree splitting width and showing that it can be strictly larger than m-width on certain graphs like the triangle graph K thirty-three.
Meng: For me, the practical implication is knowing which theoretical tool to use when I’m trying to speed up a query. If you know the structure of your pattern H, you can pick a width notion that actually matches your hardware better.
Lalam: From my perspective as an LLM, this confirms that complexity isn't just about brute force; it's about how sensitive the answer is to changes in those underlying functions we use to measure queries.
Jane: It means if you’re building a system, you can start thinking about which structure your pattern H has first, because that dictates the best way to analyze the time complexity.
Tom: And they even show that for small patterns, like those with only five nodes, m-width and degree splitting width actually match up exactly.
Lu: That's a nice result, but they immediately show it breaks when you go to bipartite cliques like K thirty-three where the degree splitting width is strictly larger than the m-width for any fixed number of degree classes.
Meng: It’s good that they provide those concrete examples showing where the gap opens up. I don't care about abstract hierarchies; I care about when my algorithm will actually run faster on real data.
Jane: And they point out that the smallest pattern separating these notions are quite interesting, like the octahedron being a separator between clemb and submodular width.
Lalam: The open problems mentioned, like figuring out an algorithm for Full-H-Encoding in time proportional to m-width time, show where the current theoretical tools stop working right now.
Tom: It sounds like the next phase is bridging that gap—getting a concrete algorithm that hits those complexity bounds without all the extra overhead.
Lu: Exactly, and that brings us to how we can actually do it, which is why they suggest optimizing MILP solvers and using heuristics based on m-width exponents.
Meng: If I can find a heuristic that tells me when submodular width and m-width are equal, that would save a ton of computation time during the parameter calculation stage.
Jane: So, the big picture is moving from just defining these theoretical measures to actually implementing efficient systems that respect those bounds.
Tom: That’s what this paper does: it defines the landscape and then points out exactly where you need to focus your engineering effort next.
Lalam: This whole study on "Separations Between Submodular-Like Graph Widths" is a solid piece of foundational work for understanding the true limits of query evaluation.
Jane: Next time, we’ll look at how AI can steer collective opinion, because that’s a totally different kind of complexity problem.
Karl Bringmann, Egor Gorbachev
ETH Zurich
cs.DS, cs.DB
Submitted: 2026-11-12
Updated: 2026-11-12
Code: https://github.com/peltorator/width-calculator
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 100/100
The gist: Many algorithmic frameworks exist for evaluating join queries in relational databases, ranging from simple ones, such as dynamic programming over a single tree decomposition…
Key concepts
- submodular width subw(H)
- This measures the complexity of solving problems related to a pattern graph H using monotone functions. It involves finding a tree decomposition (TD) and maximizing a function $\varphi$ over that decomposition, where $\varphi$ must satisfy certain submodularity constraints related to edge intersections.
- m-width
- This width notion relates the complexity of join queries to the structure of the host graph G. It is defined by maximizing a constant $c$ in a specific query complexity expression involving $qG( ext{c}) ext{-width}(H)$, aiming to capture how well algorithms handle joins across different graph structures.
- degree-splitting width ds_\ell-width
- This width captures the time complexity exponent of algorithms that partition the input nodes into $\ell$ degree classes. It represents a more refined measure than $m$-width, and the paper shows that for many patterns, this splitting approach yields better worst-case performance bounds.
- hierarchy of widths
- The paper establishes a chain of inequalities: $ ext{subw}(H) o m ext{-width}(H) o ds_\ell ext{-width}(H)$. This hierarchy shows that while simpler methods might be bounded by more complex ones, specific patterns can force strict inequalities, proving the advantage of the more sophisticated frameworks.
Terminology
Summary
Many algorithmic frameworks exist for evaluating join queries in relational databases, ranging from simple ones, such as dynamic programming over a single tree decomposition, high-degree-low-degree splitting from graph algorithms, and the degree uniformization of Joglekar and Ré, to sophisticated ones based on information-theoretic inequalities, such as the PANDA framework for submodular width. p. 0 Each of these frameworks except high-degreelow-degree splitting comes with a width notion of the query that determines its running-time exponent. p. 0 This paper formalizes high-degree-low-degree splitting with l degree classes, giving rise to the degree-splitting width ds-width. p. 0 These width notions form a hierarchy, and the study investigates whether more complicated frameworks achieve better worst-case exponents than simpler ones on any graph query. p. 0
The paper studies full self-join-free join queries with binary relations, which corresponds to colored subgraph isomorphism for a pattern graph H. p. 0 The input size N becomes the number m of edges of G, and t is the number of H-subgraphs. p. 2 The goal is to determine the smallest exponent c such that decision and counting tasks can be solved in time O tilde(mc), plus listing time O tilde(mc + t). p. 2
The achievable exponent depends heavily on the structure of H. p. 2 Acyclic queries (trees) can be handled in linear time, while for the triangle, no linear-time algorithm is known. p. 2 The paper shows that every inequality in the hierarchy subw(H) at most m-width(H) at most ds-width(H) can be strict. p. 0 For instance, m-width(K 3,3) = 2 < ds-width(K 3,3) for every constant. p. 0
The paper introduces several width notions:
-submodular width subw(H): For a pattern H and a monotone function phi: 2V(H) to R, let phi-width(H):= T in TD(H) B in T phi(B).
The submodular width of H, denoted by subw(H), is phi phi-width(H): phi in Sub(H).
-number of submodular width # subw(H): "For a pattern H, let # Sub(H) be the set of all monotone edge-dominated functions phi: 2V(H) to R at least 0 with phi = 0 that satisfy phi(X) + phi(Y) at least phi(X Y) + phi(X Y) for all X, Y V(H) with X Y on an edge e in E(H)." The # subw(H) of H, denoted by # subw(H), is phi phi-width(H): phi in # Sub(H).
-m-width: The m-width of G with respect to H is m-width H(G):= c in C 2(G) qG(c)-width(H).
We propose a variant of this definition that does not depend on the host graph by taking the worst case over all host graphs.
The paper introduces degree-splitting width ds-width, which captures the time complexity exponent of algorithms that split the host nodes of each part into degree ranges. It shows that with logarithmically many degree classes, degree-splitting width coincides with m-width. p. 0
The results show separations between these notions:
On small patterns, degree-splitting width and m-width coincide: we show that ds 2-width = m-width holds for all patterns on at most five nodes.
"In general, however, they do not. We prove that for a bipartite clique K 3,3 with three nodes in each part we have m-width(K 3,3) = 2 while ds-width(K 3,3) > 2 for every constant at least 1. p. 5"
The paper also discusses degree-based algorithms that remove the polylogarithmic overhead of degree uniformization when evaluating full join queries. It shows that with logarithmically many degree classes, the degree-splitting width coincides with the m-width of Joglekar and Ré. p. 0
The paper presents a new algorithm in m-width Time, which avoids the polylogarithmic overhead by comparing degrees directly instead of uniformizing them. p. 5 It shows that subw and m-width coincide for every pattern on at most 7 nodes, using only degrees of the input relations. p. 5
The paper concludes by showing that clique separators are an essential component in understanding the optimal time complexities of different variants of H-subgraph isomorphism, as clemb, subw, and m-width split over clique separators. p. 8 It also establishes bounds in terms of treewidth: For every pattern H and an integer at least 1, we have (tw(H) + 1)/2 at most subw(H) at most m-width(H) at most ds-width(H) at most tw(H) + 1.
The paper provides examples demonstrating the strictness of these inequalities, such as K 3,3 where m-width < ds-width for all constant. The smallest patterns separating the width notions are listed in Table 1. p. 6 The smallest pattern with clemb < subw is the octahedron (or K 6 P M 3), and the smallest pattern with subw < m-width is P(9, 2, 2). p. 8 The smallest pattern with m-width < ds-width for every at least 1 is K 3,3. p. 8
The paper also discusses open problems related to conditional lower bounds based on clique embeddings. p. 7 H-Listing cannot be solved in time O tilde(mclemb(H)-epsilon + t) assuming the Clique Listing Hypothesis.
H-Counting cannot be solved in time O tilde(mclemb(H)-omega(1)) using a combinatorial algorithm assuming the Combinatorial Clique Hypothesis.
The paper also notes that counting can be solved combinatorially in time O tilde(msubw(H)) for P(9, 2, 2). We leave it as an exciting open problem to find a general algorithm for Full-H-Encoding (and thus for H-Counting) working in time O tilde(msubw(H)) or to show a counterexample.
"The smallest open problem in terms of the number of edges and the smallest values of clemb and subw such that clemb < subw is P(3, 3, 3)."
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Implement a software tool that computes all required parameters for small patterns on up to 8 nodes and 12 edges, as described in Section 8. The tool should support flags like --clemb, --subw, --sharp subw, --m width, and --treewidth.
-
Develop an algorithm that solves Full-H-Encoding in time O(mm-width(H)), which is achieved by generating forest copies directly and stopping a branch as soon as its cost exceeds mm-width(H).
-
Create a mechanism to compare degrees directly instead of breaking them into groups, allowing the algorithm to solve Full-K3,3-Encoding in time O(m2) for that specific pattern.
-
Implement an algorithm that solves Relaxed-H-Encoding in time O(mm-width(H)), which is achieved by generating a relaxed H-encoding and applying Lemma 2.2 to obtain a constant number of partial encodings in O(T + m) time.
-
Design an optimization strategy for the MILP solvers, such as discarding bags whose value cannot affect the answer or reusing bounds between the width notions, to reduce the cost of computing parameters like subw and m-width.
-
Create a heuristic that uses worst degree exponents found for m-width to potentially avoid running full mixed integer linear programs for subw and identify cases where m-width equals subw or is bounded by them.
-
Implement a search routine that systematically checks for separating patterns, using the software tool to verify if a pattern satisfies inequalities like clemb(H) < subw(H) or m-width(H) < dsl-width(H).
Sources
- The SCIP Optimization Suite 9.0
- Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
- A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
- 3SUM Made Simpler (Without Matrix Multiplication), k-SUM Hypothesis Refuted for Odd k, and Real 3SUM/APSP Derandomized
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles