{"id":"cb769616-23d1-4c5c-ad06-bc144cade5cb","arxiv_id":"2501.11697","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The directed temporal graph settings form a single reachability hierarchy topped by strict and simple graphs, while undirected settings split into two incomparable strands.","lead":"This paper maps out which kinds of temporal graphs, directed or undirected, can simulate which others while keeping the same reachability relations. It settles open questions in the hierarchy and shows directed temporal graphs form a single chain with strict-and-simple as the most powerful class.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.5's final 8-vs-6 edge count assumes the two center cliques are temporally disjoint, but only per-source inequalities are proved; a single six-edge labeling might serve both phases.","rationale":"Observation 4.13 (any directed reachability graph is realized by D & strict & simple via R(G) with all labels 1) is correct and gives the top of the hierarchy independent support. Support-dilation and reachability-dilation are plausible generalizations of [7], though the proof of Theorem 4.9 glosses over the DAG ordering of strongly connected components within a snapshot. The most exposed point is Lemma 4.5, the only separation that distinguishes D & proper & simple from D & non-strict & simple and thereby pins the bottom of the directed chain. The reader flagged Lemma 4.2's one-sentence impossibility proof and the 8-vs-6 counting; I agree with the latter but locate the gap more precisely: the counting treats the two required center cliques as edge-disjoint, while only per-vertex inequalities are established. A finite exhaustive search over label orders on the six directed edges of the triangle would settle whether a six-edge proper & simple labeling can satisfy both rounds; if it can, the separation fails, and if it cannot, the proof needs a short lemma making the disjointness explicit. The paper deserves conditional acceptance pending this check; no ad hominem or circularity concerns.","tokens_in":21268,"tokens_out":19244,"duration_ms":198274,"concrete_test":"Enumerate all 720 label orderings of the six directed edges among x,y,z (or solve a small SAT instance) and test whether any D & proper & simple labeling satisfies the constraints extracted from Lemma 4.5: per-source inequalities λ(ai,i) < λ(i,bf(i)) < λ(i,cg(i)) < λ(i,di) for each i; for each i, an early temporal path from i to every center j completing before λ(i,cg(i)) and a late temporal path from i to every center j starting after λ(i,cg(i)); and the forbidden-reachability conditions (c-rounds must not reach the b-vertices reachable from the f(i) centers). If such a labeling exists, the 8-vs-6 count is invalid and Lemma 4.5's separation must be reproven or is false; if none exists, the missing global-separation step can be supplied.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The directed hierarchy collapses to a single strand only if Lemma 4.5's separation D & non-strict & simple ̸⇝R D & proper & simple holds. Its final argument counts 8 temporal edges among the center vertices x,y,z: 'requiring an x,y,z-clique to exist at two different points in time. Each of these requires four temporal edges ... eight in total. However, at most six temporal edges can exist between x,y,z in a simple graph.' The per-source inequalities λ(ai,i) < λ(i,bf(i)) < λ(i,cg(i)) < λ(i,di) just proved only order labels incident to each i individually; they do not establish that all a-phase center paths complete before all c-phase center paths begin. Without such a global time separation, the two required cliques may share temporal edges, since each directed edge among x,y,z carries a single label and can serve both an early and a late reachability round. If sharing is possible, the 8-vs-6 contradiction collapses and Lemma 4.5 is unproven. This is the load-bearing step for the claimed single-strand directed hierarchy, not Lemma 4.2's terse proof, whose n+1 bound is in fact correct.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the framework of Casteigts, Corsini, and Sarkar for comparing temporal graph settings under bijective, support, reachability, and induced-reachability equivalence, adding the directed-vs-undirected dimension. The main claims are: (i) the directed reachability settings form a single-strand hierarchy in which directed & strict & simple is the most expressive class and directed & proper & simple the least, with strict classes strictly more expressive than non-strict classes; (ii) the undirected hierarchy has two incomparable strands, resolving two open questions from the prior work; and (iii) every undirected setting transforms into its directed counterpart under reachability equivalence, while no directed setting transforms into an undirected one. The paper introduces several transformations, including support-dilation and reachability-dilation, and uses a series of separating structures to establish strictness of the hierarchy.","tokens_in":21348,"tokens_out":14895,"duration_ms":147991,"significance":"If the results are correct, the paper provides a complete taxonomy of expressiveness for temporal graph settings under reachability equivalence, answering open questions from the CCS framework and clarifying the role of edge direction. The observation that any directed temporal graph can be transformed to a directed & strict & simple graph by taking its reachability graph as the footprint with a uniform label (Observation 4.13) is elegant and potentially very useful for transferring algorithmic results. The reachability-dilation construction with only linear label blow-up is also a valuable contribution. However, the central directed hierarchy rests critically on Lemma 4.5, whose proof is incomplete in a load-bearing way; until that gap is repaired, the main classification should be considered unproven.","major_comments":[{"comment":"The proof asserts that the a-phase and c-phase traversals of the center clique x,y,z must occur at two different points in time, and therefore require eight temporal edges among x,y,z, contradicting simplicity (at most six). The only supporting evidence is the per-source inequality λ(a_i,i) < λ(i,b_{f(i)}) < λ(i,c_{g(i)}) < λ(i,d_i), which orders labels of edges incident to each individual center vertex i. This inequality does not establish that all a-phase uses of the center-clique edges finish before any c-phase use begins. In particular, it does not preclude c_{g(i)} from reaching its entry center before the (unique) clique time and then using the same set of center-clique edges as the a-phase. Without a rigorous global-time-separation argument, the claimed 8-vs-6 contradiction collapses, and the separation D & non-strict & simple ̸⇝R D & proper & simple is not established. Since this separation is load-bearing for the single-strand directed hierarchy, the proof must be repaired or replaced.","section":"Section 4.1, Lemma 4.5 (final paragraph)"},{"comment":"The notation in the key concluding paragraph is inconsistent and prevents verification. The text lists edges (a_i,i), (c_{g(i)},i), (i,b_{f(i)}), (i,d_i), but then writes an inequality involving λ(i,c_{g(i)}), which is the reverse of the edge (c_{g(i)},i), and also refers to c_{f(i)} where c_{g(i)} is presumably meant. The intended inequality must be stated precisely, and its derivation from the reachability requirements (a_i reaches b_{f(i)} and d_i, c_{g(i)} reaches every d_j but no b_j) must be spelled out step by step.","section":"Section 4.1, Lemma 4.5 (final paragraph)"},{"comment":"The proof of Lemma 4.2 is a hand-wave: after reducing to the case of a directed cycle with n temporal edges, it states that 'it is impossible to label the edges in a way that forms strictly increasing temporal paths between all vertex pairs' without any argument. This lemma is used in Lemma 4.5 to conclude that a 3-vertex clique in a D & proper graph requires four temporal edges. Even if the n+1 lower bound is true, the proof as written is not sufficient for a formal paper; a rigorous argument (or a precise citation to a known theorem) is required.","section":"Section 4, Lemma 4.2"},{"comment":"The paper proposes an alternative definition of 'proper' for directed temporal graphs, forbidding equal labels only on edges of the form (u,v) and (v,x), and claims it is 'more convenient.' It is not shown to be equivalent, with respect to reachability, to the standard definition used throughout Sections 2–4, nor is it stated explicitly that all earlier directed results remain valid under the new definition. Since Observation 5.1 and Lemma 5.4 rely on this redefinition, the paper must either prove the equivalence of the two definitions in the relevant settings or use the standard definition consistently.","section":"Section 5, Definition 5.2"}],"minor_comments":[{"comment":"The name of the prior work is misspelled as 'Casteigt, Corsini, and Sakar'; it should be 'Casteigts, Corsini, and Sarkar.'","section":"Introduction"},{"comment":"The section is titled 'Saturation' but it actually presents the trivial reachability-graph construction of Observation 4.13, which is different from the undirected saturation process described earlier. The title should be changed or the relation to saturation should be explained.","section":"Section 4.3.2"},{"comment":"The labels in the figure and the edge sets E1–E4 should be checked for consistency; for instance, the text mentions labels 2.5 and 5.5 while the figure shows some values like 2.3 and 5.3, and it is not immediately clear which edges carry which labels.","section":"Section 4.1, Lemma 4.5 (construction)"},{"comment":"The phrase 'every direct edge (β,α) would form a directed triangle with the corresponding green edges (α,h_β^α), (h_β^α,β)' is confusing: if the direct edge is (β,α), the triangle would consist of (β,α), (α,h), (h,β), not the two green edges as listed. The sentence should be rephrased to identify the three edges of the forbidden triangle.","section":"Section 4.1, Lemma 4.5, Claim 1"},{"comment":"There are numerous typos and minor grammatical errors, including inconsistent ordering of 'simple & proper' versus 'proper & simple' (e.g., 'D & simple & proper' in Corollary 4.16 vs 'D & proper & simple' elsewhere), and phrases like 'the directed triangle still separates the strict setting from the proper and from the non-strict settings' that could be clearer. A thorough copyedit is recommended.","section":"Global"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an interesting and timely question and contains several useful ideas, but the proof of Lemma 4.5, which is essential for the main directed hierarchy, is currently incomplete in a way that a careful reader cannot fill in without substantial additional work. The authors should be asked to provide a complete proof of the global time-separation claim or to otherwise justify the 8-vs-6 edge count. I would also encourage them to fix the notation in that lemma and to clarify the status of the alternative definition of 'proper' in Section 5. The remaining results (Theorem 3.1, Observation 4.13, the dilation constructions) appear sound at the level of detail given, but the overall contribution cannot be assessed until the central separation is rigorously established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine extension of the CCS framework and a useful result for the temporal-graph subfield, but the central directed hierarchy has a load-bearing proof gap. The new material is the directed single-strand hierarchy—Observation 4.13, that every directed temporal graph is reachability-equivalent to a directed & strict & simple graph, is the clean top of that hierarchy—plus the resolution of CCS's undirected open question and the merged directed/undirected comparison. Observation 4.13 is almost too simple to be novel, but it is exactly the observation that makes the directed side organize into one strand.\n\nWhat is done well: the paper is explicit about what comes from CCS and what is new. Support-dilation and reachability-dilation are sensible generalizations, and the directed semaphore adapts cleanly. Theorem 3.1's proof strategy—forcing the footprint by forbidding shortcuts and then arguing no simple strict labeling works—looks sound. The paper fits no parameters and does not argue circularly; its reliance on CCS is legitimate background. The writing is mostly readable and the figures are genuinely helpful.\n\nThe soft spots are concentrated in Section 4. The load-bearing separation Lemma 4.5 is not fully proved. The final 8-vs-6 edge count assumes that the a-phase and c-phase each require a temporally disjoint x,y,z-clique. What is actually established is only per-source ordering: at each center i, λ(a_i,i) < λ(i,b) < λ(c,i) < λ(i,d). That does not imply that all a-phase traffic finishes before all c-phase traffic starts, and nothing rules out a single six-edge labeling serving both phases. This is the step on which the entire single-strand directed hierarchy depends, so it needs a real argument or independent verification. The stress-test note is right about this. I would not put the main weight on Lemma 4.2: its proof is one sentence, but the n+1 bound is correct; that is a presentation issue, not a correctness issue. Support-dilation's ordering and label-shifting details are also underspecified, and Theorem 4.15 is deferred to [7] rather than proved. The missing citation placeholder in the future-work section is minor.\n\nThis deserves a serious referee. The right outcome is likely major revision directed at Lemma 4.5 and the support-dilation details, not a desk reject. If Lemma 4.5 gets fixed or verified, the paper is a solid contribution.","headline":"Real contribution to temporal graph hierarchies, but the directed single-strand result rests on an unproved global-disjointness step in Lemma 4.5.","tokens_in":21997,"tokens_out":12303,"would_cite":true,"duration_ms":142427,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"For directed temporal graphs, every reachability pattern expressible in any natural setting is reproduced by a strict, single-labeled graph, so the directed hierarchy is one chain.","keywords":["temporal graphs","directed graphs","temporal reachability","reachability equivalence","strict vs non-strict paths","proper vs arbitrary temporal graphs","simple vs multi-labeled edges","dynamic networks"],"falsifier":"Exhibit a directed proper temporal graph on three vertices with exactly three temporal edges whose reachability graph is the complete directed graph; Lemma 4.2 says this cannot exist, and its existence would collapse the proof of Lemma 4.5, which separates non-strict & simple from proper & simple by counting six possible temporal edges against the eight needed for two three-vertex cliques.","tokens_in":20925,"feed_emoji":"🕰️","tokens_out":8546,"duration_ms":86534,"temperature":0.7,"pith_summary":"This paper sets out to order the natural settings of temporal graphs—whether time labels must strictly increase, whether adjacent edges may share a time, and whether an edge may carry several times—into a hierarchy by what reachability relations they can express, now adding the directed/undirected axis. The main claim is that for directed temporal graphs the hierarchy is a single chain: the strict & simple setting (every edge appears once, and paths must use strictly increasing times) can reproduce the reachability graph of every directed temporal graph, while no non-strict or proper class can reproduce everything the strict class can. For undirected graphs the paper closes the last open separation: non-strict & simple undirected graphs cannot be transformed into strict & simple ones without changing reachability, so the undirected hierarchy splits into two incomparable strands rather than one. The point of the hierarchy is transfer: a positive result in a more expressive class carries down to weaker classes, and a hardness result in a weaker class carries up.","feed_headline":"One label per edge captures every directed temporal reachability","feed_subtitle":"Directed settings form a single chain; undirected settings split into two incomparable strands.","key_machinery":"The machinery has three parts. The first is the reachability graph R(G), the static directed graph of who can reach whom, used as the invariant under comparison. The second is the saturation observation: replacing G by R(G) with uniform label 1 shows directed & strict & simple is universal for directed reachability. The third is a pair of structural lemmas: Lemma 4.1 says any directed cycle in a non-strict temporal graph creates at least one transitive reachability, so a 3-cycle with all labels 1 separates strict from non-strict; Lemma 4.2 says a proper directed graph on n > 2 vertices whose reachability graph is a clique must contain at least n + 1 temporal edges, and this count separates non-strict & simple from proper & simple. Two transformations carry the positive direction: support-dilation, which orders strongly connected components within each snapshot and dilates their interior to make the graph proper while preserving path supports, and reachability-dilation, which replaces each strongly connected component by a bidirected spanning tree with distinct increasing labels, preserving reachability with only a doubling of the lifetime. A directed semaphore gadget, which subdivides edges through auxiliary vertices and tilts labels by an edge-coloring, shows all directed settings are equivalent under induced-reachability.","core_discovery":"The paper's central discovery is that directedness changes the shape of the reachability hierarchy. The central move is Observation 4.13: given any directed temporal graph G, build a static directed graph on the same vertices with an edge (u,v) whenever u can reach v in G, and give every edge time label 1. In the strict & simple setting the only temporal paths of length one use the single label, and longer strict paths are impossible because 1 is not strictly greater than 1; hence the reachability graph is unchanged. Consequently directed & strict & simple, and therefore directed & strict, is the most expressive directed class. The paper then proves the matching negative results: a directed triangle with three label-1 edges has a reachability graph no non-strict directed graph can realize, because Lemma 4.1 forces an extra transitive reachability inside any cycle, and a four-vertex gadget built from two three-cliques at distinct times cannot be realized in directed & proper & simple, because Lemma 4.2 says a three-vertex clique in a proper graph needs four temporal edges while the simple setting permits only six edges between the three center vertices to cover two time steps. These results, together with support-dilation and reachability-dilation transformations, fix the full directed ordering and answer the two open undirected comparisons.","pith_inferences":["If the directed single-chain result is taken at face value, the realizability question for directed temporal graphs becomes nearly trivial: because every finite directed graph is its own reachability graph under the uniform-label-1 construction, the set of reachability graphs of any directed setting is exactly the set of all finite directed graphs.","The 8-versus-6 counting in the separation of non-strict & simple from proper & simple suggests a testable invariant: the minimal number of temporal edges needed to realize a clique at two distinct times in a simple proper graph, and checking whether any other three-vertex gadget could do it with fewer edges would probe the robustness of that separation.","A positive answer to the paper's remaining open question, whether undirected & non-strict graphs can be mapped to directed & proper & simple while preserving reachability, would mean that an undirected edge never needs more than one label per direction, unifying the non-strict undirected strand with the directed chain."],"forward_implications":["For problems that depend only on the reachability graph, studying directed & strict & simple graphs loses nothing, and algorithms or positive results there apply to every directed setting.","The two undirected strands are incomparable: reachability results cannot be transferred between the strict & simple and non-strict & simple undirected classes, although within each strand the usual transfer rules hold.","Every undirected temporal graph has a directed counterpart with the same reachability graph, but no directed temporal graph can be rewritten as an undirected one, so directed settings are strictly more expressive than undirected ones.","Strict classes dominate non-strict classes in both the directed and undirected hierarchies, so any reachability graph realizable by a non-strict class is also realizable by a strict class, with the reverse failing."],"supporting_citations":[{"why":"Defines the four equivalence notions and the strict/non-strict, proper, simple dimensions for undirected graphs, and supplies the dilation, saturation, and semaphore constructions that this paper generalizes to directed graphs, together with the two open questions that are answered here.","marker":"[7]"},{"why":"Supplies the fact that a strongly connected directed graph on n vertices with n edges must be a directed cycle, which underpins Lemma 4.2's edge count for proper graphs with clique reachability.","marker":"[14]"},{"why":"Shows that any undirected tree can be temporally connected with at most two labels per edge, an argument this paper adapts to bidirected spanning trees in reachability-dilation.","marker":"[9]"}],"fun_headline_variants":["Directed temporal reachability: one label per edge is enough","Strict and simple: the most expressive directed temporal class","Directed graphs collapse reachability hierarchy to a single chain","Undirected temporal reachability splits; directed does not"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a directed temporal graph in which no two touching edges share a time needs more temporal edges than vertices before every vertex can reach every other; the paper asserts this without a full derivation, and the separation between the single-label non-strict class and the single-label proper class depends directly on that count.","fun_headline_variants_meta":{"raw":{"variants":["Directed temporal reachability: one label per edge is enough","Strict and simple: the most expressive directed temporal class","Directed graphs collapse reachability hierarchy to a single chain","Undirected temporal reachability splits; directed does not"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000836,"raw_usage":{"total_tokens":3738,"prompt_tokens":1125,"completion_tokens":2613,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":741,"completion_tokens_details":{"reasoning_tokens":2548}},"tokens_in":741,"tokens_out":2613,"duration_ms":20405,"temperature":1.0,"reasoning_tokens":2548,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:58:42.563049+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a directed proper temporal graph on three vertices with exactly three temporal edges whose reachability graph is the complete directed graph; Lemma 4.2 says this cannot exist, and its existence would collapse the proof of Lemma 4.5, which separates non-strict & simple from proper & simple by counting six possible temporal edges against the eight needed for two three-vertex cliques.","supporting_citations":[{"cited_title":"Simple, strict, proper, happy: A study of reachability in temporal graphs","cited_arxiv_id":null,"evidence_quote":"Defines the four equivalence notions and the strict/non-strict, proper, simple dimensions for undirected graphs, and supplies the dilation, saturation, and semaphore constructions that this paper generalizes to directed graphs, together with the two open questions that are answered here."},{"cited_title":"Minimal strong digraphs","cited_arxiv_id":null,"evidence_quote":"Supplies the fact that a strongly connected directed graph on n vertices with n edges must be a directed cycle, which underpins Lemma 4.2's edge count for proper graphs with clique reachability."}],"review_version":1}