{"id":"a8d3566a-cc09-4164-bcef-a3e46d66cd6f","arxiv_id":"2511.04258","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims constant-space, DAG-treedepth-based pattern counting in degenerate graphs, but the flagship algorithm's time bound is contradicted by a star-pattern counterexample.","lead":"This paper introduces DAG treedepth, a new graph parameter intended to yield constant-space algorithms for counting small patterns in sparse networks. The central algorithm's time proof, however, fails on simple star patterns, so the main results do not follow as written.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's proof relies on a false bounded-extension claim for Algorithm 1: line 4 can enumerate n^{|R(v)|} assignments, not g(k,d), so the O(n^t) bound is unsupported.","rationale":"The reader's weakest assumption is exactly the fatal step. I independently traced the proof of Theorem 4: the induction establishes correctness only if line 4's enumeration is well-defined and cheap; the only cost argument is the sentence claiming g(k,d) iterations. That sentence is false. The all-leaves-as-sources star is a clean witness: DAG treedepth is 2, yet the algorithm as written enumerates Ω(n^{m+1}) partial extensions. This is not a missing edge case but a systematic cost leak in the proposed divide-and-conquer recursion. Because Theorems 5, 6, 10, 23, and 25 all invoke Theorem 4 for their running times, the constant-space algorithmic results inherit the gap. There is no machine-checked proof, no shipped code, and no independent verification that could offset this. I also note that lines 5 and 10 appear to overwrite p rather than summing over extensions, which would be an additional correctness defect, but the cost concern is sufficient to reject the paper's central claim. Structural results, such as the induced-minor obstructions for dtd≤2, may still be salvageable, but the main algorithmic contribution is not established by this manuscript.","tokens_in":33679,"tokens_out":12548,"duration_ms":116999,"concrete_test":"Implement Algorithm 1 exactly as written, with a counter incremented on every iteration of line 4. Run it for H = K_{1,3} oriented with the three leaves as sources and the center as the unique non-source, on an n-vertex star host. The proof of Theorem 4 predicts O(n^2) total line-4 iterations; the literal algorithm performs Θ(n^4). If this count is confirmed, the bounded-extension premise in the proof of Theorem 4 is false, and the theorem requires a different algorithmic argument or a corrected bound.","verdict_should_be":"REJECT","load_bearing_attack":"The central algorithmic claim is Theorem 4, and its proof is the only substantiation offered for the constant-space counting bounds in Theorems 5, 6, 10, 23, and 25. The proof fails at the cost analysis of Algorithm 1, line 4: 'for all σ′ extending σ to {v} ∪ R(v) such that σ′(v)=u'. Here R(v) is the set of non-source vertices reachable from v in the pattern DAG, and each such vertex may be mapped to any of the n host vertices. The proof asserts this loop has only g(k,d) iterations because 'there are at most d outgoing edges from any vertex in H' and paths in H have length at most k. That confuses the host degeneracy d with a bound on the pattern's outdegree; even if H had bounded outdegree, the number of partial homomorphism extensions to r unmapped vertices is generally n^r, not g(k,d). Concretely, let H be the star K_{1,m} oriented with all m leaves as sources and the center as the unique non-source. Then dtd(H)=2, and on an n-vertex star host (a 1-degenerate graph), the root leaf's line-4 loop enumerates n choices for the center, and the recursive calls for the other m-1 leaves each enumerate n choices for the leaf image, giving Θ(n^{m+1}) executions of line 4. Theorem 4 promises O(n^2). The pseudocode also overwrites p in lines 5 and 10 instead of accumulating over the line-4 iterations, but the cost gap alone is already fatal: the paper does not provide any aggregation mechanism that would replace this enumeration, and no such mechanism is described in the proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":34155,"tokens_out":9002,"duration_ms":82832,"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":[{"comment":"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.","section":"§3, Theorem 4 and Algorithm 1, line 4"},{"comment":"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.","section":"§3, Algorithm 1, lines 5 and 10"},{"comment":"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.","section":"§4.2, 'Proof of Conjecture 3'"},{"comment":"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.","section":"§4.2, Corollary 3 and Theorem 32"},{"comment":"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.","section":"§3.2, Theorem 17"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"§3, Theorem 15, Claim 2"},{"comment":"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.","section":"§4.2, Theorem 29"}],"recommendation":"reject","confidential_remarks":"The decisive issue is Theorem 4's cost analysis. The K_{2,b} example shows that a fixed pattern with dtd=2 can force n^{Omega(k)} iterations in the proposed recursion, so the advertised O(n^t) bound is not merely missing a detail: the divide-and-conquer scheme as described does not achieve it. The conditional 'resolution' of Conjecture 3 and the unsupported Corollary 3 add further concerns. These are load-bearing problems, not presentation issues, and I do not see a repair that stays within the manuscript's stated scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"New parameter, broken main proof. DAG treedepth is a natural idea, and the induced-minor obstruction set for dtd≤2 is a real, citable contribution. But Theorem 4, the engine of the paper, is not proved. The proof asserts that line 4 of Algorithm 1 can only run g(k,d) times because the host is d-degenerate. That confuses the pattern's outdegree with the host's degeneracy. The loop enumerates all partial homomorphisms extending to {v} ∪ R(v); each vertex in R(v) has, in general, n possible images. A star K_{1,m} with the m leaves as sources and the center as the single non-source has dtd=2, yet on any host the recursion explores n choices for the center and n choices for each remaining leaf, so Ω(n^m) work for the root call alone. This directly contradicts the promised O(n^2). The stress-test note is correct, and the counterexample is enough to sink the theorem as stated.\n\nSince Theorems 5, 6, 10, 23, and 25 all lean on Theorem 4, the algorithmic claims fall with it. There are other soft spots worth naming: the proofs of Theorems 22 and 24 are sketches, with the residual cases hand-waved; Corollary 3's jump from +4 to +3 is asserted, not derived; and the answer to Conjecture 3 is conditional on an unproven K4-hardness assumption from the authors' own earlier paper, so calling it an \"affirmative answer\" overstates it.\n\nCredit where it is due: the dtd parameter itself, the XP membership for dtd≤k, the obstruction set {C6, P7, H1, H2}, and the tree-depth sandwiching results are plausible and may well survive a rewrite. A focused paper on those would be worth reading.\n\nWho is this for: people working on subgraph counting in degenerate graphs. But in the present form, I would not trust any of the headline running times. If I were the editor, I would still send it to a referee: the structural sections deserve expert scrutiny, and the main theorem's failure is instructive enough to justify referee time. I would expect either heavy revision or the authors splitting off the structural material.","headline":"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.","tokens_in":34617,"tokens_out":4518,"would_cite":false,"duration_ms":41471,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C30","05C85","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new graph parameter, DAG treedepth, lets pattern occurrences in sparse graphs be counted in O(n^t) time using constant memory.","keywords":["DAG treedepth","DAG treewidth","homomorphism counting","subgraph counting","induced subgraph counting","degenerate graphs","constant-space algorithms","induced minor obstructions"],"falsifier":"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.","tokens_in":33550,"feed_emoji":"🧮","tokens_out":4861,"duration_ms":42139,"temperature":0.7,"pith_summary":"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.","feed_headline":"One new parameter makes pattern counting constant-space","feed_subtitle":"DAG treedepth, a treedepth analogue for DAGs, yields cubic-time counting for all patterns up to nine vertices with no extra memory.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Constant space counting for all patterns up to 9 vertices","One parameter, zero extra memory: pattern counting in cubic time","DAG treedepth unlocks constant-space pattern counting","Pattern counting without extra memory: the power of DAG treedepth","From polynomial to constant space: pattern counting gets a new trick"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Constant space counting for all patterns up to 9 vertices","One parameter, zero extra memory: pattern counting in cubic time","DAG treedepth unlocks constant-space pattern counting","Pattern counting without extra memory: the power of DAG treedepth","From polynomial to constant space: pattern counting gets a new trick"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000207,"raw_usage":{"total_tokens":1326,"prompt_tokens":923,"completion_tokens":403,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":667,"completion_tokens_details":{"reasoning_tokens":332}},"tokens_in":667,"tokens_out":403,"duration_ms":4501,"temperature":1.0,"reasoning_tokens":332,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T23:45:37.681901+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}