Pith. sign in

REVIEW 5 major objections 3 minor 20 references

Counting Patterns in Degenerate Graphs in Constant Space

T0 review · 5 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new graph parameter, DAG treedepth, lets pattern occurrences in sparse graphs be counted in O(n^t) time using constant memory.

desk verdict The DAG treedepth parameter and its obstruction set are genuinely new, but the paper's main algorithm is broken: Theorem 4's proof misanalyzes Algorithm 1, and a star pattern is a concrete counterexample to the claimed O(n^t) bound. read the letter →

arxiv 2511.04258 v2 pith:UXX2KT6S submitted 2025-11-06 cs.DS

Balagopal Komarath , Anant Kumar , Akash Pareek This is my paper · ORCID
classification cs.DS MSC 05C3005C8568Q25
keywords DAGtreedepthtreewidthhomomorphismcountingsubgraphinduceddegenerategraphsconstant-spacealgorithmsminorobstructions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper's central proposal is a new graph parameter, DAG treedepth (dtd), defined for acyclic orientations of a pattern graph. It shows that if a k-vertex pattern H has dtd t, then all homomorphisms from H to an n-vertex, d-degenerate graph can be counted in O(n^t) time using only constant memory (Theorem 4). A divide-and-conquer recursion over a DAG elimination forest carries the argument, and the constant-space property follows because each recursion level stores only a bounded amount of state. Building on this, the paper gives an induced-minor characterization of patterns with dtd at most two (the graphs C6, P7, H1, H2), proves that all patterns up to nine vertices can be counted as induced subgraphs in O(n^3) time and constant space, and improves the DAG-treewidth-based exponent for induced-subgraph counting from k/4 to k/5 using polynomial space. If correct, this means pattern counting in sparse networks no longer requires memory that scales with the network size.

What carries the argument

DAG treedepth (dtd) is defined via a DAG elimination forest: recursively pick a source vertex, delete it together with all vertices reachable from it, and recurse on the remaining components; the parameter is the minimum possible depth. This is the direct analogue of treedepth but with the deletion step removing an entire reachability cone. The parameter matters because it drives Algorithm 1, a constant-space divide-and-conquer recursion that counts homomorphisms by branching over source images and multiplying counts over disjoint subtrees. The paper also uses the spasm identity (subgraph counts as linear combinations of homomorphism counts) and a graph family G_S built by contracting non-so

What would settle it

Run Algorithm 1 on the pattern K_{1,m} oriented with all leaves as sources and the host as an n-leaf star (1-degenerate). Count the total number of partial-extension iterations over all calls. If this total grows as Ω(n^m) rather than as a function of m and d only, then the claimed O(n^t) constant-space bound fails for this pattern.

Watch

Extended reading notes

Core claim

The paper claims that DAG treedepth is the right parameter for constant-space pattern counting in degenerate graphs. Theorem 4 states that counting homomorphisms from a k-vertex pattern with DAG treedepth t into an n-vertex d-degenerate graph can be done in O(n^t) time in constant space. The algorithm works by recursively picking a source vertex, enumerating all extensions of the current partial homomorphism to that source and everything reachable from it, and multiplying the counts for independent subtrees. From this single mechanism the paper derives constant-space algorithms for counting subgraphs and induced subgraphs, a DAG-treedepth-two obstruction set, the nine-vertex cubic-time bound

Load-bearing premise

The central algorithm assumes that, for each source vertex, the number of distinct ways to extend the current partial mapping to that source and all vertices reachable from it depends only on the pattern size and host degeneracy; on star patterns mapped into star hosts, this iteration count can grow with the host size, so the premise is not safe in general.

Editorial extensions

If this is right

  • Every pattern with bounded DAG treedepth can be counted in sparse host graphs in polynomial time with constant space, so pattern counting no longer needs per-instance memory.
  • All induced subgraph patterns on at most nine vertices are countable in O(n^3) time and constant space.
  • All patterns on at most eleven vertices have DAG treewidth at most two, giving quadratic-time counting with polynomial space.
  • The constant-space algorithm for induced subgraphs matches Bressan's DAG-treewidth running time while using O(1) rather than polynomial space.
  • Subgraph counting for ℓ-edge patterns runs in O(n^{⌊ℓ/5⌋+3}) time and constant space, improving the previous exponent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The star-pattern counterexample suggests the constant-space recursion is not the whole story: patterns with many sources and a single non-source (stars) are easy to count but may have unbounded extension cost under Algorithm 1, so a complete dichotomy likely needs a second mechanism beyond dtd.
  • If the k/5 bound for DAG treewidth generalizes, the ten-vertex hardness construction may be sharp, pointing to a fine-grained boundary between quadratic and subquadratic pattern counting in degenerate graphs.
  • The induced-minor characterization for dtd ≤ 2 mirrors the DAG-treewidth-one results and may support an induced-minor-based dichotomy for constant-space counting, analogous to the linear-time dichotomy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 3 minor

