{"id":"04e2ed0f-e40f-47cc-a80e-cb89ed210ec6","arxiv_id":"2506.14081","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Counting non-induced sub-hypergraphs is fixed-parameter tractable exactly for families with bounded fractional co-independent edge-cover number, and induced counting exactly for bounded fractional edge-cover number, assuming ETH.","lead":"This paper classifies when counting small hypergraph patterns inside large hypergraphs is computationally tractable. It shows the boundary is governed by two new fractional edge-cover parameters, and that hypergraphs behave differently from graphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound proofs hinge on the unproved integrality-gap Lemma 3.11, and its application in Eq. 18 drops the factor 4; if that external lemma has hidden hypotheses, Main Theorems 1 and 2 collapse.","rationale":"The reader's weakest-assumption diagnosis is correct: Lemma 3.11 is the least locally justified premise of the lower-bound proofs. Both main theorems depend on it at the exact transition from structural parameters to adaptive width. The paper restates the lemma without proof, applies it with a dropped factor 4, and does not address edge cases such as singleton edges introduced by trimming. This is a genuine, but not disconfirming, concern: the lemma is a published result, and the factor-4 discrepancy is likely a typo that does not affect the asymptotic argument. The rest of the central construction, including the homomorphism basis, Dedekind interpolation, the quotient-cover inequalities, and the Ramsey/König amplification, is internally coherent as far as I checked. Therefore the reader's conditional verdict is appropriate, and no verdict change is warranted.","tokens_in":40824,"tokens_out":37598,"duration_ms":406479,"concrete_test":"Verify Lemma 3.11 independently: locate BLR23 Theorem 17, re-derive its proof, and confirm it applies to unbounded-rank hypergraphs under the paper's convention that isolated vertices receive singleton edges. As a computational cross-check, enumerate all hypergraphs on at most 4 vertices and a random sample of 10^5 hypergraphs on 5–8 vertices; for each, compute α by brute force, α* by linear programming, and aw by enumerating fractional independent sets and tree decompositions, then test α ≥ 1/2 + α*/(4·aw). The test must include hypergraphs with singleton edges and isolated vertices, since H⟨X⟩ in Lemma 5.8 can contain them even when H does not. A single counterexample, or a missing hypothesis in the external theorem, would invalidate Lemmas 5.8 and 5.17.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central dichotomy rests on Lemmas 5.8 and 5.17. In the bounded-adaptive-width case, both invoke Lemma 3.11 (BLR23, Theorem 17): for every hypergraph H, α(H) ≥ 1/2 + α*(H)/(4·aw(H)). This is the step that converts unbounded σ* or ρ* into arbitrarily large independent sets, which are then amplified by the Ramsey/König argument into high-treewidth graph quotients and hence into hardness of homomorphism counting. The lemma is not proved or adapted in this paper; it is only cited. Moreover, the application in Lemma 5.8 (displayed Eq. 18) writes α(H⟨X⟩) ≥ 1/2 + α*(H⟨X⟩)/aw(H⟨X⟩), silently omitting the factor 4 from the denominator. That omission is asymptotically harmless, but it shows that the exact statement and hypotheses of the external result were not checked during the proof. If the true theorem requires rank-bounded hypergraphs, or excludes hypergraphs with singleton edges, or has a different constant or condition, then the derivation of a large independent set in H⟨X⟩ fails, and with it the hardness direction of both main theorems. This is the precise point where the unconditional structural hypotheses (unbounded σ* or ρ*) are converted into the width-based hardness criteria of Marx, so it is the most load-bearing step in the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized complexity of counting small sub-hypergraphs and induced sub-hypergraphs, parameterized by the number of vertices of the pattern. It introduces a new parameter, the fractional co-independent edge-cover number σ*, and proves two dichotomies assuming ETH: #Sub(H) is FPT iff σ* is bounded on H, and #IndSub(H) is FPT iff the fractional edge-cover number ρ* is bounded on H. The technical machinery includes a hypergraph version of the homomorphism basis, a suitable tensor product for Dedekind interpolation, and an analysis of adaptive width of quotients and edge-superhypergraphs. The paper also shows that the FPT cases can be genuinely hard: #Sub can be #P-hard despite being FPT, and #IndSub admits only quasi-polynomial time unless Graph Isomorphism is in P. A final section studies trimmed sub-hypergraphs and shows that the natural trimmed homomorphism basis does not satisfy complexity monotonicity.","tokens_in":41053,"tokens_out":38693,"duration_ms":396614,"significance":"If the main theorems are correct, this is a substantial contribution: it provides the first complete parameterized complexity dichotomies for counting small sub-hypergraphs of unbounded rank, subsuming the known graph classifications as special cases. The lifting of the homomorphism-basis and complexity-monotonicity framework from graphs to unbounded-rank hypergraphs is technically nontrivial and likely to be reused. The paper is also careful to expose the source of hardness: the FPT cases are shown to be nonetheless #P-hard or quasi-polynomial-time, which is an honest and informative separation from the graph setting. The proof structure is largely transparent, and the main reductions are spelled out in detail; the main theorems rest on established external results on hypergraph homomorphism counting and on an integrality-gap lemma of Bressan, Lanzinger, and Roth.","major_comments":[{"comment":"The displayed application of Lemma 3.11 in Eq. (18) writes α(H⟨X⟩) ≥ 1/2 + α*(H⟨X⟩)/aw(H⟨X⟩), omitting the factor 4 that Lemma 3.11 places in the denominator. This inequality is the mechanism by which unbounded σ*(H) is converted into an arbitrarily large independent set, so the lower-bound direction of Main Theorem 1, and the analogous step in Lemma 5.17 for Main Theorem 2, depends on the exact statement. Please correct the constant and confirm that Lemma 3.11 applies at the stated level of generality, in particular to hypergraphs with isolated vertices under Remark 3.5 and to trimmed induced subhypergraphs H⟨X⟩.","section":"§5.1, Eq. (18)"},{"comment":"The hypergraph H⟨R∪I⟩ may contain singleton edges {v}, arising from original hyperedges whose intersection with R∪I is a single vertex. Such a hypergraph is not a bipartite graph in the usual sense, and a matching consisting of singleton edges would not yield the large-treewidth quotient needed in Claim 5.10. The proof should apply König's theorem to the bipartite graph formed by the size-2 edges between R and I, noting that singleton edges play no role in the co-independence argument; as written, the claim and its subsequent use of Lemma 5.7 are not fully justified.","section":"§5.1, Claim 5.9"},{"comment":"The statement K_{α(H)} ∈ 𝒯(𝒮(H)) is not literally correct as written: if vertices of the independent set I lie in some edge of H, then H′⟨I⟩ also contains singleton edges, so the induced trimmed subhypergraph is not isomorphic to the 2-uniform clique K_{α(H)}. Please either state explicitly that the term 'graph' in Lemma 4.18 means a rank-at-most-2 hypergraph in which singleton edges are allowed, or modify the construction so that a genuine graph of treewidth α(H) appears in 𝒯(𝒮(H)). This is a load-bearing step in the bounded-adaptive-width case of Main Theorem 2.","section":"§5.2, Lemma 5.17"},{"comment":"The formula ∑_t C(n_t,k) overcounts #IndTrimSub(B_k→G) when G has isolated vertices: for t(v)=∅, the trimmed induced subhypergraph G⟨X⟩ has no edges and is not isomorphic to B_k for any k≥1, yet the sum contributes C(n_∅,k). This makes the proof of Theorem 6.5(2) incorrect as stated. The argument is repairable by summing only over non-empty types, so the polynomial-time claim survives, but the lemma as written needs correction.","section":"§6.1, Lemma 6.8"}],"minor_comments":[{"comment":"The notation for the quasi-polynomial running time is inconsistent: the statement says (ln ∥H∥)^{O(1)} while the proof uses (log ∥H∥)^{O(1)}; please use one convention throughout.","section":"Theorem 5.19"},{"comment":"In the first case of the proof, the sentence 'The claim then follows by Lemma 3.9' should cite Marx's hardness theorem for unbounded adaptive width rather than Lemma 3.9, which only records inequalities between width measures.","section":"Lemma 5.8"},{"comment":"For patterns with |F|=2, the added edge V(F) coincides with a possible graph edge of size 2, so the claimed bijection between induced copies and graph isomorphism needs a short separate argument for small patterns.","section":"Theorem 5.20"},{"comment":"There are several minor typographical issues, including 'Isomoprhism' in the statement of Theorem 5.20 and a reference to 'Sub(H→G)' in Section 2.5 where '#IndSub(H→G)' is meant.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main dichotomy results are valuable and likely correct, but the lower-bound proofs need careful repair: the missing factor 4 in Eq. (18), the treatment of singleton edges in Claim 5.9 and Lemma 5.17, and the overcounting in Lemma 6.8 should all be addressed. These are local and fixable, but they sit at load-bearing points, so I recommend major revision rather than acceptance in the current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers what it says: complete ETH-based dichotomies for #Sub and #IndSub on unbounded-rank hypergraphs. That is the first full classification in a setting where the graph criteria were known to fail, and it is genuinely new. The fractional co-independent edge-cover number sigma* is a useful contribution on its own, and the separations—#P-hard FPT cases, quasi-polynomial time for induced counting, and the reduction from Graph Isomorphism—are surprising and well worth knowing.\n\nI spot-checked the main machinery: the quotient cover-number inequalities (Lemma 5.3), the bipartite matching argument (Claim 5.9), the Ramsey step, and the transfer from homomorphism hardness to sub-hypergraph counting all look sound. The hypergraph tensor product and Dedekind interpolation are handled carefully, including the size blowup issue, which is the kind of detail that usually gets swept under the rug.\n\nTwo soft spots, both minor. First, the displayed inequality in Lemma 5.8 drops the factor 4 from the cited integrality gap Lemma 3.11. That is asymptotically harmless for the proof, since the lower bound still goes to infinity with s, but it is a clear typo that should be fixed. If the external lemma had hidden hypotheses the lower bound would need rechecking, but BLR23 states it for all hypergraphs and I see no reason to doubt it. Second, Lemma 6.8 overcounts: vertices with the empty type (isolated vertices) are included in the summation, but a set of isolated vertices yields no edges and cannot be isomorphic to B_k. Excluding the empty type fixes the argument; this affects only the secondary trimmed-subgraph counterexample, not the main theorems.\n\nI also want to say the citation practice is fine. The lower bounds rely on Marx, Grohe–Marx, and Neuen, and on the BLR23 integrality gap. Those are published, independent theorems, and the dependence is properly flagged. This is not a case of circularity.\n\nWho is this for? Anyone working on parameterized counting complexity, hypergraph algorithms, or conjunctive query counting. The new parameter and the trimmed counterexample will be reused. The main theorems deserve a careful referee, not a desk reject. I would send it out, with instructions to check Lemma 3.11's exact statement and to verify the fix for Lemma 6.8. After minor revision it should be a strong conference paper.","headline":"Main dichotomies for sub-hypergraph counting are real and the core proofs hold up; two small bugs in secondary statements are easy to patch.","tokens_in":41662,"tokens_out":3243,"would_cite":true,"duration_ms":34722,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C65","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Counting small sub-hypergraphs is tractable exactly when a fractional cover number is bounded.","keywords":["hypergraph counting","fractional edge cover","parameterized complexity","fixed-parameter tractability","Exponential Time Hypothesis","homomorphism basis","adaptive width","induced subhypergraph"],"falsifier":"To refute the dichotomy, exhibit a recursively enumerable family $\\mathcal{H}$ with $\\sigma^*(\\mathcal{H})=\\infty$ for which $\\#\\mathrm{Sub}(\\mathcal{H})$ is still fixed-parameter tractable, or a family with $\\rho^*(\\mathcal{H})=\\infty$ for which $\\#\\mathrm{IndSub}(\\mathcal{H})$ is still FPT; under ETH the theorems forbid both. A concrete spot to probe is the construction of Lemma 5.8: run it on the family of 4-uniform sunflowers with core size one and check whether the quotients it produces really contain graphs of unbounded treewidth — if the Ramsey step fails to produce such a quotient, the lower-bound chain breaks.","tokens_in":40570,"feed_emoji":"🧮","tokens_out":13212,"duration_ms":108968,"temperature":0.7,"pith_summary":"This paper gives the first complete complexity classification for the parameterized problem of counting how many times a small hypergraph $H$ appears inside a large hypergraph $G$, in both the ordinary and the induced sense. The dividing line is a single rational parameter: ordinary copies are counted in fixed-parameter time exactly when the fractional co-independent edge-cover number $\\sigma^*(\\mathcal{H})$ is bounded over the family $\\mathcal{H}$, and induced copies exactly when the fractional edge-cover number $\\rho^*(\\mathcal{H})$ is bounded. Both claims are conditional on the Exponential Time Hypothesis, and both subsume the previously known graph dichotomies as special cases. The proof works by writing copy counts as linear combinations of hypergraph homomorphism counts and then reducing the problem to known tractability and hardness results for homomorphism counting. The paper also shows that the easy cases are not trivial: some easy #Sub families are #P-hard, and the easy #IndSub families run in quasi-polynomial time unless Graph Isomorphism lies in P.","feed_headline":"Sub-hypergraph counting is easy exactly when a cover number is bounded","feed_subtitle":"New dichotomy: bounded fractional covers give fast counting; unbounded ones make it hard under ETH.","key_machinery":"The load-bearing object is the hypergraph homomorphism basis: every sub-hypergraph count and every induced sub-hypergraph count is expressed as a finite linear combination of homomorphism counts $\\#\\mathrm{Hom}(F \\to G)$, summed over quotients of $H$ and, for induced copies, over quotients of its edge-super-hypergraphs. Because the hypergraph tensor product multiplies homomorphism counts, $\\#\\mathrm{Hom}(F \\to G \\otimes H) = \\#\\mathrm{Hom}(F \\to G) \\cdot \\#\\mathrm{Hom}(F \\to H)$, the interpolation method of Dedekind can isolate each summand, making the counting problem exactly as hard as the hardest homomorphism in the support. The tractable direction feeds on a known FPT algorithm for $\\#\\mathrm{Hom}$ on classes of bounded fractional hypertree width; the hardness direction feeds on known ETH-based hardness for classes of unbounded adaptive width. The bridge between the new cover parameters and width is the inequality $\\alpha(H) \\ge \\frac{1}{2} + \\frac{\\alpha^*(H)}{4\\,\\mathrm{aw}(H)}$, together with a Ramsey argument that turns a large independent set inside a minimal co-independent set into a quotient graph of large treewidth.","core_discovery":"The central claim is that two newly isolated invariants govern the entire complexity map. For every recursively enumerable family $\\mathcal{H}$ of hypergraphs, assuming ETH, $\\#\\mathrm{Sub}(\\mathcal{H})$, parameterized by $|H|$, is fixed-parameter tractable if and only if $\\sigma^*(\\mathcal{H}) < \\infty$, and $\\#\\mathrm{IndSub}(\\mathcal{H})$ is fixed-parameter tractable if and only if $\\rho^*(\\mathcal{H}) < \\infty$. These are exact dichotomies, not merely upper or lower bounds. Along the way the paper proves that the tractable side is algorithmically delicate: some families with bounded $\\sigma^*$ are #P-hard for #Sub, and some with bounded $\\rho^*$ require quasi-polynomial time for #IndSub unless Graph Isomorphism is in P. Finally, the paper studies a natural trimmed notion of sub-hypergraph and shows that the homomorphism-basis method, which carries the two dichotomies, provably cannot be adapted to that setting.","pith_inferences":["Because the dichotomy is decided by two static rational parameters on the pattern hypergraph, a practical system could compute $\\sigma^*$ and $\\rho^*$ on query patterns to predict whether a hypergraph counting workload is likely to admit fixed-parameter algorithms.","The constant $1/4$ in the integrality-gap inequality is the quantitative hinge of the lower-bound construction; improving it would sharpen the dependence of the hardness results on the pattern size, and a counterexample to it would reopen the lower-bound proofs.","The failure of complexity monotonicity for trimmed sub-hypergraphs hints that other hypergraph deletion semantics, such as vertex pruning that keeps residual edges, may each require their own algebraic basis and cannot borrow the homomorphism-basis framework.","The dichotomies are asymptotic in the pattern size, so they leave open fine-grained questions about the smallest exponent of the host size for specific families; the quotient construction used in the lower-bound proof could serve as a template for building candidate hard families with controlled pattern rarity."],"forward_implications":["For any recursively enumerable family $\\mathcal{H}$, $\\#\\mathrm{Sub}(\\mathcal{H})$ is fixed-parameter tractable when $\\sigma^*(\\mathcal{H}) < \\infty$, yet some such families remain #P-hard, so fixed-parameter tractability does not collapse to polynomial time in the hypergraph setting.","For any recursively enumerable family $\\mathcal{H}$, $\\#\\mathrm{IndSub}(\\mathcal{H})$ is fixed-parameter tractable when $\\rho^*(\\mathcal{H}) < \\infty$, solvable in quasi-polynomial time; a polynomial-time algorithm for every such family would place Graph Isomorphism in P.","The classical graph dichotomies are special cases: for graphs, $\\sigma^*$ behaves asymptotically like the vertex-cover number and $\\rho^*$ like the vertex count, so the two theorems recover the known classifications for subgraph and induced subgraph counting.","Unbounded $\\sigma^*$ or $\\rho^*$ makes the corresponding problem not fixed-parameter tractable unless ETH fails, yielding a hard 'if and only if' statement at the level of parameterized complexity.","For trimmed sub-hypergraphs, the usual complexity-monotonicity machinery breaks down: an easy induced trimmed counting problem can have a hard trimmed homomorphism in its expansion, and no fixed-parameter-associative product can serve as the basis for interpolation."],"supporting_citations":[{"why":"Supplies the interpolation theorem and the integrality-gap inequality $\\alpha(H) \\ge \\frac{1}{2} + \\frac{\\alpha^*(H)}{4\\,\\mathrm{aw}(H)}$ that power the lower-bound constructions.","marker":"[BLR23]"},{"why":"Gives the fixed-parameter algorithm for counting hypergraph homomorphisms on families of bounded fractional hypertree width, used in both tractable directions.","marker":"[GM14]"},{"why":"Proves that homomorphism counting is hard on families of unbounded adaptive width, giving the lower-bound engine under ETH.","marker":"[Mar13]"},{"why":"Introduces the homomorphism-basis and complexity-monotonicity framework for graphs that the paper lifts to hypergraphs of unbounded rank.","marker":"[CDM17]"},{"why":"Supplies the graph dichotomy for subgraph counting and the Ramsey lemma that extracts large cliques, bicliques, or matchings used in the quotient construction.","marker":"[CM14]"},{"why":"Provides the Möbius-inversion identities over the partition lattice that express embedding and strong-embedding counts as combinations of homomorphism counts.","marker":"[Lov12]"},{"why":"Gives the bounded-rank homomorphism counting dichotomy used to derive #W[1]-hardness when quotients contain graphs of unbounded treewidth.","marker":"[DJ04]"},{"why":"States the Exponential Time Hypothesis that the hardness results condition on.","marker":"[IP01]"},{"why":"Yields the quasi-polynomial hypergraph isomorphism test used in the quasi-polynomial upper bound for the bounded-$\\rho^*$ case.","marker":"[Neu22]"},{"why":"Provides the logarithmic integrality gap for fractional edge covers used to enumerate a small edge cover in the quasi-polynomial algorithm.","marker":"[Vaz01]"}],"fun_headline_variants":["Hypergraph count easy iff a cover number is bounded","Two cover numbers dictate hypergraph counting complexity","ETH dichotomy: bounded cover gives fixed-parameter tractability","Sub-hypergraph counting: fractional covers decide tractability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hardness direction rests on an externally supplied inequality claiming that every hypergraph has an independent set at least one half plus a quarter of its fractional independence number divided by its adaptive width; if that inequality fails for any hypergraph family used in the proof, the lower-bound arguments collapse.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph count easy iff a cover number is bounded","Two cover numbers dictate hypergraph counting complexity","ETH dichotomy: bounded cover gives fixed-parameter tractability","Sub-hypergraph counting: fractional covers decide tractability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000228,"raw_usage":{"total_tokens":1534,"prompt_tokens":1064,"completion_tokens":470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":407}},"tokens_in":680,"tokens_out":470,"duration_ms":4706,"temperature":1.0,"reasoning_tokens":407,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:57:20.570038+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To refute the dichotomy, exhibit a recursively enumerable family $\\mathcal{H}$ with $\\sigma^*(\\mathcal{H})=\\infty$ for which $\\#\\mathrm{Sub}(\\mathcal{H})$ is still fixed-parameter tractable, or a family with $\\rho^*(\\mathcal{H})=\\infty$ for which $\\#\\mathrm{IndSub}(\\mathcal{H})$ is still FPT; under ETH the theorems forbid both. A concrete spot to probe is the construction of Lemma 5.8: run it on the family of 4-uniform sunflowers with core size one and check whether the quotients it produces really contain graphs of unbounded treewidth — if the Ramsey step fails to produce such a quotient, the lower-bound chain breaks.","supporting_citations":[],"review_version":2}