pith. sign in

arxiv: 2606.02183 · v1 · pith:62TEYF4Inew · submitted 2026-06-01 · 💻 cs.DS · cs.DB

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration

Karl Bringmann , Nick Fischer , Yanheng Wang This is my paper

Pith reviewed 2026-06-28 12:19 UTC · model grok-4.3

classification 💻 cs.DS cs.DB
keywords projected treesenumerationlistingsubgraph isomorphismmatrix multiplicationsubmodular widthdelaypreprocessing
0
0 comments X

The pith

New algorithms enumerate projected trees using polynomial preprocessing time and polylogarithmic delay.

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

The paper presents the first algorithms that enumerate all solutions for projected trees after only polynomial preprocessing and with polylogarithmic delay per solution. Earlier methods required either superpolynomial time in the pattern size plus output size or linear dependence on the output size multiplied by a polynomial factor. The work also supplies a generic reduction that converts any listing algorithm into an enumeration algorithm with controlled preprocessing and delay. Both results rest on fast rectangular matrix multiplication and extend to hypergraph patterns measured by submodular width.

Core claim

We present the first algorithms for enumerating projected trees with polynomial preprocessing time (widetilde O(n^17.42)) and polylogarithmic delay (polylog(n)). Prior algorithms required time Omega(n^Omega(k) + t) or t · n^Omega(1). The result generalizes to arbitrary projected hypergraphs with preprocessing time widetilde O(m^17.42 · subw(H)) and polylogarithmic delay. We also give a generic reduction that turns any listing algorithm running in time O(f(n,m) + t · g(n,m)) into an enumeration algorithm with preprocessing time O((f(n,m) + g(n,m) + m) log^2 n) and delay O(g(n,m)).

What carries the argument

Fast rectangular and output-sensitive matrix multiplication, which powers the enumeration procedure for trees and hypergraphs; complemented by a generic enumeration-to-listing reduction that equates the two problems under standard assumptions.

If this is right

  • Projected trees admit enumeration after widetilde O(n^17.42) preprocessing with polylog(n) delay per solution.
  • The same bounds hold for arbitrary projected hypergraphs, scaled by the submodular width of the pattern.
  • Any listing algorithm for colored subgraph isomorphism running in O(f + t g) time yields an enumeration algorithm with O((f + g + m) log^2 n) preprocessing and O(g) delay.
  • Any algorithm that beats Omega(n^Omega(k) + t) for these problems must rely on fast matrix multiplication.

Where Pith is reading between the lines

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

  • The listing-to-enumeration reduction may be applied to other pattern-matching problems where only listing algorithms are currently known.
  • Further improvements to the matrix-multiplication exponent would immediately lower the preprocessing exponent for projected-tree enumeration.
  • The submodular-width parameterization suggests that similar enumeration results could be sought for additional classes of hypergraph queries whose width is bounded.

Load-bearing premise

Fast algorithms for rectangular matrix multiplication exist and can be invoked to accelerate the enumeration steps.

What would settle it

An algorithm that enumerates all projected trees in preprocessing time o(n^17.42) without using fast matrix multiplication, or an explicit fine-grained reduction proving that any such improvement requires matrix multiplication.

Figures

Figures reproduced from arXiv: 2606.02183 by Karl Bringmann, Nick Fischer, Yanheng Wang.

Figure 1
Figure 1. Figure 1: The recursion tree has root ε and nodes labeled by bitstrings. The tree R (drawn in black) corresponds to the recursive calls that have started. The ancestors A(u ∗ ) (drawn as the yellow path) correspond to the recursive calls that have started but not yet finished. The leaves L of R are marked in blue. The leaves L ′ of R ′ = R \ L are marked in green. Claim. |L ′ | ≤ j /b + 1. Proof. Since L ′ are the l… view at source ↗
read the original abstract

The subgraph isomorphism problem and its generalizations such as conjunctive queries, where some nodes are projected, are among the most fundamental problems in graph algorithms and database theory. In this paper, we study the listing and enumeration variants of these problems and present two main results. (1) We present the first algorithms for enumerating projected trees with polynomial preprocessing time ($\widetilde{O}(n^{17.42})$) and polylogarithmic delay ($\mathrm{polylog}(n)$). Prior to this work, all algorithms in the literature required time $\Omega(n^{\Omega(k)} + t)$ or $t \cdot n^{\Omega(1)}$ to list all copies of a $k$-node tree with projections, where $t$ is the number of solutions. Our result generalizes to arbitrary projected hypergraphs, achieving enumeration in preprocessing time $\widetilde{O}(m^{17.42 \cdot \mathrm{subw}(H)})$ and polylogarithmic delay, where $\mathrm{subw}(H)$ is the submodular width of the pattern hypergraph $H$. We heavily rely on fast (rectangular and output-sensitive) matrix multiplication, which we complement by fine-grained lower bounds indicating that any algorithm beating time $\Omega(n^{\Omega(k)} + t)$ must rely on fast matrix multiplication. (2) As our second main result, we present a generic enumeration-to-listing reduction, establishing that listing and enumeration are equivalent under natural assumptions. For (colored) subgraph isomorphism, our reduction transforms any listing algorithm running in time $O(f(n,m) + t \cdot g(n,m))$ into an enumeration algorithm with preprocessing time $O((f(n,m)+g(n,m)+m) \log^2 n)$ and delay $O(g(n,m))$. We utilize this equivalence as a tool for proving our first main result, and we expect that our generic reduction will find many future applications.

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.