Summary. The paper introduces a new pattern parameter, DAG treedepth (dtd), and proposes constant-space divide-and-conquer algorithms for counting homomorphisms, subgraphs, and induced subgraphs in n-vertex, d-degenerate host graphs. The headline claims are Theorem 4 (an O(n^t)-time, O(1)-space homomorphism-counting algorithm when dtd(H)=t), the derived constant-space bounds for hom/sub/ind counting (Theorems 5, 6, 23, 25), an induced-minor characterization of dtd<=2 (Theorem 7 / Theorem 17), an O(n^3) constant-space result for all patterns on at most nine vertices (Theorem 10), and an improvement of Bressan's induced-subgraph exponent to k/5+O(1) with polynomial space (Theorems 13 and 32). The paper also claims an affirmative resolution of Conjecture 3 of [PPS24] and gives an XP algorithm for deciding dtd(H)<=k. Several other results are conditional on the paper's Conjectures 1 and 2.

Significance. If the main results were correct, the paper would be a substantial contribution: it would replace Bressan's polynomial-space dynamic programming for degenerate-host pattern counting with constant-space algorithms at the same or better running times, and it would give the first induced-minor characterization in this regime. The paper does contain some useful ingredients: Algorithm 2 gives a plausible XP verification procedure for dtd, and the lemmas relating dtd and dtw to treedepth/treewidth of the associated graph family may be of independent interest. However, the central algorithmic claim rests on a cost analysis that is demonstrably incorrect, and several of the headline structural and algorithmic results are either conditional on unproven assumptions or supported only by informal case arguments. I cannot certify any of the main constant-space bounds as stated.

major comments (5)
  1. [§3, Theorem 4 and Algorithm 1, line 4] The proof of Theorem 4 asserts that the loop on line 4 over all sigma' extending sigma to {v} union R(v) has at most g(k,d) iterations because 'there are at most d outgoing edges from any vertex in H'. This is invalid: the loop ranges over all choices of images for the vertices in R(v), and |R(v)| is not bounded by d. Concretely, let H be the complete bipartite graph K_{2,b} oriented with two sources s1,s2, both reaching the same b non-source vertices. Then dtd(H)=2: delete s1 and all b non-sources, leaving isolated s2. At the root s1, R(s1) contains b vertices, so line 4 enumerates n choices for sigma(s1) times n^b choices for the non-source images, i.e. n^{b+1} iterations. For b=3 this is Omega(n^4), contradicting the promised O(n^2). No aggregation mechanism is provided. This invalidates Theorem 4 and consequently the derived bounds in Theorems 5, 6, 10, 23, and 25.
  2. [§3, Algorithm 1, lines 5 and 10] There is a separate correctness bug in the same algorithm. Inside the line-4 loop, the variable p is reset to 1 for every sigma' and then overwritten on the next iteration. After the loop, line 10 adds only the product belonging to the last extension sigma', not the sum over all extensions. The algorithm as written therefore does not compute the number of homomorphisms. One would need an inner accumulator q and an addition of q to c for each sigma' before the next iteration.
  3. [§4.2, 'Proof of Conjecture 3'] The paper states in Section 1.1 that it provides an affirmative answer to Conjecture 3 of [PPS24], but the proof in Section 4.2 begins: 'Our proof relies on the assumption from [KKMS23], which states that there is no combinatorial algorithm of time o(m^2) to count copies of K4.' That makes the result conditional on an unproven lower bound, not an unconditional resolution of the conjecture. Moreover, [KKMS23] shares two authors with the present paper, so the assumption is not independent. The wording in the introduction ('Hence, we provide an affirmative answer to the conjecture') is therefore misleading.
  4. [§4.2, Corollary 3 and Theorem 32] Corollary 3 is unsupported. Lemma 12 gives dtw(H) <= t/5.217 + 4. The corollary says: 'The additive term +4 arises only when using Lemma 12, which divides by 5.217. If we divide by 5, so in practice, using +3 is sufficient. Hence, dtw(H) <= k/5 + 3.' This is not a proof: changing the denominator from 5.217 to 5 makes the main term larger, not smaller, and no argument is given that the additive constant drops from 4 to 3. Since Theorems 13 and 32 rely on this corollary, the claimed k/5 improvement over Bressan's bound is not established.
  5. [§3.2, Theorem 17] The proof of the dtd<=2 induced-minor characterization is an informal case analysis. It repeatedly uses phrases such as 'we can check', 'it forms a structure', and 'One can identify' without giving a complete, verifiable argument that C6, P7, H1, H2 are exactly the induced-minor obstructions. Since this characterization is advertised as a main structural result (Theorem 7), the proof as written is not sufficient. A rigorous argument, or a machine-checked exhaustive case analysis, would be needed.
