{"id":"15ef4071-9a3c-4bf2-82ef-8ce637bb1575","arxiv_id":"2607.05040","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Hypergraph motif counting is always FPT-near-quadratic in rank, and FPT-near-linear exactly for the degenerate Venn diagrams, assuming Triangle and Hyperclique Hypotheses.","lead":"The paper classifies the fine-grained complexity of counting three-edge hypergraph motifs by Venn diagram pattern, parameterized by hypergraph rank. Every pattern admits FPT near-quadratic time; only degenerate patterns (one edge contained in another) admit FPT near-linear time, under standard hypotheses.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the two fine-grained hypotheses as the sole external assumptions and correctly notes that the technical novelty (and the place where cancellations could have been fatal) is the colourful-fracture machinery. That machinery is carried out case-by-case for all 14 non-degenerate diagrams and yields non-zero coefficients on explicitly non-acyclic patterns; the upper-bound side is a routine application of Yannakakis-style algorithms once ghtw≤2 is observed. Because both halves are combinatorial, fully written, and free of hidden parameters or circular appeals, the ACCEPT verdict with high confidence stands. The partial classification for k>3 is already flagged by the authors as inherited from the open status of unbounded-rank #Hom and does not affect the main claim for three-edge motifs.","tokens_in":36086,"tokens_out":528,"duration_ms":5281,"concrete_test":"Independently recompute the fourteen coefficients coeff_H,V(⊤) for V1–V14 (Lemmas 4.3–4.7) by enumerating the relevant fractures of the chosen Δ/Γ patterns; if any coefficient evaluates to zero the lower-bound half of Corollary 1.4 fails for that diagram.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central dichotomy (FPT-near-quadratic for every Venn diagram; FPT-near-linear precisely for the degenerate ones) rests on two pillars that both appear solid: (1) the homomorphism expansion of #M(V\to G) (Lemma 5.2) together with the elementary observation that every 3-edge hypergraph has ghtw≤2 and every degenerate one has ghtw≤1 after quotients (Lemma 5.1), and (2) the colourful-fracture coefficient analysis (Corollary 4.8) that places a non-α-acyclic term (a Δ(j1,j2,j3) or Γ(j1,j2,j3)) with non-zero coefficient for every non-degenerate V. The only external assumptions are the Triangle and Hyperclique Hypotheses, which the authors invoke exactly as the literature does for non-acyclic homomorphism counting; they are not hidden. No cancellation, missing case, or reduction gap that would break the dichotomy is visible in the written proofs.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper classifies the fine-grained parameterized complexity of exact counting of hypergraph motifs (connected 3-edge subhypergraphs whose intersections match a Venn diagram V in {0,1}^7) with respect to the rank of the host hypergraph G. It proves that #HyperMotif(V) always admits an FPT-near-quadratic algorithm f(rank(G)) · Õ(|E(G)|^2). Moreover, FPT-near-linear time is possible if and only if V is degenerate (one edge forced to be contained in another); for every non-degenerate V the problem is not FPT-near-linear unless the Triangle Hypothesis or the Hyperclique Hypothesis fails. The proofs proceed by expressing motif counts as linear combinations of (colourful) hypergraph homomorphism counts via fractures and Möbius inversion over the fracture lattice, isolating a non-α-acyclic term of generalized hypertreewidth >1 for non-degenerate diagrams, and invoking known near-linear hardness of homomorphism counting from non-acyclic patterns. Partial FPT/ETH results are also given for generalized motifs of order k>3 via hereditary fractional hypertreewidth and adaptive width.","tokens_in":36302,"tokens_out":905,"duration_ms":12086,"significance":"The result supplies a tight, exhaustive dichotomy for a motif-counting problem that was introduced for practical hypergraph analysis (Lee–Ko–Shin, VLDB 2020) and whose previous algorithms were cubic even on bounded-rank or 2-uniform instances. The improvement to near-quadratic (and near-linear for the degenerate cases) is therefore both theoretically clean and immediately relevant to the original application domain. The technical machinery—hypergraph fractures, the colourful intermediate problem, and coefficient non-vanishing arguments that survive multiple non-isomorphic realisations of the same Venn diagram—extends the recent hypergraph-homomorphism basis of Bressan et al. (SODA 2026) in a non-trivial way and is likely reusable for other hypergraph motif problems. The partial classification for k>3 correctly identifies the open gap with the still-unresolved complexity of unbounded-rank hypergraph homomorphism counting, so the paper does not overclaim.","major_comments":[],"minor_comments":[{"comment":"Figure 2 and Definition 2.14: the visual distinction between degenerate (green) and non-degenerate (red) diagrams is helpful, but a short explicit list of the containment conditions that characterise the twelve degenerate diagrams would make the dichotomy easier to verify without inspecting every picture.","section":null},{"comment":"Section 4 (especially Lemmas 4.3–4.7): the case-by-case coefficient calculations for the fourteen non-degenerate diagrams are correct but somewhat repetitive; a short table summarising, for each V_i, the chosen host (Δ(j1,j2,j3) or Γ(j1,j2,j3)) and the resulting non-zero coefficient of the coarsest fracture would improve readability.","section":null},{"comment":"Lemma 3.8 / Algorithm 1: the claimed O(r^{2} · ∥G∥ · ∥F∥) bound for the colour-preserving tensor product is fine, yet the algorithm description does not explicitly state that edges of unequal cardinality are discarded; a one-line remark would remove any ambiguity.","section":null},{"comment":"Page 9, line 3 of the abstract and several places in the introduction: the notation |G| is used for the input size while |E(G)| appears in the running-time statements; a uniform convention (or an explicit remark that |G| = Θ(|V| + |E|) under the no-isolated-vertex assumption) would avoid minor confusion.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean, self-contained fine-grained complexity paper that sits comfortably in the SODA/STOC/FOCS/ICALP track. The only external hardness assumptions are the standard Triangle and Hyperclique Hypotheses already used for non-acyclic homomorphism counting; they are invoked transparently. I see no novelty or citation issues. Accept as is (or after the purely cosmetic minor revisions listed)."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper finishes the fine-grained story for the three-edge hypergraph motifs that Lee et al. introduced and left at cubic time. Every Venn diagram is FPT-near-quadratic in the number of edges once you parameterise by rank; the degenerate ones (one edge contained in another) drop to FPT-near-linear; the rest stay hard under Triangle or Hyperclique. That is the whole dichotomy, and it is explicit for all 26 diagrams.\n\nWhat is new is the colourful intermediate problem plus the fracture lattice. The ordinary homomorphism expansion of motif counts produces alternating sums that can cancel, and multiple non-isomorphic three-edge hypergraphs realise the same Venn diagram, so you cannot just read off the support. By colouring the three edges and working with fractures they get a cleaner coefficient formula, then they simply check, diagram by diagram, that a non-acyclic term (a padded triangle or a 3-uniform almost-clique) survives with non-zero coefficient. The upper bounds are the usual ones: quotients of three-edge hypergraphs have ghtw at most 2, and at most 1 when the diagram is degenerate, so Yannakakis-style algorithms finish the job. The reduction chain that transfers hardness is short and standard once the coefficients are non-zero.\n\nThe only soft spot is the partial result for k>3 motifs. They correctly reduce it to the still-open gap between fractional hypertreewidth and adaptive width for unbounded-rank hypergraph homomorphisms, and they do not pretend otherwise. Everything else is combinatorial, fully written, and checkable from the text; the external hypotheses are exactly the ones the literature already uses for non-acyclic homomorphism counting.\n\nThis is for people who care about pattern counting, fine-grained complexity, or hypergraph algorithms that already appear in VLDB/ML pipelines. It deserves a serious referee and is worth reading if you work in the area. I would engage.","headline":"Clean FPT-near-quadratic / near-linear dichotomy for all 26 three-edge hypergraph motifs under rank, with the hard work done by colourful fractures that kill cancellations.","tokens_in":36942,"tokens_out":490,"would_cite":true,"duration_ms":5644,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","05C65","68R10"],"pacs":[],"model":"grok-4.5","headline":"Exact hypergraph motif counting is always fixed-parameter near-quadratic in rank, and admits fixed-parameter near-linear time precisely for the degenerate Venn diagrams.","keywords":["hypergraph motifs","Venn diagrams","fine-grained complexity","parameterised counting","homomorphism basis","generalised hypertreewidth","Triangle Hypothesis","Hyperclique Hypothesis"],"falsifier":"Exhibit either an FPT-near-linear algorithm for any single non-degenerate Venn diagram, or a near-linear algorithm for detecting triangles in graphs or hypercliques in uniform hypergraphs; either would collapse the claimed dichotomy.","tokens_in":36946,"feed_emoji":"🔢","tokens_out":919,"duration_ms":10972,"temperature":0.7,"pith_summary":"Hypergraph motifs are three-edge connected subhypergraphs whose intersections match a prescribed Venn diagram pattern. Prior algorithms took cubic time even on bounded-rank inputs, including ordinary graphs. This paper proves that every such motif can be counted exactly in time that is fixed-parameter near-quadratic in the number of edges once the rank is treated as the parameter. The same running time improves to fixed-parameter near-linear if and only if the Venn diagram is degenerate (one edge forced inside another). For every non-degenerate diagram the near-linear regime is impossible unless standard fine-grained hypotheses fail. The result therefore supplies a complete dichotomy for the three-edge case and explains exactly when the cubic barrier can be beaten.","feed_headline":"Hypergraph motifs always near-quadratic, near-linear if degenerate","feed_subtitle":"A complete fine-grained dichotomy: cubic algorithms are never optimal once rank is fixed","key_machinery":"The hypergraph-homomorphism basis (linear combinations of homomorphism counts obtained from quotients of the motif hypergraphs) together with a colourful intermediate problem defined via fractures of the host. Non-zero coefficients of non-α-acyclic terms survive for every non-degenerate diagram, and Dedekind interpolation transfers hardness; generalised hypertree-width at most 2 (respectively 1) yields the matching upper bounds.","core_discovery":"Every Venn diagram admits an exact counting algorithm running in f(rank(G))·Õ(|E(G)|^{2}) time. This improves to f(rank(G))·Õ(|E(G)|) time exactly when the diagram is degenerate, i.e., forces one of the three hyperedges to be fully contained in another. For all non-degenerate diagrams no fixed-parameter near-linear algorithm exists unless the Triangle Hypothesis or the Hyperclique Hypothesis fails.","pith_inferences":["The colourful-fracture technique introduced here is likely reusable for any motif-counting problem whose patterns are defined by emptiness constraints on intersections, including higher-arity relational queries.","Closing the remaining gap between fractional hypertree-width and adaptive width for hypergraph homomorphisms would immediately give a complete FPT dichotomy for all generalised hypergraph motifs.","The same linear-combination approach should yield conditional lower bounds for approximate counting of non-degenerate motifs under the same fine-grained hypotheses."],"forward_implications":["On any class of bounded-rank hypergraphs the cubic algorithms of Lee et al. are never optimal: every motif is near-quadratic and the degenerate ones are near-linear.","The same dichotomy immediately specialises to ordinary graphs (rank 2), giving a complete fine-grained classification of three-edge motif counting on simple graphs.","Any future improvement of the generalised-hypertree-width algorithms for homomorphism counting would automatically improve the motif-counting upper bounds by the same factor.","The hereditary fractional-hypertree-width and adaptive-width criteria already supply matching FPT and ETH-hardness results for generalised motifs on more than three edges, leaving only the open gap inherited from hypergraph homomorphism counting."],"fun_headline_variants":["Hypergraph motifs: always FPT-near-quadratic, near-linear iff degenerate","Every Venn pattern admits FPT-near-quadratic motif counting","Degenerate diagrams alone allow FPT-near-linear hypergraph motifs","Fine-grained dichotomy: motifs near-quadratic unless degenerate","Rank-parameterized motif counting is near-quadratic, linear only if nested"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The near-linear lower bounds for non-degenerate diagrams rest on the Triangle Hypothesis and the Hyperclique Hypothesis remaining true.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph motifs: always FPT-near-quadratic, near-linear iff degenerate","Every Venn pattern admits FPT-near-quadratic motif counting","Degenerate diagrams alone allow FPT-near-linear hypergraph motifs","Fine-grained dichotomy: motifs near-quadratic unless degenerate","Rank-parameterized motif counting is near-quadratic, linear only if nested"]},"model":"grok-4.5","effort":"low","cost_usd":0.005636,"raw_usage":{"total_tokens":1598,"prompt_tokens":940,"num_sources_used":0,"completion_tokens":98,"cost_in_usd_ticks":56360000,"prompt_tokens_details":{"text_tokens":940,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":560,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":940,"tokens_out":98,"duration_ms":4367,"temperature":1.0,"reasoning_tokens":560,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T09:41:46.396469+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit either an FPT-near-linear algorithm for any single non-degenerate Venn diagram, or a near-linear algorithm for detecting triangles in graphs or hypercliques in uniform hypergraphs; either would collapse the claimed dichotomy.","supporting_citations":[],"review_version":1}