Pith. sign in

REVIEW 1 major objections 6 minor 82 references

The Parameterised Complexity of Temporal Motif Counting, and a Lov\'asz-Style Isomorphism Theorem

T0 review · 1 major / 6 minor · reviewed 2026-07-10 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Counting temporal motifs: full dichotomy and a Lovász theorem

desk verdict Solid theory paper with a natural new width measure and a complete dichotomy; main risk is proof intricacy, not correctness of the ideas. read the letter →

arxiv 2607.08614 v1 pith:YJGBRJVG submitted 2026-07-09 cs.CC cs.DM

Jayakrishnan Madathil , Kitty Meeks , Marc Roth This is my paper · ORCID
classification cs.CCcs.DM
keywords temporalgraphshomomorphismcountingparameterisedcomplexityLovásztheoremcliquewidthdichotomyfixed-parametertractabilitymotifs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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,

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

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.

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 (1)
  1. 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.
minor comments (6)
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found. Pure theory paper with self-contained proofs.

full rationale

This is a pure parameterised complexity theory paper with no fitted parameters, no empirical data, and no normalisation choices. I walked all three main derivation chains and found no circularity. (1) The Temporal Lovász Theorem (Theorem 1.6/3.1) adapts Lovász's original argument [32, external] using inclusion-exclusion (Lemma 3.4) and Möbius inversion over partition lattices (Lemma 3.6) to handle temporal constraints. The backward direction replaces Γ2 with Γ1 using the premise #Hom(P→Γ1)=#Hom(P→Γ2), which is the input assumption, not a fitted quantity. (2) The FPT algorithm (Theorem 1.12/Lemma 4.6) is a constructive dynamic program along cliquewidth expressions of the order-augmented dual; no parameter is fitted to data. (3) The dichotomy (Theorem 1.15) combines an upper bound (Lemma 1.16: bounded semi-induced matching number ⟹ bounded toadwidth, proved by explicit clique-expression construction in Lemma 5.1; then Theorem 1.12: bounded toadwidth ⟹ FPT) with a lower bound (Lemma 5.8: reduction from Clique via grid embedding; Lemma 5.15: inclusion-exclusion from coloured to uncoloured). These are independent arguments. The toadwidth (Definition 1.10) and semi-induced matching number (Definition 1.14) are defined independently of each other and of the results. The only author self-citations are [37, 38] (Roth's PhD thesis and a survey), cited once for the standard grid-to-clique reduction technique (Lemma 5.11, 'cf. [37, Claim 2.46]') and for background on parameterised counting — neither is load-bearing for the paper's central claims. The Lovász theorem is attributed to Lovász [32], not to the present authors. No step in any derivation chain reduces to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 4 invented entities

The paper is a pure mathematics/theoretical computer science paper. There are no free parameters (no data fitting, no hand-tuned constants). The axioms are all standard results from parameterised complexity theory and graph theory. The invented entities (toadwidth, order-augmented dual, order-isomorphism) are well-motivated and their properties are derived independently of the main results, with the dichotomy providing cross-validation between toadwidth and semi-induced matching number.

assumptions (5)
  • domain assumption FPT ≠ W[1]
    Invoked in Theorem 1.15 as the standard hardness assumption for the W[1]-hardness lower bound. This is the standard assumption in parameterised complexity theory, not specific to this paper.
  • standard math Lovász's Theorem for static graphs (Theorem 1.4)
    Used as the template for the temporal version; the proof adapts the original argument with inclusion-exclusion. Cited from Lovász [32].
  • standard math Dalmau-Jonsson dichotomy for static homomorphism counting
    Referenced in Section 1.1 (Toadwidth vs. Treewidth) as the static analogue: counting homomorphisms is FPT iff line graphs have bounded cliquewidth. Used to motivate the toadwidth definition.
  • standard math Bounded treewidth iff bounded cliquewidth of line graphs (Gurski-Wanke [22])
    Used to argue that toadwidth is the natural temporal analogue of treewidth, since the order-augmented dual extends the line graph with temporal arcs.
  • standard math Möbius inversion on the partition lattice
    Used in Lemma 3.6 to relate injective homomorphism counts to general homomorphism counts via quotients, following Lovász's original proof technique.