minor comments (3)
  1. [Throughout] The manuscript contains many typos and nonsensical phrases, e.g. 'The prove follows' (Theorem 26), 'Therefore' typo in Section 1, and inconsistent citation labels such as [BPS21]/[BPS19]/[PPS25b]. The text would need careful copyediting.
  2. [§3, Theorem 15, Claim 2] In the proof of Claim 2, the text says 'Let T be a DAG elimination tree of width at most k' but should say 'depth at most k'. Similar depth/width mixing appears elsewhere.
  3. [§4.2, Theorem 29] The proof of Theorem 29 treats selected cases (5, 6, and 7 sources) and ends with 'The remaining cases are also similar to the prove.' Since the theorem is used for all patterns with up to 11 vertices, the omitted cases need to be spelled out.

Circularity Check

1 steps flagged · score 4.0 of 10

Conjecture 3 is 'answered' only via a K4-hardness assumption from the authors' own prior paper; core DAG-treedepth results are independent.

  1. self citation load bearing [Section 4.2, Proof of Conjecture 3]
    "Our proof relies on the assumption from [KKMS23], which states that there is no combinatorial algorithm of time o(m^2) to count copies of K 4 ([KKMS23])."

    KKMS23 is co-authored by two of the present authors (Komarath and Kumar). The claimed 'affirmative answer' to Conjecture 3 is exactly the conditional consequence of this unproven K4-hardness assumption, and the paper presents it as a resolution ('Hence, we provide an affirmative answer to the conjecture'). The load-bearing evidence is therefore a self-citation that is itself an unverified assumption, not an independent external result.

full rationale

Most of the paper's derivation is self-contained: Theorem 4 introduces Algorithm 1 and the O(n^t) bound follows from the stated DAG-elimination-tree recursion; Theorems 22 and 24 prove dtd <= k/4+2 and dtd <= l/5+3 by explicit elimination-tree constructions; Theorem 7's obstruction set is argued from the definition of DAG treedepth. I do not see any fitted parameter being relabeled as a prediction, nor any definition that presupposes the target bound. The one genuine circularity is the 'Proof of Conjecture 3': the paper claims to affirmatively resolve [PPS24]'s conjecture, but the proof states it 'relies on the assumption from [KKMS23]' that no o(m^2) combinatorial algorithm counts K4, and [KKMS23] is by two of the present authors. That is a load-bearing self-citation of an unproven assumption, so the advertised 'answer' is conditional rather than derived. Theorems 8-9 similarly depend on the authors' own Conjectures 1-2, though these are explicitly labelled as assumptions and hence not hidden circularity. Separately, the proof of Theorem 4 contains a serious non-circular correctness gap: line 4's claim of only g(k,d) extensions is inconsistent with the n^{|R(v)|} possible assignments (e.g., a star pattern on a star host), and Corollary 3's '+3' bound is asserted rather than proved. These affect validity, not circularity, so I keep the score at 4 rather than higher.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No data fitting is performed; k and d are fixed constants absorbed into f(k,d). The conjectures are not fitted parameters.

