{"id":"a7511bf2-5993-4f9d-a83d-9aa72549b7a4","arxiv_id":"2411.16017","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"An O(|V(G)|^6) algorithm for hypergraph immersion is claimed, but the proof has a false Mader-type lemma and applies a fixed-parameter theorem to a pattern that grows with the input.","lead":"The paper defines hypergraph immersion and claims a fixed-parameter tractable algorithm running in O(|V(G)|^6) time. The proof contains a false density lemma and an invalid use of a fixed-parameter embedding theorem, so the central claim is not established.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.5 is false: hypergraphs with linearly many singleton hyperedges need not immerse K2, so the O(N^6) bound is not established.","rationale":"The reader's weakest assumption is exactly Lemma 4.5, and I agree that it is the load-bearing failure. The counterexample is not exotic: size-1 hyperedges are explicitly permitted, and the lemma's proof does not even describe a valid operation for converting hyperedges into pairwise edges. I also note the independent issue that the pattern H''_L is input-dependent, which reinforces rejection but is not needed for the main objection. The definitional framework and Proposition 3.4 may be useful, but the central algorithmic complexity theorem is not supported as written.","tokens_in":50,"tokens_out":7823,"duration_ms":139868,"concrete_test":"Take C = 2 and define G_n with n vertices and 2n singleton hyperedges. Inspect whether the reduction in Lemma 4.5 can produce an ordinary graph G_0 with O(n) edges and whether K2 immerses in G_n; direct inspection shows no Berge path between distinct vertices, so K2 is not immersed. Then, without Lemma 4.5, recompute |V(G''_{M,L})| using only the general bound |E(G)| = O(|V(G)|^2) (e.g., complete 3-uniform hypergraphs); the resulting embedding algorithm would run in more than O(|V(G)|^6) time, so the claimed fixed-parameter bound does not follow.","verdict_should_be":"REJECT","load_bearing_attack":"The key step bounding |E(G)| = O(|V(G)|) is Lemma 4.5, the claimed hypergraph analogue of Mader's theorem. It is false as stated. Let G consist of n vertices and C n disjoint singleton hyperedges (C any proposed constant), and let H = K2. Since G has no Berge path between distinct vertices, no connected subgraph can contain images of both endpoints of H's edge; H is not immersed, contradicting the lemma's assertion. The proof of Lemma 4.5 also assumes that dewetting reduces a hypergraph to an ordinary graph with the same edge count, but dewetting e to e\\{v} only removes one incidence, never splits e into pairwise edges, so the reduction to ordinary Mader is invalid. Theorem 4.1 uses Lemma 4.5 to conclude |V(G''_{M,L})| = O(|V(G)|^2) and hence O(|V(G)|^6); without this lemma there is no valid complexity bound. A separate gap is that Theorem 2.7 is applied to H''_L whose size grows with L = O(|V(G')|), outside the fixed-H hypothesis of Grohe et al.; either issue independently breaks the proof as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a notion of hypergraph immersion, in which each hyperedge of a pattern H is mapped to an edge-disjoint connected subgraph (with respect to Berge paths) of a host hypergraph G, and it proposes an equivalent characterization via two operations, coalescence and dewetting. The main claim (Theorems 3.5, 4.1, and 5.1) is that for every fixed ordinary or hypergraph H, deciding whether H can be immersed in a hypergraph G can be done in O(|V(G)|^6) time, giving fixed-parameter tractability. The proof strategy is to convert hypergraph immersion to ordinary graph embedding by using an M-generalized factor graph, densifying vertices with large cliques, and, for hypergraph patterns, testing a finite set of 'divisions' of H. The paper also introduces a dual hypergraph immersion notion via transposition. The algorithmic argument is not established as written: a key lemma bounding the number of hyperedges is false, and the densified pattern used in the reduction is not fixed.","tokens_in":41,"tokens_out":11312,"duration_ms":163957,"significance":"The paper proposes a natural and useful extension of graph immersion to hypergraphs, and the division-based reduction is conceptually interesting. If the technical gaps were repaired, an O(|V(G)|^6) fixed-parameter algorithm for hypergraph immersion would be a meaningful contribution to algorithmic graph theory and could be relevant to quantum network routing. The paper is also clearly written and the definitions are well motivated. However, the central theorem is not proven in the current version because of load-bearing errors in the complexity analysis, so the significance cannot be assessed as claimed.","major_comments":[{"comment":"The lemma is false as stated. The paper permits size-1 hyperedges (see the footnote in Section 2.2 and Remark 2.3). Let G have n vertices and C·n distinct singleton hyperedges, where C is any proposed constant. Then |E(G)| = C|V(G)|, but G contains no Berge path between distinct vertices, so the ordinary graph K2 cannot be immersed in G. Thus the claimed bound |E(G)| = O(|V(G)|) is not a consequence of the lemma. The proof's reduction via dewetting is also invalid: applying dewetting to a hyperedge e yields the smaller hyperedge e\\{v}, and for |e|=1 it cannot produce an ordinary edge at all; it never turns a hyperedge into two ordinary edges. Consequently, the step in the proof of Theorem 4.1 that uses Lemma 4.5 to conclude |V(G''_{M,L})| = O(|V(G)|^2) fails, and the O(|V(G)|^6) bound is not established.","section":"§4.2, Lemma 4.5"},{"comment":"The densified pattern H''_L is not a fixed graph. Remark 4.4 sets L > M|V(G'_M)|, so even if Lemma 4.5 were true, |V(G'_M)| = M|V(G)| + |E(G)| = O(|V(G)|), giving |V(H''_L)| = L|V(H)| = O(|V(G)|). Theorem 2.7 provides an O(|V(G)|^3) algorithm for embedding a fixed graph H; the constant in the O may depend on H. Applying Theorem 2.7 to the growing graph H''_L therefore does not yield a uniform O(|V(G)|^6) algorithm. The same problem appears in the proof of Theorem 5.1, where each densified division \\tilde H''_L also has size depending on L = O(|V(G)|). The paper acknowledges the growth of L in Remark 4.4 but gives no argument that the dependence on H''_L is harmless for fixed-parameter tractability.","section":"§4.2, Remark 4.4 and proof of Theorem 4.1"}],"minor_comments":[{"comment":"The proof of Proposition 3.4 is only a sketch and relies on the authors' own preprint [28]. In the 'if' direction, it is not shown rigorously how a sequence of coalescence and dewetting operations on a subgraph of G yields well-defined edge-disjoint connected subgraphs α(e) for each e ∈ E(H). An independent, complete proof would be preferable, or the statement should be clearly marked as a result from [28] with a full proof.","section":"§3.1, Proposition 3.4"},{"comment":"The running time for testing one densified factor graph is stated as O(|V(G''_{M,L})|) (twice in the proof of Theorem 5.1); it should be O(|V(G''_{M,L})|^3) to match Theorem 2.7.","section":"§5.4, proof of Theorem 5.1"},{"comment":"The statement 'Let |E(G)| = C |V(G)|' should be 'Let |E(G)| ≥ C |V(G)|' for the lemma to be a Mader-type density condition. Also, the expression '|E(G0)| / |E(H)| = C0 |V(G0)|' is dimensionally confusing and should be rewritten with explicit multiplicative constants.","section":"§4.2, Lemma 4.5"},{"comment":"There is a typographical error: 'a(v1) ≠ α(v2)' should read 'α(v1) ≠ α(v2)'.","section":"§3.1, proof of Proposition 3.4"}],"recommendation":"reject","confidential_remarks":"The manuscript depends on its own unpublished preprint [28] for a central equivalence and on an unproved hypergraph analogue of Mader's theorem (Lemma 4.5). The latter is not merely unproved but false under the paper's own definitions, and the former is not given a complete independent proof. The fixed-parameter tractability claim also relies on applying a fixed-pattern embedding algorithm to a pattern whose size grows with the input. These are load-bearing issues that would require substantial new results to repair. The topic is within the scope of the journal, but the current version is not ready for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Thanks for sending this. The thing to know: the paper's central theorem is not supported. The new definition of hypergraph immersion—edge-disjoint connected subgraphs, with coalescence and dewetting operations—is genuinely new and worth recording. The division/topological-class idea for handling hypergraph patterns is also a reasonable direction. But Theorem 3.5 (and 5.1) should not be taken as proven.\n\nThe main problem is Lemma 4.5, the claimed hypergraph analogue of Mader's theorem. It is false as stated. The paper explicitly permits size-1 hyperedges. A hypergraph on n vertices with C n singleton hyperedges has linear edge count but no Berge path between any two distinct vertices, so it cannot immerse even K2. That directly contradicts the lemma, no matter how large C is. The lemma is the step that bounds |E(G)| = O(|V(G)|), and the O(N^6) bound in the proof of Theorem 4.1 comes from |V(G''_{M,L})| = O(|V(G)|^2) using that bound. Without Lemma 4.5, the complexity argument collapses.\n\nThere is a second, independent hole: the embedding algorithm of Grohe et al. (Theorem 2.7) is FPT with the pattern fixed. Here it is applied to H''_L, whose size depends on L = O(|V(G'_M)|), i.e., on the input hypergraph, not just on H. That is outside the theorem's scope.\n\nI would also flag Proposition 3.4's dependence on the authors' own Ref [28] for the equivalence of immersion with coalescence/dewetting. They provide a proof sketch, but the stated theorem is not self-contained.\n\nWhat is good: the definitions are clean, the dual hypergraph immersion in Section 6 is a nice addition, and the finite topological-class reduction for divisions of H (Lemma 5.5) is a sensible idea. None of that rescues the main theorem, though.\n\nWho is this for? Someone thinking about generalizing immersion to hypergraphs might get value from the definitions and the division framework, but not from the algorithmic claim. I would not send this to a serious referee as is; the counterexample is simple and the main theorem is unproven. A revised version that restricts the input (e.g., excluding singleton hyperedges) or fixes the Mader argument could be worth another look.","headline":"The hypergraph immersion definition is a real contribution, but the claimed O(N^6) FPT algorithm rests on a false hypergraph Mader lemma and an out-of-scope invocation of Grohe et al.; the main theorem is not established.","tokens_in":16964,"tokens_out":3187,"would_cite":false,"duration_ms":27758,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C85","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"Hypergraph immersion is decidable in $O(|V(G)|^6)$ time for every fixed pattern.","keywords":["hypergraph immersion","fixed-parameter tractability","graph immersion","M-generalised factor graph","densification","Berge path","edge coalescence","dewetting"],"falsifier":"Test Lemma 4.5 directly: take $H = K_2$ (a single edge) and take $G$ to be a hypergraph on $n$ vertices that consists only of $n$ singleton hyperedges, one at each vertex, so $|E(G)| = |V(G)|$. By the definition of hypergraph paths, no Berge path connects two distinct vertices in such a $G$, so $H$ cannot be immersed; this would disprove the lemma as stated and show that the proof's linear edge cap needs a different justification.","tokens_in":15916,"feed_emoji":"🕸️","tokens_out":13280,"duration_ms":107041,"temperature":0.7,"pith_summary":"The paper extends immersion minor—the relation in which a pattern appears inside a larger graph through edge-disjoint paths—to hypergraphs, where edges may connect more than two vertices. It claims that for every fixed hypergraph $H$, deciding whether $H$ can be immersed in an input hypergraph $G$ is fixed-parameter tractable, with an algorithm that runs in $O(|V(G)|^6)$ time and whose exponent does not depend on $H$. The proof converts the hypergraph problem into an ordinary graph embedding problem and then applies a cubic-time embedding test. This matters because hypergraph connectivity models multipartite entanglement in quantum networks, chemical reaction systems, and other higher-order interaction data, so a uniform polynomial test for pattern containment in those settings has direct use.","feed_headline":"Hypergraph immersion is decidable in O(N^6) time","feed_subtitle":"The proof reduces hypergraph routing to ordinary graph embedding: one polynomial test for every fixed pattern.","key_machinery":"The paper gives two equivalent definitions of hypergraph immersion: a geometric definition using edge-disjoint connected subgraphs (hypergraph paths known as Berge paths), and an operation-based definition using two rewrites—edge coalescence, which merges two intersecting hyperedges into their union, and dewetting, which removes one vertex from a hyperedge. The algorithmic proof is carried by three constructions: the $M$-generalised factor graph $G'_M$, an ordinary graph with $M$ copies of each vertex and one vertex per hyperedge; densification, which replaces each distinguished vertex copy by a large clique $K_L$ to enforce the correct vertex mapping; and divisions of $H$, which replace each hyperedge by a Steiner tree connecting its vertices so that all possible internal topologies of an immersed hyperedge fall into finitely many topological classes. The densified factor graphs turn hypergraph immersion into ordinary graph embedding, for which a cubic-time algorithm is available, and the final complexity is obtained by bounding the size of the auxiliary graph.","core_discovery":"The central claim, Theorem 5.1 (with Theorem 3.5 as the general statement), is that for every finite loopless hypergraph $H$ there is an $O(|V(G)|^6)$-time algorithm deciding whether $H$ can be immersed in a hypergraph $G$. Hypergraph immersion means mapping the vertices of $H$ injectively to vertices of $G$ and mapping each hyperedge of $H$ to an edge-disjoint connected subgraph of $G$ containing the images of its vertices. The proof first handles ordinary graphs $H$, using an $M$-generalised factor graph $G'_M$ and a densification step that replaces special vertices by large cliques so that the vertex mapping is forced to respect the original hypergraph vertices; it then handles hypergraph $H$ by testing factor graphs of a finite set of divisions of $H$, which account for all possible internal topologies of an immersed hyperedge. A hypergraph analogue of the classical average-degree forcing theorem is used to bound $|E(G)|$ linearly in $|V(G)|$, which keeps the auxiliary graph at size $O(|V(G)|^2)$ and gives the stated $O(|V(G)|^6)$ bound.","pith_inferences":["Editorial inference: the constant hidden by the $O(|V(G)|^6)$ bound grows with the number of divisions in $D(H)$—the paper itself counts 18 topological classes for the complete 3-uniform hypergraph on 4 vertices—so the practical bottleneck is pattern-dependent even though the asymptotic exponent is not.","Editorial inference: the same reduction to ordinary graph embedding could be reused for other hypergraph containment relations that allow arbitrary internal topology for each hyperedge, since the division-and-densification machinery is not specific to immersion.","Editorial inference: the exact exponent 6 is tied to the linear edge bound supplied by the hypergraph analogue of the average-degree forcing theorem; if that bound needs to be weakened, the paper's method would still give a polynomial algorithm, but possibly with a larger fixed exponent."],"forward_implications":["For any fixed pattern $H$, deciding immersion in a hypergraph $G$ takes at most $O(|V(G)|^6)$ time, so the problem is fixed-parameter tractable with exponent independent of $H$.","The ordinary graph immersion problem is the special case where every hyperedge has size 2, so the theorem supplies a polynomial immersion test for ordinary graphs as well, with a larger but still constant exponent.","The finite division set $D(H)$ means the search over possible internal topologies of immersed hyperedges is finite and depends only on the pattern $H$, not on the input hypergraph.","By the paper's duality theorem, the same $O(|V(G)|^6)$ algorithm also decides dual immersion between the transposed hypergraphs, giving a polynomial check for the vertex-coalescence version of the problem."],"supporting_citations":[{"why":"Supplies the cubic-time ordinary graph embedding algorithm and the densification technique that the proof adapts to hypergraphs.","marker":"[9]"},{"why":"Provides the classical theorem on average edge density forcing a fixed graph as an immersion, which the paper extends to hypergraphs in Lemma 4.5 to bound |E(G)| linearly.","marker":"[18]"},{"why":"Establishes the equivalence between hypergraph immersion and the sequence of coalescence and dewetting operations, stated as Proposition 3.4.","marker":"[28]"},{"why":"Defines immersion in ordinary graphs and supplies the surrounding graph-minor theory that the hypergraph definition extends.","marker":"[25]"},{"why":"Defines the hypergraph path notion (Berge paths) used to formulate connectivity of immersed connected subgraphs.","marker":"[1]"},{"why":"Defines factor graphs of hypergraphs, the construction that the proof generalises to M-generalised factor graphs.","marker":"[3]"}],"fun_headline_variants":["O(N^6) algorithm finds any fixed hypergraph immersion","Fixed hypergraph immersion: one O(N^6) test","Polynomial-time test for hypergraph immersion","Immersion check for fixed hypergraphs: O(N^6)","O(N^6) suffices for hypergraph immersion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's $O(|V(G)|^6)$ bound depends on Lemma 4.5, which asserts that any hypergraph with at least a constant $C(H)$ times $|V(G)|$ edges already contains $H$ as an immersion; the lemma is proved by reducing the hypergraph to an ordinary graph through dewetting and capping multiedges, and if that step fails, the linear edge bound on $|E(G)|$ and hence the stated exponent are not established.","fun_headline_variants_meta":{"raw":{"variants":["O(N^6) algorithm finds any fixed hypergraph immersion","Fixed hypergraph immersion: one O(N^6) test","Polynomial-time test for hypergraph immersion","Immersion check for fixed hypergraphs: O(N^6)","O(N^6) suffices for hypergraph immersion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000505,"raw_usage":{"total_tokens":2453,"prompt_tokens":921,"completion_tokens":1532,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":1451}},"tokens_in":537,"tokens_out":1532,"duration_ms":11589,"temperature":1.0,"reasoning_tokens":1451,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:41:54.019732+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test Lemma 4.5 directly: take $H = K_2$ (a single edge) and take $G$ to be a hypergraph on $n$ vertices that consists only of $n$ singleton hyperedges, one at each vertex, so $|E(G)| = |V(G)|$. By the definition of hypergraph paths, no Berge path connects two distinct vertices in such a $G$, so $H$ cannot be immersed; this would disprove the lemma as stated and show that the proof's linear edge cap needs a different justification.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the cubic-time ordinary graph embedding algorithm and the densification technique that the proof adapts to hypergraphs."},{"cited_title":"Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen","cited_arxiv_id":null,"evidence_quote":"Provides the classical theorem on average edge density forcing a fixed graph as an immersion, which the paper extends to hypergraphs in Lemma 4.5 to bound |E(G)| linearly."},{"cited_title":"Multipartite Entanglement Routing as a Hypergraph Immersion Problem","cited_arxiv_id":"2406.13452","evidence_quote":"Establishes the equivalence between hypergraph immersion and the sequence of coalescence and dewetting operations, stated as Proposition 3.4."},{"cited_title":"Nash-Williams’ immersion conjec- ture, Journal of Combinatorial Theory, Series B 100 (2010), no","cited_arxiv_id":null,"evidence_quote":"Defines immersion in ordinary graphs and supplies the surrounding graph-minor theory that the hypergraph definition extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the hypergraph path notion (Berge paths) used to formulate connectivity of immersed connected subgraphs."}],"review_version":1}