invented entities (4)
  • Toadwidth (temporally order-augmented dual width) independent evidence
    purpose: Width measure for temporal patterns, defined as the cliquewidth of the order-augmented dual mixed graph. Used as the tractability criterion for the FPT algorithm (Theorem 1.12).
    The dichotomy (Theorem 1.15) provides independent confirmation: bounded semi-induced matching number implies bounded toadwidth (Lemma 1.16), and unbounded semi-induced matching number implies W[1]-hardness. The measure is not circularly defined to make the algorithm work.
  • Order-augmented dual (oad) of a temporal pattern independent evidence
    purpose: Mixed graph with vertices = edges of the pattern, undirected edges for shared endpoints, and directed arcs for temporal constraints. The cliquewidth of this graph is the toadwidth.
    The construction is explicit (Definition 1.9) and the toadwidth bound in Lemma 1.16 is derived independently of the algorithm.
  • Order-isomorphism between temporal graphs independent evidence
    purpose: Notion of temporal graph isomorphism preserving the order of time steps but not their precise values. Used in the Lovász-style theorem (Theorem 1.6).
    The definition (Definition 1.5) is compared against existing notions (pointwise, timewise, and [24]'s version) with explicit examples (Figure 2) showing the distinctions.
  • Semi-induced matching number independent evidence
    purpose: Graph parameter: maximum size of a set of pairwise disjoint edges with no cross-edges between non-matching endpoints. Used as the dichotomy criterion for total orders.
    This is a standard graph parameter; the paper connects it to toadwidth via Lemma 1.16 and to W[1]-hardness via the reduction in Section 5.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Parameterised Complexity of Temporal Motif Counting, and a Lov\'asz-Style Isomorphism Theorem." pith.science (2026). https://pith.science/paper/YJGBRJVG

@misc{pith2026260708614,
  author       = {Pith},
  title        = {Pith review of: The Parameterised Complexity of Temporal Motif Counting, and a Lov\'asz-Style Isomorphism Theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YJGBRJVG}},
  note         = {Machine review of arXiv:2607.08614}
}
abstract

We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern $P$ consists of a graph together with a partial order on its edges, and a homomorphism from $P$ to a temporal graph must not only preserve edges, but also satisfy the temporal constraints imposed by the partial order of the edge set of the pattern. The main results of this work are three-fold: First, we prove a temporal Lov\'asz-style theorem, stating that two temporal graphs are isomorphic (under a natural definition of temporal isomorphisms) if and only if they have the same number of homomorphisms from all temporal patterns. Second, we introduce a cliquewidth-based measure on temporal patterns, called the temporally order-augmented dual width, the "toadwidth" for short, and show that counting temporal homomorphisms is fixed-parameter tractable for temporal patterns of bounded toadwidth. Third, we provide a parameterised complexity dichotomy with an explicit tractability criterion for counting homomorphisms from totally ordered temporal patterns, classified along their underlying graph structure.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

82 extracted references · 82 canonical work pages

  1. [1]

    The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree , booktitle =

    Marco Bressan and Matthias Lanzinger and Marc Roth , editor =. The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree , booktitle =. 2023 , url =. doi:10.1145/3564246.3585204 , timestamp =

    work page doi:10.1145/3564246.3585204 2023

  2. [3]

    Benson and Jure Leskovec , editor =

    Ashwin Paranjape and Austin R. Benson and Jure Leskovec , editor =. Motifs in Temporal Networks , booktitle =. 2017 , url =. doi:10.1145/3018661.3018731 , timestamp =

    work page doi:10.1145/3018661.3018731 2017

  3. [4]

    IEEE Transactions on Knowledge and Data Engineering , volume=

    Temporal network motifs: Models, limitations, evaluation , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2021 , publisher=

    work page 2021

  4. [5]

    Discover Data , volume=

    A powerful lens for temporal network analysis: temporal motifs , author=. Discover Data , volume=. 2025 , publisher=

    work page 2025

  5. [6]

    The complexity of counting homomorphisms seen from the other side , journal =

    V. The complexity of counting homomorphisms seen from the other side , journal =. 2004 , url =. doi:10.1016/J.TCS.2004.08.008 , timestamp =

    work page doi:10.1016/j.tcs.2004.08.008 2004

  6. [7]

    Can You Beat Treewidth? , journal =

    D. Can You Beat Treewidth? , journal =. 2010 , url =. doi:10.4086/TOC.2010.V006A005 , timestamp =

    work page doi:10.4086/toc.2010.v006a005 2010

  7. [8]

    Complexity of

    Radu Curticapean and D. Complexity of. Proc.\ of IEEE FOCS , pages =. 2014 , doi =

    work page 2014

  8. [9]

    Homomorphisms are a good basis for counting small subgraphs , booktitle =

    Radu Curticapean and Holger Dell and D. Homomorphisms are a good basis for counting small subgraphs , booktitle =. 2017 , _url =. doi:10.1145/3055399.3055502 , timestamp =

    work page doi:10.1145/3055399.3055502 2017

Show all 82 references
  1. [10]

    2024 , url =

    Jacob Focke and Marc Roth , title =. 2024 , url =. doi:10.1137/22M1512211 , timestamp =

    2024 doi

  2. [11]

    Counting Small Induced Subgraphs with Edge-Monotone Properties , booktitle =

    Simon D. Counting Small Induced Subgraphs with Edge-Monotone Properties , booktitle =. 2024 , url =. doi:10.1145/3618260.3649644 , timestamp =

    2024 doi

  3. [12]

    Benson and Moses Charikar , editor =

    Paul Liu and Austin R. Benson and Moses Charikar , editor =. Sampling Methods for Counting Temporal Motifs , booktitle =. 2019 , url =. doi:10.1145/3289600.3290988 , timestamp =

    2019 doi

  4. [13]

    Arnaud Casteigts and Paola Flocchini and Walter Quattrociocchi and Nicola Santoro , title =. Int. J. Parallel Emergent Distributed Syst. , volume =. 2012 , url =. doi:10.1080/17445760.2012.668546 , timestamp =

    2012 doi

  5. [14]

    Finding Temporal Paths Under Waiting Time Constraints , journal =

    Arnaud Casteigts and Anne. Finding Temporal Paths Under Waiting Time Constraints , journal =. 2021 , url =. doi:10.1007/S00453-021-00831-W , timestamp =

    2021 doi

  6. [15]

    Bruno Courcelle and Stephan Olariu , title =. Discret. Appl. Math. , volume =. 2000 , url =. doi:10.1016/S0166-218X(99)00184-5 , timestamp =

    2000 doi

  7. [16]

    Juedes and Iyad A

    Jianer Chen and Benny Chor and Mike Fellows and Xiuzhen Huang and David W. Juedes and Iyad A. Kanj and Ge Xia , title =. Inf. Comput. , volume =. 2005 , _url =. doi:10.1016/j.ic.2005.05.001 , timestamp =

    2005 doi

  8. [17]

    Kanj and Ge Xia , title =

    Jianer Chen and Xiuzhen Huang and Iyad A. Kanj and Ge Xia , title =. J. Comput. Syst. Sci. , volume =. 2006 , _url =. doi:10.1016/j.jcss.2006.04.007 , timestamp =

    2006 doi

  9. [18]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =. 2001 , _url =. doi:10.1006/JCSS.2000.1727 , timestamp =

    2001 doi

  10. [19]

    On recognizing graphs by numbers of homomorphisms , journal =

    Zdenek Dvor. On recognizing graphs by numbers of homomorphisms , journal =. 2010 , url =. doi:10.1002/JGT.20461 , timestamp =

    2010 doi

  11. [20]

    Holger Dell and Martin Grohe and Gaurav Rattan , editor =. Lov. 45th International Colloquium on Automata, Languages, and Programming,. 2018 , url =. doi:10.4230/LIPICS.ICALP.2018.40 , timestamp =

    2018 doi

  12. [21]

    Parameterized Complexity Theory , series =

    J. Parameterized Complexity Theory , series =. 2006 , url =. doi:10.1007/3-540-29953-X , isbn =

    2006 doi

  13. [22]

    Hamilton and Jan Eric Lenssen and Gaurav Rattan and Martin Grohe , title =

    Christopher Morris and Martin Ritzert and Matthias Fey and William L. Hamilton and Jan Eric Lenssen and Gaurav Rattan and Martin Grohe , title =. The Thirty-Third. 2019 , url =. doi:10.1609/AAAI.V33I01.33014602 , timestamp =

    2019 doi

  14. [23]

    As Time Goes By: Reflections on Treewidth for Temporal Graphs , booktitle =

    Till Fluschnik and Hendrik Molter and Rolf Niedermeier and Malte Renken and Philipp Zschoche , editor =. As Time Goes By: Reflections on Treewidth for Temporal Graphs , booktitle =. 2020 , url =. doi:10.1007/978-3-030-42071-0\_6 , timestamp =

    2020 doi

  15. [24]

    Frank Gurski and Egon Wanke , title =. Discret. Math. , volume =. 2007 , url =. doi:10.1016/J.DISC.2007.01.020 , timestamp =

    2007 doi

  16. [25]

    Dabrowski and Matthew Johnson and Dani

    Konrad K. Dabrowski and Matthew Johnson and Dani. Clique-width for hereditary graph classes , booktitle =. 2019 , url =. doi:10.1017/9781108649094.002 , timestamp =

    2019 doi

  17. [26]

    2012 , url =

    Bruno Courcelle and Joost Engelfriet , title =. 2012 , url =

    2012

  18. [27]

    CoRR , volume =

    Franziska Heeg and Jonas Sauer and Petra Mutzel and Ingo Scholtes , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2505.24438 , eprinttype =. 2505.24438 , timestamp =

    2025 doi arXiv

  19. [28]

    Weisfeiler-Lehman goes dynamic: An analysis of the expressive power of Graph Neural Networks for attributed and dynamic graphs , journal =

    Silvia Beddar. Weisfeiler-Lehman goes dynamic: An analysis of the expressive power of Graph Neural Networks for attributed and dynamic graphs , journal =. 2024 , url =. doi:10.1016/J.NEUNET.2024.106213 , timestamp =

    2024 doi

  20. [29]

    Marc Roth , title =. Comput. Sci. Rev. , volume =. 2026 , url =. doi:10.1016/J.COSREV.2025.100837 , timestamp =

    2026 doi

  21. [30]

    Efficient computation of optimal temporal walks under waiting-time constraints , journal =

    Matthias Bentert and Anne. Efficient computation of optimal temporal walks under waiting-time constraints , journal =. 2020 , url =. doi:10.1007/S41109-020-00311-0 , timestamp =

    2020 doi

  22. [31]

    On the Equivalence Between Temporal and Static Equivariant Graph Representations , booktitle =

    Jianfei Gao and Bruno Ribeiro , editor =. On the Equivalence Between Temporal and Static Equivariant Graph Representations , booktitle =. 2022 , url =

    2022

  23. [32]

    Antonio Longa and Veronica Lachi and Gabriele Santin and Monica Bianchini and Bruno Lepri and Pietro Lio and Franco Scarselli and Andrea Passerini , title =. Trans. Mach. Learn. Res. , volume =. 2023 , url =

    2023

  24. [33]

    Enright and Kitty Meeks and Hendrik Molter , title =

    Jessica A. Enright and Kitty Meeks and Hendrik Molter , title =. Algorithmica , volume =. 2025 , url =. doi:10.1007/S00453-025-01301-3 , timestamp =

    2025 doi

  25. [34]

    2012 , note =

    Temporal networks , journal =. 2012 , note =. doi:https://doi.org/10.1016/j.physrep.2012.03.001 , url =

    2012 doi

  26. [35]

    Expressive Power of Temporal Message Passing , booktitle =

    Przemyslaw Andrzej Walega and Michael Rawson , editor =. Expressive Power of Temporal Message Passing , booktitle =. 2025 , url =. doi:10.1609/AAAI.V39I20.35396 , timestamp =

    2025 doi

  27. [36]

    and Bertin, Nicolas and Hao, Tong and Goldberg, Debra S

    Han, Jing-Dong J. and Bertin, Nicolas and Hao, Tong and Goldberg, Debra S. and Berriz, Gabriel F. and Zhang, Lan V. and Dupuy, Denis and Walhout, Albertha J. M. and Cusick, Michael E. and Roth, Frederick P. and Vidal, Marc , title =. Nature , volume =. 2004 , doi =

    2004

  28. [37]

    Communication motifs: a tool to characterize social communications , booktitle =

    Qiankun Zhao and Yuan Tian and Qi He and Nuria Oliver and Ruoming Jin and Wang. Communication motifs: a tool to characterize social communications , booktitle =. 2010 , url =. doi:10.1145/1871437.1871694 , timestamp =

    2010 doi

  29. [38]

    Kleinberg and Amit Kumar , title =

    David Kempe and Jon M. Kleinberg and Amit Kumar , title =. J. Comput. Syst. Sci. , volume =. 2002 , url =. doi:10.1006/JCSS.2002.1829 , timestamp =

    2002 doi

  30. [39]

    2019 , url =

    Marc Roth , title =. 2019 , url =

    2019

  31. [40]

    Large Networks and Graph Limits , series =

    L. Large Networks and Graph Limits , series =. 2012 , url =

    2012

  32. [41]

    Tight Algorithms for Connectivity Problems Parameterized by Clique-Width , booktitle =

    Falko Hegerfeld and Stefan Kratsch , editor =. Tight Algorithms for Connectivity Problems Parameterized by Clique-Width , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ESA.2023.59 , timestamp =

    2023 doi

  33. [42]

    Fast exact algorithms for some connectivity problems parameterized by clique-width , journal =

    Benjamin Bergougnoux and Mamadou Moustapha Kant. Fast exact algorithms for some connectivity problems parameterized by clique-width , journal =. 2019 , url =. doi:10.1016/J.TCS.2019.02.030 , timestamp =

    2019 doi

  34. [43]

    Weisfeiler-lehman goes dynamic: An analysis of the expressive power of graph neural networks for attributed and dynamic graphs

    Silvia Beddar - Wiesing, Giuseppe Alessio D'Inverno, Caterina Graziani, Veronica Lachi, Alice Moallemy - Oureh, Franco Scarselli, and Josephine Maria Thomas. Weisfeiler-lehman goes dynamic: An analysis of the expressive power of graph neural networks for attributed and dynamic...

    2024

  35. [44]

    Efficient computation of optimal temporal walks under waiting-time constraints

    Matthias Bentert, Anne - Sophie Himmel, Andr \' e Nichterlein, and Rolf Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. Appl. Netw. Sci. , 5(1):73, 2020

    2020

  36. [45]

    Fast exact algorithms for some connectivity problems parameterized by clique-width

    Benjamin Bergougnoux and Mamadou Moustapha Kant \' e . Fast exact algorithms for some connectivity problems parameterized by clique-width. Theor. Comput. Sci. , 782:30--53, 2019

    2019

  37. [46]

    Time-varying graphs and dynamic networks

    Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distributed Syst. , 27(5):387--408, 2012

    2012

  38. [47]

    Finding temporal paths under waiting time constraints

    Arnaud Casteigts, Anne - Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. Algorithmica , 83(9):2754--2802, 2021

    2021

  39. [48]

    Juedes, Iyad A

    Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized N P -hard problems. Inf. Comput. , 201(2):216--231, 2005

    2005

  40. [49]

    Kanj, and Ge Xia

    Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. , 72(8):1346--1367, 2006

    2006

  41. [50]

    Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach , volume 138 of Encyclopedia of mathematics and its applications

    Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach , volume 138 of Encyclopedia of mathematics and its applications . Cambridge University Press, 2012

    2012

  42. [51]

    Upper bounds to the clique width of graphs

    Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discret. Appl. Math. , 101(1-3):77--114, 2000

    2000

  43. [52]

    Homomorphisms are a good basis for counting small subgraphs

    Radu Curticapean, Holger Dell, and D \' a niel Marx. Homomorphisms are a good basis for counting small subgraphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, C...

    2017

  44. [53]

    Complexity of C ounting S ubgraphs: O nly the B oundedness of the V ertex- C over N umber C ounts

    Radu Curticapean and D \' a niel Marx. Complexity of C ounting S ubgraphs: O nly the B oundedness of the V ertex- C over N umber C ounts. In Proc.\ of IEEE FOCS , pages 130--139, 2014

    2014

  45. [54]

    Dabrowski, Matthew Johnson, and Dani \" e l Paulusma

    Konrad K. Dabrowski, Matthew Johnson, and Dani \" e l Paulusma. Clique-width for hereditary graph classes. In Allan Lo, Richard Mycroft, Guillem Perarnau, and Andrew Treglown, editors, Surveys in Combinatorics, 2019: Invited lectures from the 27th British Combinatorial Confere...

    2019

  46. [55]

    The complexity of counting homomorphisms seen from the other side

    V \' ctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. , 329(1-3):315--323, 2004

    2004

  47. [56]

    Lov \' a sz meets weisfeiler and leman

    Holger Dell, Martin Grohe, and Gaurav Rattan. Lov \' a sz meets weisfeiler and leman. In Ioannis Chatzigiannakis, Christos Kaklamanis, D \' a niel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Cze...

    2018

  48. [57]

    Counting small induced subgraphs with edge-monotone properties

    Simon D \" o ring, D \' a niel Marx, and Philip Wellnitz. Counting small induced subgraphs with edge-monotone properties. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, C...

    2024

  49. [58]

    On recognizing graphs by numbers of homomorphisms

    Zdenek Dvor \' a k. On recognizing graphs by numbers of homomorphisms. J. Graph Theory , 64(4):330--342, 2010

    2010

  50. [59]

    Enright, Kitty Meeks, and Hendrik Molter

    Jessica A. Enright, Kitty Meeks, and Hendrik Molter. Counting temporal paths. Algorithmica , 87(5):736--782, 2025

    2025

  51. [60]

    Parameterized Complexity Theory

    J \" o rg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006

    2006

  52. [61]

    As time goes by: Reflections on treewidth for temporal graphs

    Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. As time goes by: Reflections on treewidth for temporal graphs. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to H...

    2020

  53. [62]

    Counting small induced subgraphs with hereditary properties

    Jacob Focke and Marc Roth. Counting small induced subgraphs with hereditary properties. SIAM J. Comput. , 53(2):189--220, 2024

    2024

  54. [63]

    On the equivalence between temporal and static equivariant graph representations

    Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv \' a ri, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 202...

    2022

  55. [64]

    Line graphs of bounded clique-width

    Frank Gurski and Egon Wanke. Line graphs of bounded clique-width. Discret. Math. , 307(22):2734--2754, 2007

    2007

  56. [65]

    Han, Nicolas Bertin, Tong Hao, Debra S

    Jing-Dong J. Han, Nicolas Bertin, Tong Hao, Debra S. Goldberg, Gabriel F. Berriz, Lan V. Zhang, Denis Dupuy, Albertha J. M. Walhout, Michael E. Cusick, Frederick P. Roth, and Marc Vidal. Evidence for dynamically organized modularity in the yeast protein--protein interaction ne...

    2004

  57. [66]

    Weisfeiler and leman follow the arrow of time: Expressive power of message passing in temporal event graphs

    Franziska Heeg, Jonas Sauer, Petra Mutzel, and Ingo Scholtes. Weisfeiler and leman follow the arrow of time: Expressive power of message passing in temporal event graphs. CoRR , abs/2505.24438, 2025

    2025 arXiv

  58. [67]

    Tight algorithms for connectivity problems parameterized by clique-width

    Falko Hegerfeld and Stefan Kratsch. Tight algorithms for connectivity problems parameterized by clique-width. In Inge Li G rtz, Martin Farach - Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, ...

    2023

  59. [68]

    Temporal networks

    Petter Holme and Jari Saramäki. Temporal networks. Physics Reports , 519(3):97--125, 2012. Temporal Networks

    2012

  60. [69]

    On the complexity of k- SAT

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k- SAT . J. Comput. Syst. Sci. , 62(2):367--375, 2001

    2001

  61. [70]

    Kleinberg, and Amit Kumar

    David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. , 64(4):820--842, 2002

    2002

  62. [71]

    Benson, and Moses Charikar

    Paul Liu, Austin R. Benson, and Moses Charikar. Sampling methods for counting temporal motifs. In J. Shane Culpepper, Alistair Moffat, Paul N. Bennett, and Kristina Lerman, editors, Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM 201...

    2019

  63. [72]

    Temporal network motifs: Models, limitations, evaluation

    Penghang Liu, Valerio Guarrasi, and Ahmet Erdem Sar y \"u ce. Temporal network motifs: Models, limitations, evaluation. IEEE Transactions on Knowledge and Data Engineering , 35(1):945--957, 2021

    2021

  64. [73]

    Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities

    Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Trans. Mach. Learn. Res. , 2023, 2023

    2023

  65. [74]

    Large Networks and Graph Limits , volume 60 of Colloquium Publications

    L \' a szl \' o Lov \' a sz. Large Networks and Graph Limits , volume 60 of Colloquium Publications . American Mathematical Society, 2012

    2012

  66. [75]

    Can you beat treewidth? Theory Comput

    D \' a niel Marx. Can you beat treewidth? Theory Comput. , 6(1):85--112, 2010

    2010

  67. [76]

    R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network Motifs : Simple Building Blocks of Complex Networks . Science , 298(5594):824--827, 2002. \_eprint: https://www.science.org/doi/pdf/10.1126/science.298.5594.824

    2002 doi

  68. [77]

    Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-F...

    2019

  69. [78]

    Benson, and Jure Leskovec

    Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. Motifs in temporal networks. In Maarten de Rijke, Milad Shokouhi, Andrew Tomkins, and Min Zhang, editors, Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM 2017, Cambridge, United Ki...

    2017

  70. [79]

    Counting problems on quantum graphs

    Marc Roth. Counting problems on quantum graphs . PhD thesis, Saarland University, Germany, 2019

    2019

  71. [80]

    Parameterised counting complexity theory

    Marc Roth. Parameterised counting complexity theory. Comput. Sci. Rev. , 59:100837, 2026

    2026

  72. [81]

    A powerful lens for temporal network analysis: temporal motifs

    Ahmet Erdem Sar y \"u ce. A powerful lens for temporal network analysis: temporal motifs. Discover Data , 3(1):14, 2025

    2025

  73. [82]

    Expressive power of temporal message passing

    Przemyslaw Andrzej Walega and Michael Rawson. Expressive power of temporal message passing. In Toby Walsh, Julie Shah, and Zico Kolter, editors, Thirty-Ninth AAAI Conference on Artificial Intelligence, Thirty-Seventh Conference on Innovative Applications of Artificial Intellig...

    2025

  74. [83]

    Communication motifs: a tool to characterize social communications

    Qiankun Zhao, Yuan Tian, Qi He, Nuria Oliver, Ruoming Jin, and Wang - Chien Lee. Communication motifs: a tool to characterize social communications. In Jimmy X. Huang, Nick Koudas, Gareth J. F. Jones, Xindong Wu, Kevyn Collins - Thompson, and Aijun An, editors, Proceedings of ...

    2010

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.