assumptions (6)
  • ad hoc to paper For every node v in a DAG elimination tree, Algorithm 1 can iterate over all partial homomorphism extensions to {v} ∪ R(v) in at most g(k,d) time/space.
    Stated in the proof of Theorem 4 ('the loop in line 4 can only have g(k,d) many iterations'). False for star patterns, since a source may reach many non-sources and a d-degenerate host can contain a vertex of degree n-1.
  • ad hoc to paper Conjectures 1 and 2 of this paper hold.
    Theorems 8 and 9 are proved conditional on these unproved conjectures in §3.3; the abstract does not flag the conditionality.
  • domain assumption There is no combinatorial o(m^2)-time algorithm for counting/detecting K4, as assumed in [KKMS23].
    Used in §4.2 to answer Conjecture 3 from [PPS24]; the referenced result is an unproved assumption from the authors' own prior work.
  • standard math Spasm identity (Curticapean–Dell–Marx): sub(H,G) is a linear combination of hom(H',G) over H' in Spasm(H).
    Used throughout to route subgraph and induced-subgraph counting through homomorphism counting (§2).
  • standard math Treewidth of any m-edge graph is at most m/5.217 + 3 (Kneis et al. 2005).
    Used in Lemma 12 to bound DAG treewidth in terms of the number of source vertices.
  • domain assumption Any d-degenerate graph admits an acyclic orientation with outdegree at most d, and d is treated as a constant.
    Standard degeneracy-ordering fact; all runtime bounds absorb d into the hidden function.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Counting Patterns in Degenerate Graphs in Constant Space." pith.science (2026). https://pith.science/paper/UXX2KT6S

@misc{pith2026251104258,
  author       = {Pith},
  title        = {Pith review of: Counting Patterns in Degenerate Graphs in Constant Space},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UXX2KT6S}},
  note         = {Machine review of arXiv:2511.04258}
}
abstract

For a fixed pattern graph, we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms into an $n$-vertex, $d$-degenerate host graph. Bressan (Algorithmica, 2021) introduced the notion of DAG treewidth and showed that counting homomorphisms and induced subgraphs can be performed efficiently using dynamic programming that requires polynomial space. In this work, we introduce a new graph parameter, called DAG treedepth, which enables efficient divide-and-conquer algorithms for counting homomorphisms in $d$-degenerate host graphs using only constant space. Bera, Gishboliner, Levanzov, Seshadhri, and Shapira (SODA, 2021) showed that a pattern graph has DAG treewidth one if and only if it contains no induced cycle of length at least six. This induced minor characterization leads to linear-time and linear-space algorithms. Building on this line of work, we derive an induced-minor characterization of graphs with DAG treedepth at most two that uses only constant space. Recently, Paul-Pena and Seshadhri (ICALP, 2025) proved that all pattern graphs on at most nine vertices can be counted in subquadratic time using polynomial space. We show that every pattern graph on at most nine vertices can be counted as an induced subgraph in $O(n^3)$ time using only constant space. Moreover, we show that patterns on at most eleven vertices can be counted in $O(n^2)$ time using polynomial space. Finally, we present a constant-space algorithm for counting induced subgraphs that matches the running time of Bressan algorithm. We further show that, when polynomial space is allowed, homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms can be counted faster than Bressan algorithm. In addition, we establish several other results related to DAG treewidth and DAG treedepth that may be of independent interest.

Figures

Figures reproduced from arXiv: 2511.04258 by the authors.

