{"id":"506493d7-fdda-4586-a230-2eeb3a6480bc","arxiv_id":"2607.08614","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Two temporal graphs are order-isomorphic iff they have equal homomorphism counts from all temporal patterns; counting is FPT for bounded toadwidth and dichotomized for total orders.","lead":"This paper proves three results about counting temporal graph patterns: a Lovász-style theorem showing homomorphism counts determine temporal graph isomorphism, an FPT algorithm for patterns of bounded 'toadwidth', and a complexity dichotomy for totally ordered patterns. It matters because temporal motif counting underpins analysis of dynamic networks but lacked theoretical complexity foundations.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The arithmetic separation in Lemma 5.9 is verifiable and correct; the backward direction of Lemma 5.11 has a subtle but sound dependency on the edge-colourful condition.","rationale":"The reader correctly identifies the arithmetic separation properties (Lemma 5.9) as a critical dependency, but my verification confirms these are correct: the gap of $n^2$ between consecutive $u$-values dominates the additive terms bounded by $k+2$, and the assumption $n > k$ ensures this. The more subtle load-bearing concern is actually in the backward direction of Lemma 5.11, where the inductive argument that forces each 2-path to map to the correct grid cell depends on the interplay between the edge-colourful condition, the temporal ordering, and the construction of the $H$-colouring. I traced through this argument and found it sound: the non-packing edges are assigned the highest time-steps (item 4 in Definition 5.10), forcing them to be mapped to their own colour class first; then the inductive argument on the packing edges works because the temporal constraints and the grid structure of the time-assignment functions force each 2-path into the correct cell. The Claims 5.12 and 5.13 (which extract the clique) follow from the arithmetic properties of $t_ℓ$ and $t_r$. The overall structure of the dichotomy is sound: the upper bound (Theorem 1.12 + Lemma 1.16) and the lower bound (Lemma 5.8 + Corollary 5.14 + Lemma 5.15) are well-constructed and cross-validate through the toadwidth measure. The paper lacks formal verification, which would be valuable for the most intricate parts (Claim 5.3 with its sixteen numbered facts, and the DP in Section 4), but the arguments are specified in sufficient detail for manual verification. No adjustment to the ACCEPT verdict is warranted.","tokens_in":87831,"tokens_out":1097,"duration_ms":969399,"concrete_test":"Independently verify the inductive argument in the backward direction of Lemma 5.11 by explicitly constructing a small example: take $k=2$, $n=3$ (so $F$ is a graph on 3 vertices), and a pattern $H$ with a $P_2$-packing of size $(k+1)^2 - 1 = 8$. Compute all time-steps using equations (4)-(5) and Definition 5.10, then verify that any edge-colourful homomorphism from $(H, ≼)$ to $(G, τ, c)$ must map each 2-path to the correct cell, and that the resulting vertex selections form a 2-clique in $F$. If any valid edge-colourful homomorphism fails to induce a clique, the backward direction fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption targets the arithmetic separation properties in Lemma 5.9 (equations 4-5). I checked these: the functions are $t_ℓ(u,h,v) = (u+1)n^2(h+1) + (v+1)$ and $t_r(u,h,v) = (u+1)n^2(k+v+2) + (h+1)$, where $u ∈ [n)$ and $n = |V(F)| > k$. The three inequalities in Lemma 5.9 follow because the dominant term $(u+1)n^2$ creates gaps of size $n^2$ between consecutive values of $u$, while the additive perturbation is at most $k+2 < n < n^2$. The arithmetic is sound and no edge case breaks the strict inequalities. The more subtle load-bearing point is in the backward direction of Lemma 5.11 (edge-colourful homomorphism ⇒ $k$-clique). The argument first establishes that edges outside the $P_2$-packing must map to their own colour class (using the fact that they receive the $κ$ highest time-steps), and then uses an inductive argument to show each 2-path maps to the correct grid cell. The inductive step starts from $e^ℓ_{0,k}$ (the last edge in the order) and works backwards. The key claim is that if $e^ℓ_{0,k}$ is NOT mapped to a time of the form $t_r(u,k,k)+1$, then some earlier edge in the order must map to a higher time, violating the temporal constraint. This relies on the edge-colourful condition ensuring that the colour $e^ℓ_{0,k}$ must be hit, combined with the fact that all edges coloured $e^ℓ_{0,k}$ have times of the form $t_r(u,k,k)+1$. The argument is correct but intricate: it depends on the edge-colourful condition being maintained throughout the induction, which is guaranteed because the colours of the $P_2$-packing edges are distinct from the colours of the non-packing edges (by construction of the $H$-colouring). No internal inconsistency found.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the structural expressivity and parameterised complexity of counting homomorphisms from temporal patterns to temporal graphs. A temporal pattern consists of a graph H together with a partial order on its edges, and a temporal homomorphism must preserve both adjacency and the temporal constraints. The paper makes three main contributions: (1) a temporal Lovász-style isomorphism theorem, showing that two temporal graphs are order-isomorphic if and only if they have the same homomorphism counts from all temporal patterns; (2) an FPT algorithm for counting temporal homomorphisms from patterns of bounded 'toadwidth' — the cliquewidth of a mixed graph (the order-augmented dual) that encodes both the line graph structure and the temporal constraints; (3) a complete complexity dichotomy for totally ordered temporal patterns, classifying tractability along the semi-induced matching number of the line graphs of the underlying graphs.","tokens_in":88046,"tokens_out":9201,"duration_ms":315913,"significance":"The paper addresses a genuine gap in the theoretical understanding of temporal motif counting, which has been studied extensively in applied settings but lacks the kind of comprehensive complexity-theoretic framework that exists for static graphs. The Lovász-style theorem (Theorem 1.6) establishes that temporal homomorphism counts fully determine the isomorphism type of a temporal graph under order-isomorphism, providing a foundational justification for the homomorphism-counting approach. The toadwidth measure and associated DP algorithm (Theorem 1.12) provide a natural temporal analogue of the well-known treewidth-based FPT algorithm for static homomorphism counting, and the connection to line graph cliquewidth is well-motivated. The dichotomy (Theorem 1.15) is the most technically demanding result: the upper bound connects toadwidth to semi-induced matching number via a polynomial bound (Lemma 1.16), and the lower bound uses an intricate grid-based reduction from Clique (Lemma 5.8). The tractability criterion is explicit and checkable. Overall, this is a substantial and well-executed contribution to parameterised counting complexity.","major_comments":[{"comment":"Equations (4) and (5) in Section 5.2.1 define t_ℓ(u,h,v) = (u+1)n²(h+1) + (v+1) and t_r(u,h,v) = (u+1)n²(k+v+2) + (h+1). The notation 'n²(h+1)' is ambiguous: it can be read as n^2·(h+1) or as n^{2(h+1)}. The proof of Lemma 5.9 only works under the latter reading (n raised to the power 2(h+1)). Under the natural reading n^2·(h+1), the second inequality in the proof of part (a) — '2n²(h+3) < n²(h+4)' — simplifies to 2(h+3) < h+4, i.e., h < -2, which is impossible. Since Lemma 5.9 is load-bearing for the correctness of the lower bound (Lemma 5.11 → Lemma 5.8 → Corollary 5.14 → Theorem 1.15), this notation should be clarified to use explicit exponent notation, e.g., n^{2(h+1)} instead of n²(h+1). The mathematics is correct under the intended reading, but the current notation risks serious misinterpretation.","section":null}],"minor_comments":[{"comment":"Definition 2.3 states that ϑ is 'a surjection from E(H) → R', but R is a poset, not a set. This should say 'to the ground set of R', as correctly stated in Definition 1.2.","section":null},{"comment":"Section 4 (the DP algorithm) spans approximately 15 pages. While the level of detail is appreciated for verification, adding a concise high-level summary of the DP state and recurrence at the beginning of the section — before the full case analysis — would improve readability.","section":null},{"comment":"In the proof of Lemma 5.9, the chain of inequalities uses notation like 'n²h+3' which is hard to parse. Using consistent exponent notation throughout (e.g., n^{2h+3}) would help.","section":null},{"comment":"The paper switches between P = (H, R, ϑ) for general temporal patterns and P = (H, ≼) for totally ordered patterns. While this is explained, a brief reminder at the start of Section 5 would help the reader.","section":null},{"comment":"In Definition 1.1, the condition τ(e) ≠ τ(e') for parallel edges is noted as equivalent to the Kempe-Kleinberg-Kumar model. A one-line remark on how the complexity results transfer to the snapshot model would be welcome, since the snapshot model is also widely used.","section":null},{"comment":"The bound in Lemma 1.16 (toadwidth ≤ 4b⁴ + 12b³ + 14b² + 6b + 2) is stated without much intuition for the specific polynomial. A brief remark on why this particular form arises (e.g., from the counting argument in Claim 5.3) would be helpful.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong theory contribution that would fit well in a journal like ACM Transactions on Computation Theory or SIAM Journal on Computing. The three results are complementary and each is individually significant. The main concern (notation in equations 4-5) is a presentation issue, not a correctness issue — I verified the arithmetic under the intended reading and it is sound. The DP algorithm in Section 4 is the most technically involved part and appears correct upon careful checking; the 9-case analysis for the relabeling operation is exhaustive and the cases are pairwise disjoint. I would encourage the authors to consider whether the toadwidth-based upper bound can be tightened or simplified in future work, as the current DP is quite involved."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper does three things: a temporal Lovász theorem, an FPT algorithm via a new width measure called toadwidth, and a dichotomy for totally ordered patterns. All three are new and the paper fills a genuine gap between extensive applied work on temporal motifs and the lack of theoretical foundations. The toadwidth measure is the standout contribution. The observation that line-graph cliquewidth is the natural temporal analogue of treewidth for static homomorphism counting is a real insight — temporal constraints live on edges, so you operate on the line graph, and the order-augmented dual adds arcs for the temporal ordering. This is not an arbitrary cliquewidth variant; it is the right object. The Lovász theorem adaptation is clean. The inclusion-exclusion trick in Lemma 3.4 to convert between strict and non-strict temporal constraints is the correct approach and handles the subtlety about edges mapped to the same time step. The dichotomy (Theorem 1.15) is complete with an explicit, checkable tractability criterion — bounded semi-induced matching number of line graphs — and the upper and lower bounds cross-validate each other. The soft spots are in proof intricacy, not in the ideas. The DP in Section 4 handles all five clique-expression operations, but the relabeling case requires nine sub-cases tracking which label class contains witnesses for earliest and latest times. This is correct but dense, and hard to verify without working through it line by line. Claim 5.3 (bounding equivalence classes to get the toadwidth bound) runs through sixteen numbered facts in a multi-stage greedy argument — the longest and most fragile proof in the paper. The arithmetic separation in Lemma 5.9 is sound; I checked it and the n² gaps dominate the additive perturbation as claimed. The backward direction of Lemma 5.11 is intricate but correct — the edge-colourful condition does the work it needs to. The toadwidth bound in Lemma 1.16 is loose (degree 4 in b), but that does not matter for the FPT result. One limitation: the FPT algorithm restricts to patterns without parallel edges, which they flag honestly. This is a paper for parameterised complexity theorists and people working on temporal graph algorithms. A reader who wants to understand the landscape of temporal motif counting gets a clear map from it. It deserves a serious referee who is willing to work through the longer proofs.","headline":"Solid theory paper with a natural new width measure and a complete dichotomy; main risk is proof intricacy, not correctness of the ideas.","tokens_in":88663,"tokens_out":1612,"would_cite":true,"duration_ms":104582,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Counting temporal motifs: full dichotomy and a Lovász theorem","keywords":["temporal graphs","homomorphism counting","parameterised complexity","Lovász theorem","cliquewidth","dichotomy","fixed-parameter tractability","temporal motifs"],"falsifier":"A counterexample to the dichotomy would be a class of graphs whose line graphs have unbounded semi-induced matching number but for which counting temporal homomorphisms from totally ordered patterns is nonetheless fixed-parameter tractable—this would require either a fundamentally different algorithm that bypasses toadwidth, or a flaw in the clique reduction that prevents it from working for that particular class. Alternatively, a failure of the arithmetic separation properties in the time-assignment functions for small values of k or n could break the reduction and leave the lower bound unpro","tokens_in":87995,"feed_emoji":"⏱️","tokens_out":1385,"duration_ms":70416,"temperature":0.7,"pith_summary":"The paper studies the problem of counting how many times a small temporal pattern—essentially a graph whose edges carry a partial order encoding temporal precedence constraints—appears inside a large temporal graph whose edges each have a specific time label. The authors prove three main results. First, they establish a temporal analogue of Lovász's celebrated isomorphism theorem: two temporal graphs are isomorphic (under a natural notion called order-isomorphism, which preserves the relative ordering of time steps without requiring exact time values to match) if and only if they receive the same number of homomorphisms from every possible temporal pattern. This confirms that temporal homomorphism counts completely determine temporal graph structure, just as static homomorphism counts determine static graph structure. Second, they introduce a new width measure called toadwidth (temporally order-augmented dual width), defined as the cliquewidth of a mixed graph whose vertices are the edges of the pattern, with undirected edges for shared endpoints and directed arcs for temporal ordering constraints. They give a dynamic programming algorithm that counts temporal homomorphisms in fixed-parameter tractable time when the toadwidth of the pattern class is bounded. Third, for the important special case where the temporal ordering is a total order on the pattern's edges, they prove a complete complexity dichotomy: assuming FPT is not equal to W[1], counting is tractable if and only if the line graphs of the underlying static patterns have bounded semi-induced matching number—a combinatorial parameter measuring how many disjoint edge-pairs can avoid cross-adjacencies. The tractable direction follows by bounding toadwidth as a polynomial function of this parameter; the hard direction follows by a reduction from the clique problem that embeds the pattern into a grid structure where temporal constraints force any valid homomorphism to encode a clique.","feed_headline":"Counting temporal motifs: full dichotomy and a Lovász theorem","feed_subtitle":"A new width measure and a sharp tractability boundary for pattern counting in time-labelled graphs.","key_machinery":"The toadwidth is the cliquewidth of the order-augmented dual: a mixed graph built from the pattern by treating each edge as a vertex, adding undirected edges between edges that share an endpoint, and adding directed arcs for each temporal ordering constraint. The FPT algorithm does dynamic programming along a clique-expression for this mixed graph, maintaining for each active label class a small set of 'centre' vertices (at most four per class) whose images must be guessed, plus the earliest and latest time-steps to which each label class's edges are mapped. The dichotomy's upper bound connects toadwidth to semi-induced matching number via a construction that builds a clique-expression by in","core_discovery":"The central discovery is that the complexity of counting temporal homomorphisms is governed not just by the graph structure of the pattern but by the interaction between graph structure and temporal constraints, captured by the toadwidth measure. For totally ordered patterns, this interaction reduces to a clean combinatorial criterion on the underlying static graph—bounded semi-induced matching number of its line graph—yielding a sharp boundary between tractable and intractable cases. The temporal Lovász theorem further establishes that temporal homomorphism counts are structurally complete: they determine temporal graph isomorphism exactly, placing temporal motif counting on the same firmal","pith_inferences":["If toadwidth indeed characterises tractability for all temporal patterns (not just totally ordered ones), it would play the same role for temporal homomorphism counting that treewidth plays for static homomorphism counting—making it the definitive structural parameter for the temporal setting.","The connection between semi-induced matching number and tractability suggests that the obstruction to efficient counting is the presence of many independent pairs of edges that can be ordered independently, which geometrically resembles a grid-like structure in the line graph—echoing the role of grid minors in treewidth lower bounds.","The inclusion-exclusion technique used to relate strict and non-strict temporal homomorphisms in the Lovász theorem proof could serve as a bridge to relate the complexity of counting temporal subgraph embeddings (injective homomorphisms) to counting temporal homomorphisms, potentially extending the dichotomy to subgraph counting."],"forward_implications":["The toadwidth measure and its FPT algorithm immediately yield efficient counting for temporal walks, temporal paths, and other patterns whose temporal constraints follow the graph structure, providing a unified algorithmic framework for previously ad-hoc results on specific temporal motifs.","The temporal Lovász theorem opens the door to homomorphism-indistinguishability characterisations for temporal graphs, potentially yielding hierarchies of temporal graph classes analogous to those in the static setting, with connections to temporal graph neural network expressiveness.","The dichotomy for total orders suggests that extending the lower-bound technique—embedding patterns into grids whose cells are enforced by temporal constraints—to partial orders could resolve whether bounded toadwidth is necessary and sufficient for tractability in full generality.","The reduction from clique via grid-embedded temporal patterns provides a template for proving hardness of other temporal counting problems by encoding combinatorial structures into the interplay between graph edges and temporal constraints."],"fun_headline_variants":["Temporal homomorphism counts determine temporal isomorphism exactly","Toadwidth governs the complexity of counting temporal motifs","Counting temporal motifs: a Lovász theorem plus a toadwidth dichotomy","When is counting temporal motifs tractable? A sharp boundary","Toadwidth: a new width measure for temporal pattern counting"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The W[1]-hardness lower bound relies on a reduction from the clique problem that assigns specific numeric time labels to edges using arithmetic functions whose separation properties ensure that temporal ordering constraints force any valid homomorphism to map pattern edges into the correct grid cell. If these arithmetic separations fail for some edge case—say when vertex indices coincide in a way that breaks a strict inequality—the backward direction of the correctness proof,","fun_headline_variants_meta":{"raw":{"variants":["Temporal homomorphism counts determine temporal isomorphism exactly","Toadwidth governs the complexity of counting temporal motifs","Counting temporal motifs: a Lovász theorem plus a toadwidth dichotomy","When is counting temporal motifs tractable? A sharp boundary","Toadwidth: a new width measure for temporal pattern counting","Counting temporal motifs is FPT for bounded-toadwidth patterns","Temporal Lovász theorem: homomorphism counts characterize isomorphism","A dichotomy for counting temporal motifs via toadwidth","Homomorphism counts pin down temporal graph isomorphism","Bounded toadwidth makes temporal motif counting tractable","A clean dichotomy for counting totally ordered temporal motifs"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":1890,"prompt_tokens":527,"completion_tokens":1363,"prompt_tokens_details":null},"tokens_in":527,"tokens_out":1363,"duration_ms":24588,"temperature":1.0,"reasoning_tokens":1201,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T04:19:14.449261+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A counterexample to the dichotomy would be a class of graphs whose line graphs have unbounded semi-induced matching number but for which counting temporal homomorphisms from totally ordered patterns is nonetheless fixed-parameter tractable—this would require either a fundamentally different algorithm that bypasses toadwidth, or a flaw in the clique reduction that prevents it from working for that particular class. Alternatively, a failure of the arithmetic separation properties in the time-assignment functions for small values of k or n could break the reduction and leave the lower bound unpro","supporting_citations":[],"review_version":1}