Circularity Check

0 steps flagged

No circularity; derivation relies on external MM primitives and internally proven reduction

full rationale

The paper's upper bounds are constructed explicitly from fast rectangular/output-sensitive matrix multiplication (an external, long-established algorithmic primitive not defined or fitted within this work) and a new generic enumeration-to-listing reduction that is stated and proved as the second main result inside the paper itself. The lower bounds are fine-grained reductions showing necessity of the same external MM assumption. No equation, definition, or self-citation reduces any claimed runtime or equivalence to a fitted parameter, renamed input, or prior self-result by construction. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the exponent 17.42 and submodular-width dependence are stated as outcomes rather than fitted inputs.

pith-pipeline@v0.9.1-grok · 5890 in / 1173 out tokens · 25920 ms · 2026-06-28T12:19:38.178581+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

65 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Ryan Williams , title =

  2. [2]

    Don Coppersmith , title =

  3. [3]

    New Bounds for Matrix Multiplication: from Alpha to Omega , booktitle =

    Virginia. New Bounds for Matrix Multiplication: from Alpha to Omega , booktitle =

  4. [4]

    More Asymmetry Yields Faster Matrix Multiplication , booktitle =

    Josh Alman and Ran Duan and Virginia. More Asymmetry Yields Faster Matrix Multiplication , booktitle =

  5. [5]

    The Time Complexity of Fully Sparse Matrix Multiplication , booktitle =

    Amir Abboud and Karl Bringmann and Nick Fischer and Marvin K. The Time Complexity of Fully Sparse Matrix Multiplication , booktitle =

  6. [6]

    Fan R. K. Chung and Ronald L. Graham and Peter Frankl and James B. Shearer , title =. J. Comb. Theory

  7. [7]

    2021 , url =

    Madhur Tulsiani , title =. 2021 , url =

    2021

  8. [8]

    Understanding and using linear programming , series =

    Bernd G. Understanding and using linear programming , series =

  9. [9]

    Noga Alon and Raphael Yuster and Uri Zwick , title =. J

  10. [10]

    Yann Strozecki , title =. Bull

  11. [11]

    Florent Capelli and Yann Strozecki , title =. Discret. Appl. Math. , volume =

  12. [12]

    2024 , eprint =

    From Amortized to Worst Case Delay in Enumeration Algorithms , author =. 2024 , eprint =

    2024

  13. [13]

    National Institute of Informatics, Tokyo, 2003 , url =

    Two general methods to reduce delay and change of enumeration algorithms , author =. National Institute of Informatics, Tokyo, 2003 , url =

    2003

  14. [14]

    Hartung and Hung Phuc Hoang and Torsten M

    Elizabeth J. Hartung and Hung Phuc Hoang and Torsten M. Combinatorial generation via permutation languages , booktitle =

  15. [15]

    Traversing Combinatorial 0/1-Polytopes via Optimization , journal =

    Arturo Merino and Torsten M. Traversing Combinatorial 0/1-Polytopes via Optimization , journal =

  16. [16]

    Ramesh , title =

    Sanjiv Kapoor and H. Ramesh , title =

  17. [17]

    Takeaki Uno , title =

  18. [18]

    Alon Itai and Michael Rodeh , title =

  19. [19]

    Towards polynomial lower bounds for dynamic problems , booktitle =

    Mihai P. Towards polynomial lower bounds for dynamic problems , booktitle =

  20. [20]

    Tsvi Kopelowitz and Seth Pettie and Ely Porat , title =

  21. [21]

    Monochromatic Triangles, Triangle Listing and

    Virginia. Monochromatic Triangles, Triangle Listing and

  22. [22]

    Listing Triangles , booktitle =

    Andreas Bj. Listing Triangles , booktitle =

  23. [23]

    Amir Abboud and Seri Khoury and Oree Leibowitz and Ron Safier , title =

  24. [24]

    Ce Jin and Yinzhan Xu , title =

  25. [25]

    Amir Abboud and Karl Bringmann and Nick Fischer , title =

  26. [26]

    Amir Abboud and Karl Bringmann and Seri Khoury and Or Zamir , title =

  27. [27]

    Listing 6-Cycles , booktitle =

    Ce Jin and Virginia. Listing 6-Cycles , booktitle =

  28. [28]

    Listing 6-Cycles in Sparse Graphs , booktitle =

    Virginia. Listing 6-Cycles in Sparse Graphs , booktitle =

  29. [29]

    Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques , booktitle =

    Mina Dalirrooyfard and Surya Mathialagan and Virginia. Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques , booktitle =

  30. [30]

    Norishige Chiba and Takao Nishizeki , title =

  31. [31]

    Lukasz Kowalik , title =

  32. [32]

    Karl Bringmann and Egor Gorbachev , title =

  33. [33]

    Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve , booktitle =

    Amir Abboud and Arturs Backurs and Karl Bringmann and Marvin K. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve , booktitle =

  34. [34]

    A Dichotomy for Regular Expression Membership Testing , booktitle =

    Karl Bringmann and Allan Gr. A Dichotomy for Regular Expression Membership Testing , booktitle =

  35. [35]

    Fan and Paraschos Koutris , title =

    Shaleen Deep and Hangdong Zhao and Austen Z. Fan and Paraschos Koutris , title =. Proc

  36. [36]

    Shaleen Deep and Xiao Hu and Paraschos Koutris , title =. Log. Methods Comput. Sci. , volume =

  37. [37]

    Mahmoud Abo Khamis and Xiao Hu and Dan Suciu , title =. Proc

  38. [38]

    Shaleen Deep and Xiao Hu and Paraschos Koutris , title =

  39. [39]

    Xiao Hu , title =. Proc

  40. [40]

    Guillaume Bagan and Arnaud Durand and Etienne Grandjean , title =

  41. [41]

    Christoph Berkholz and Fabian Gerhardt and Nicole Schweikardt , title =

  42. [42]

    Arnaud Durand , title =

  43. [43]

    Arnaud Durand and Etienne Grandjean , title =

  44. [44]

    On the Enumeration Complexity of Unions of Conjunctive Queries , journal =

    Nofar Carmeli and Markus Kr. On the Enumeration Complexity of Unions of Conjunctive Queries , journal =

  45. [45]

    Enumeration Complexity of Conjunctive Queries with Functional Dependencies , journal =

    Nofar Carmeli and Markus Kr. Enumeration Complexity of Conjunctive Queries with Functional Dependencies , journal =

  46. [46]

    Karl Bringmann and Nofar Carmeli , title =. Log. Methods Comput. Sci. , volume =

  47. [47]

    Wojciech Kazana and Luc Segoufin , title =

  48. [48]

    If the Current Clique Algorithms are Optimal, So is Valiant's Parser , booktitle =

    Amir Abboud and Arturs Backurs and Virginia. If the Current Clique Algorithms are Optimal, So is Valiant's Parser , booktitle =

  49. [49]

    Nicole Schweikardt and Luc Segoufin and Alexandre Vigny , title =. J

  50. [50]

    Wojciech Kazana and Luc Segoufin , title =. Log. Methods Comput. Sci. , volume =

  51. [51]

    Nofar Carmeli and Luc Segoufin , title =

  52. [52]

    De la pertinence de l'

    Johann Brault. De la pertinence de l'

  53. [53]

    Holger Dell and Marc Roth and Philip Wellnitz , title =

  54. [54]

    Fan and Paraschos Koutris and Hangdong Zhao , title =

    Austen Z. Fan and Paraschos Koutris and Hangdong Zhao , title =

  55. [55]

    Mihalis Yannakakis , title =

  56. [56]

    It's All a Matter of Degree - Using Degree Information to Optimize Multiway Joins , journal =

    Manas Joglekar and Christopher R. It's All a Matter of Degree - Using Degree Information to Optimize Multiway Joins , journal =

  57. [57]

    Ngo and Ely Porat and Christopher R

    Hung Q. Ngo and Ely Porat and Christopher R. Worst-case Optimal Join Algorithms , journal =

  58. [58]

    Veldhuizen, Todd L , title =

  59. [59]

    Ngo and Christopher R

    Hung Q. Ngo and Christopher R. Skew strikes back: new developments in the theory of join algorithms , journal =

  60. [60]

    Size Bounds and Query Plans for Relational Joins , journal =

    Albert Atserias and Martin Grohe and D. Size Bounds and Query Plans for Relational Joins , journal =

  61. [61]

    Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries , journal =

    D. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries , journal =

  62. [62]

    Ngo and Dan Suciu , title =

    Mahmoud Abo Khamis and Hung Q. Ngo and Dan Suciu , title =

  63. [63]

    Ngo and Dan Suciu , title =

    Mahmoud Abo Khamis and Hung Q. Ngo and Dan Suciu , title =. TheoretiCS , volume =

  64. [64]

    PANDAExpress: a Simpler and Faster PANDA Algorithm

    Mahmoud Abo Khamis and Hung Q. Ngo and Dan Suciu , year =. 2512.10217 , archivePrefix =

    work page internal anchor Pith review Pith/arXiv arXiv

  65. [65]

    2026 , eprint =

    Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time , author =. 2026 , eprint =

    2026