Figure 1
Figure 1. The black nodes are sources and the white nodes are non-sources. In figure (a), the DAG [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. H1 and H2 are obstruction for DAG treedepth 2. In the next two lemmas, we now give relations between the obstructions of treedepth and DAG treedepth. Let Hsub be the graph obtained by subdividing each edge of H exactly once. Then we have the following lemma. Lemma 5 Let H be a minor obstruction for treedepth k − 1. Then dtd(Hsub) = k. Proof Let T be an elimination tree of H with depth k. Suppose, for contradiction, … view at source ↗
Figure 3
Figure 3. k4 with one subdivision We now derive the following lemma, which will help us to show that for a DAG with k vertices, dtw(H) ≤ k 5 + 4. We then do further refinement to show that dtw(H) ≤ k 5 + 3. Lemma 12 Given a DAG H with t source vertices such that the reachability of every source vertex is bounded by 2, we have dtw(H) ≤ t 5.217 + 4. Proof We construct a graph G where each vertex corresponds to a non-source vert… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 1 canonical work pages

  1. [18]

    The Complexity of Counting Small Sub-Hypergraphs.arXiv preprint arXiv:2506.14081,

    [BBDRW25] Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, and Philip Wellnitz. The Complexity of Counting Small Sub-Hypergraphs.arXiv preprint arXiv:2506.14081,

    arXiv

  2. [19]

    Seshadhri

    [PPS25b] Daniel Paul-Pena and C. Seshadhri. Near-linear time subhypergraph counting in bounded degeneracy hypergraphs.arXiv preprint arXiv:2510.16330,

    arXiv

  3. [20]

    General and fractional hypertree decomposi- tions: Hard and easy cases

    [FGP18] Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler. General and fractional hypertree decomposi- tions: Hard and easy cases. InProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 17–32, 2018

    2018

  4. [1968]

    [GR93] Jim Gray and Andreas Reuter.Transaction Processing: Concepts and Techniques

    doi:10.1145/362929.362947. [GR93] Jim Gray and Andreas Reuter.Transaction Processing: Concepts and Techniques. Morgan Kaufmann,

    arXiv

  5. [1974]

    [Di68] Edsger W

    doi:10.1145/361604.361612. [Di68] Edsger W. Dijkstra. Letters to the editor: go to statement considered harmful.Communications of the ACM, 11(3):147–148,

    arXiv

  6. [1975]

    [FPT08] Fedor V

    doi:10.1109/SFCS.1975.23. [FPT08] Fedor V . Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Approximating acyclicity parameters of sparse hypergraphs.arXiv preprint arXiv:0809.3646,

    arXiv 1975

  7. [1993]

    Hopcroft, Wolfgang J

    [HPV75] John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant. On Time versus Space and Related Problems. In16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, pages 57–64. IEEE,

    1975

  8. [1994]

    Bera, Noujan Pashanasangi, and C

    [BPS19] Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Linear time subgraph counting, graph degeneracy, and the chasm at size six.arXiv preprint arXiv:1911.05896,

    arXiv 1911

Show all 20 references
  1. [1997]

    [CDM17] Radu Curticapean, Holger Dell, and D ´aniel Marx

    doi:10.1007/BF02523189. [CDM17] Radu Curticapean, Holger Dell, and D ´aniel Marx. Homomorphisms are a good basis for counting small subgraphs. InProceedings of STOC 2017, pages 210–223,

    2017 doi

  2. [2001]

    Seshadhri

    [Ses23] C. Seshadhri. Some vignettes on subgraph counting using graph orientations (invited talk). In26th International Conference on Database Theory (ICDT 2023), pages 3–1,

    2023

  3. [2002]

    [Kn74] Donald E

    doi:10.1016/S0304-3975(02)00017-8. [Kn74] Donald E. Knuth. Computer Programming as an Art.Communications of the ACM, 17(12):667–673,

    doi

  4. [2015]

    Seshadhri

    [PPS22] Daniel Paul-Pena and C. Seshadhri. A dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs.arXiv preprint arXiv:2211.08605,

    arXiv

  5. [2017]

    [B25] ´Edouard Bonnet

    doi:10.1145/3055399.3055502. [B25] ´Edouard Bonnet. Treewidth inapproximability and tight eth lower bound. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2130–2135,

  6. [2019]

    Efficiently finding and counting patterns with distance constraints in sparse graphs

    [LPSXZ25] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Efficiently finding and counting patterns with distance constraints in sparse graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1965–1974,

    1965

  7. [2020]

    Finding and counting patterns in sparse graphs

    [KKMS23] Balagopal Komarath, Anant Kumar, Suchismita Mishra, and Aditi Sethia. Finding and counting patterns in sparse graphs. In40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 40–1,

    2023

  8. [2021]

    Algorithms based on the treewidth of sparse graphs

    [KMRR05] Joachim Kneis, Daniel M ¨olle, Stefan Richter, and Peter Rossmanith. Algorithms based on the treewidth of sparse graphs. InGraph-Theoretic Concepts in Computer Science: 31st International Workshop, WG 2005, pages 385–396. Springer,

    2005

  9. [2022]

    [PPS24] Daniel Paul-Pena and C

    doi:10.1145/3520240. [PPS24] Daniel Paul-Pena and C. Seshadhri. Subgraph counting in subquadratic time for bounded degeneracy graphs.arXiv preprint arXiv:2410.08376,

    arXiv

  10. [2023]

    Bera, Noujan Pashanasangi, and C

    [BPS21] Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: The barrier of long induced cycles. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2315–2332. SIAM,

    2021

  11. [2024]

    Seshadhri

    [PPS25] Daniel Paul-Pena and C. Seshadhri. A dichotomy hierarchy for linear time subgraph counting in bounded degeneracy graphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 48–87. SIAM,

    2025

  12. [2025]

    Counting homomorphic cycles in degenerate graphs

    [GLYS22] Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, and Raphael Yuster. Counting homomorphic cycles in degenerate graphs. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 417–430,

    2022

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.