Temporal Role Colouring

Ella Yates; Jessica Enright; Kitty Meeks; Puck Rombach

REVIEW 2 major objections 5 minor 15 references

Temporal role colouring is NP-complete, but tractable on sparse networks

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 10:15 UTC pith:H7GI4TNQ

load-bearing objection New problem definition and two FPT results are solid, but the tree-interval-membership width FPT claim as written is XP, not FPT, and needs a fix. the 2 major comments →

arxiv 2607.29272 v1 pith:H7GI4TNQ submitted 2026-07-31 cs.DM math.CO

Temporal Role Colouring

Jessica Enright , Kitty Meeks , Puck Rombach , Ella Yates This is my paper

classification cs.DM math.CO MSC 68Q2705C8568R10

keywords temporal role colouringtemporal graphsparameterised complexityfixed-parameter tractabilityfinite automatatreewidthvertex-interval-membership widthtree-interval-membership width

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper introduces temporal role colouring, a dynamic version of the classic role colouring problem in graphs, and maps its computational complexity. The central claim is that the decision problem is NP-complete in general, via a reduction from the static role colouring problem. To handle this hardness, the paper gives three fixed-parameter tractability results: one parameterised by vertex-interval-membership width and automaton states, one by tree-interval-membership width and automaton states, and one by the treewidth of the underlying graph together with lifetime and number of colours. A sympathetic reader should care because these results identify when role assignments that evolve over time — e.g., roles in a dynamic contact network — can be computed efficiently rather than being intractable.

Core claim

The paper's central discovery is a complexity classification for temporal role colouring. It defines a k-colour role automaton whose states carry a colour and extra bookkeeping, and whose input word at each vertex is the sequence of colour-sets of its neighbours over the lifetime. A temporal graph admits a temporal role colouring exactly when every vertex's neighbourhood-colour word is accepted by the automaton. The paper proves NP-completeness by a polynomial reduction from static R-role colouring, using a two-state-per-role automaton and a temporal graph of lifetime 1. It then shows the problem is fixed-parameter tractable when parameterised by (i) the vertex-interval-membership width plus

What carries the argument

The central object is the k-colour role automaton: a finite automaton whose states are coloured by roles and whose input alphabet is all subsets of [k], so that the word read by a vertex is the sequence of colour-sets of its neighbourhoods over time. The automaton's ε-transitions from the start state allow a vertex to choose its initial role, and its other transitions enforce which neighbourhood colour-sets permit which role changes. The three algorithms use, respectively, dynamic programming over the vertex-interval-membership sequence; a reduction to a component-exchangeable temporally uniform problem that can be solved by a meta-algorithm on a tree-interval-membership decomposition; and d

Load-bearing premise

The FPT claim for tree-interval-membership width rests on the runtime of the cited meta-algorithm and on an algebraic simplification in the proof that is not valid as written — if the meta-algorithm runtime is only as quoted, that parameterisation yields at best XP time.

What would settle it

Compute the two sides of the equality O(nΛρ^{12φ³}3^{12φ³}(3Λn)^{4φ⁹}ρφ³) = O((nΛ)⁵(3ρ)^{12φ³}ρ^{φ¹²}) for concrete values such as φ=2, n=Λ=ρ=10; the left side contains a factor (300)^{2048}, while the right side is only polynomial in n and Λ, so the claimed identity fails and the FPT conclusion is unsupported.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

The NP-completeness result means that unrestricted temporal role colouring cannot be solved efficiently unless P=NP, so practical algorithms must exploit structure.
The vertex-interval-membership width FPT algorithm runs in O(Λρ^{3ω+1}ω²), so temporal role colouring is polynomial-time solvable when few vertices are active across each interval and the automaton has few states.
The treewidth-based FPT algorithm runs in O(Λ n ω (ρ²+ωk) 2^{6k(Λ+1)(ω+1)}), making the problem tractable on networks of bounded treewidth when lifetime and colour count are small.
The TIM-width result, if valid, generalises the vertex-interval-membership approach to disconnected snapshot components, allowing more efficient decomposition-based processing.
The component-exchangeable temporally uniform formulation indicates that other temporal problems with local neighbourhood dependencies may admit the same meta-algorithmic treatment.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The proof of the TIM-width FPT bound (Theorem 4) contains a questionable algebraic simplification: the left-hand runtime places n and Λ inside an exponent that depends on the parameter, which would not be FPT unless the cited meta-algorithm has a stronger bound than quoted. A corrected analysis or a direct FPT argument is needed to settle this parameterisation.
The automaton model restricts spontaneous role changes to the start state, so role changes can only be triggered by reading neighbourhood colours; an extension allowing spontaneous role changes at any time could alter the complexity landscape and is worth exploring.
The paper's three parameters are all sparse-structure measures; a natural testable extension is how the problem behaves on dense but structured temporal graphs, such as those with bounded temporal cliquewidth or modular-width, which the discussion notes as future work.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

New problem definition and two FPT results are solid, but the tree-interval-membership width FPT claim as written is XP, not FPT, and needs a fix.

read the letter

Colleague,

The short version: this paper defines a natural temporal analogue of role colouring, proves it NP-complete by a clean reduction, and gives two detailed FPT algorithms. But the headline FPT result for tree-interval-membership width has a load-bearing runtime error. It should go to review, not be rejected, because the flaw looks fixable and the rest is worth having.

What's genuinely new and good: the automaton-based definition of temporal roles is sensible and the reduction from static role colouring is straightforward and correct. The VIM-width DP (Algorithms 1 and 2) is real, and the supporting lemmas mostly line up despite recurring off-by-one inconsistencies in the notation F_{\Lambda-t} vs F_{\Lambda-t+1}; I read those as typos, not conceptual gaps. The treewidth DP in Section 5 is also well-structured: the introduce/forget/join lemmas are plausible and the runtime, O(\Lambda n \omega (\rho^2 + \omega k) 2^{6k(\Lambda+1)(\omega+1)}), is honest FPT for the stated parameter set.

The trouble is Theorem 4. The proof quotes the meta-algorithm from [6] with a factor (3\Lambda n)^{4\phi^9}. Since the exponent depends on the parameter \phi, this is n^{O(\phi^9)} \Lambda^{O(\phi^9)}, which is XP, not FPT, for the parameter pair (\rho, \phi). The simplification step that absorbs this factor into (n\Lambda)^5 is not valid: you cannot fold a parameter-dependent exponent into a constant-degree polynomial. Unless the actual meta-algorithm in [6] has a strictly stronger bound, e.g., a factor (\Lambda n)^{O(1)} with exponent independent of \phi, the theorem does not deliver what the abstract promises. This is a real soft spot, and it is isolated: the NP-completeness result and the other two FPT theorems do not rely on it.

One smaller thing: the paper leans on its own earlier meta-algorithm, but Lemma 3 independently proves that temporal role colouring fits the required template, so the self-citation is not the issue. The problem is just the runtime quoted from [6].

Who should read it: anyone working on temporal graph algorithms or parameterized complexity. The problem definition is likely to become a reference point, and the VIM-width DP is a nice demonstration of the technique. My call: send it to peer review. A competent referee will catch the Theorem 4 issue, and the authors should be able to either correct the bound or weaken the claim. The paper deserves a revision, not a desk reject.

Referee Report

2 major / 5 minor

Summary. The paper defines temporal role colouring, where a temporal graph G and a k-colour role automaton A are given, and asks whether there is a colouring r:V×[Λ+1]→[k] such that for every vertex the word of neighbourhood colour sets is accepted by A. The main results are NP-completeness (Theorem 1), an FPT algorithm parameterized by the vertex-interval-membership width and the number of automaton states (Theorem 2), a claimed FPT algorithm parameterized by the tree-interval-membership width and number of states via a meta-algorithm (Theorem 4), and an FPT algorithm parameterized by the underlying treewidth, lifetime, and number of colours (Theorem 5).

Significance. The NP-completeness reduction is straightforward and clean. The VIM-width DP (Theorem 2) and the treewidth DP (Theorem 5) are described with detailed lemmas and their runtimes have the standard FPT form. The main gap is Theorem 4, whose proof does not establish an FPT bound as written. If that gap is repaired, the paper offers a useful new temporal variant of role colouring and two solid algorithmic contributions.

major comments (2)

[Section 4, Theorem 4] The proof applies Theorem 3 with k=1, |X|=ρ, b=1 and f(ϕ,x)=ρϕ^3, yielding O(nΛρ^{12ϕ^3}3^{12ϕ^3}(3Λn)^{4ϕ^9}ρϕ^3). The simplification to O((nΛ)^5(3ρ)^{12ϕ^3}ρ^{ϕ^12}) is invalid: the factor (3Λn)^{4ϕ^9} has n and Λ in an exponent that depends on ϕ, so the bound is n^{O(ϕ^9)}Λ^{O(ϕ^9)} times a function of ρ and ϕ, i.e. XP rather than FPT for the parameter pair (ρ,ϕ). This does not support the abstract's FPT claim for tree-interval-membership width. The authors must either correct the quoted meta-algorithm bound or provide an alternative FPT argument.
[Section 3, Algorithm 1 / Lemma 2] There are repeated off-by-one inconsistencies. Algorithm 1's Require states that F_{Λ−t+1} is the set of states accepting ∅^{Λ−t+1}, but line 7 tests membership in F_{Λ−t}; Algorithm 2 line 7 passes F_{Λ−t+1} (with an undefined t). Lemma 2's proof contains conflicting statements, e.g. 'α_t(v)∈F_{Λ−t+1}' versus 'α_{t+1}(v)∈F_{Λ−t}'. The intended checks appear to be F_{Λ−t} for vertices leaving U_t, but the presentation must be fixed so the algorithm and proof are consistent.

minor comments (5)

[Section 2, Theorem 1 proof] In the converse direction, 'r(N_G(v))=N_R(r(u))' should be 'r(N_G(v))=N_R(r(v))'.
[Section 4, Lemma 3] The transition test is written as δ(l_i(v), c(N_C(v))) = l_j(v); since δ returns a set, this should be l_j(v) ∈ δ(...). The same shorthand appears elsewhere (e.g., in the proof of Theorem 1).
[Section 5, Lemma 5 proof] The line ending '...∪ {π^*(u, t)} = β.' should read '= β(v, t)'.
[Section 4, Theorem 3 statement] The runtime expression 'O(nΛ|X|^{12ϕ^3}(3b)^{12kϕ^3}(3Λn)^{4kϕ^9}k^2f(ϕ,x))' is difficult to parse; please use clearer exponent grouping.
[Section 3, Definition 1] The definition of U_t uses 'uv, wv∈E(G)' without specifying that u and w are distinct; if distinctness is intended, it should be stated (though the current wording is conventional in this context).

Circularity Check

0 steps flagged

No significant circularity: the temporal-role-colouring definition, the NP-completeness reduction, and the vertex-interval-membership and treewidth FPT algorithms are self-contained. The tree-interval-membership FPT claim rests on a self-cited meta-algorithm and an invalid runtime simplification (a correctness gap, not a circular reduction).

full rationale

The derivation chain is self-contained except for one step. The problem definition (Def. 3) is new; the NP-completeness proof (Thm 1) is a direct bijective reduction from the static R-role colouring problem, whose NP-completeness is cited from the external work [8], and both directions are proven explicitly rather than assumed. The vertex-interval-membership-width FPT claim (Thm 2) is proven by a self-contained dynamic program (Algorithms 1-2, Lemmas 1-2) with explicit runtime O(Λρ^{3ω+1}ω²), which has the required FPT form for parameter (ρ,ω). The treewidth claim (Thm 5) is likewise proven fully in-paper (Lemmas 4-7) with runtime O(Λnω(ρ²+ωk)2^{6k(Λ+1)(ω+1)}), FPT in (k,Λ,ω). The only load-bearing external dependency is Theorem 3, the (k,X,f)-component-exchangeable meta-algorithm quoted from Enright et al. [6], which is a self-citation (Enright and Meeks are co-authors). This is genuine evidence, not circularity: the meta-algorithm is a general statement whose stated assumptions do not include temporal role colouring, and the paper independently proves (Lemma 3) that temporal role colouring fits those assumptions by explicitly constructing Tr, St, Val, and Fin. No parameter is fitted to data, and no claimed result is equivalent by construction to an input of the derivation. The real defect is confined to Theorem 4's proof: the line O(nΛρ^{12ϕ^3}3^{12ϕ^3}(3Λn)^{4ϕ^9}ρϕ^3) = O((nΛ)^5(3ρ)^{12ϕ^3}ρ^{ϕ^12}) is algebraically invalid because (3Λn)^{4ϕ^9} exponentiates n and Λ by a parameter-dependent exponent 4ϕ^9; as quoted, Theorem 3 yields only XP time n^{O(ϕ^9)}Λ^{O(ϕ^9)}g(ρ,ϕ), not FPT time for the parameter pair (ρ,ϕ). This is a derivational gap in one of the three advertised FPT results — a correctness risk, not a circular reduction — since the conclusion does not reduce to its own input. A stronger runtime in [6] or a revised argument would be needed to recover Theorem 4.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The paper introduces no empirical free parameters and no fictitious physical entities. Its central claims rest on standard prior complexity results, a self-cited meta-algorithm whose quoted runtime appears to yield XP rather than FPT, and standard automaton/tree-decomposition facts.

axioms (4)

domain assumption R-role colouring is NP-complete for any simple connected graph R on at least three vertices (Fiala & Paulusma [8]).
Used as the source problem in the NP-hardness reduction in Theorem 1.
domain assumption The meta-algorithm of Enright et al. [6] (Theorem 3) is correct and runs in the stated time O(nΛ |X|^{12ϕ^3} (3b)^{12kϕ^3} (3Λn)^{4kϕ^9 k^2} f(ϕ,x)).
Load-bearing for Theorem 4; the paper's simplification of this bound to an FPT runtime is not justified.
standard math Automaton acceptance of a word of length Λ can be checked in O(Λρ^2) time (Algorithm 13 of Esparza & Blondin [7]).
Used in the NP-membership argument and in the forget-node acceptance check in Section 5.
standard math Every tree decomposition can be transformed into a nice tree decomposition with O(ωn) nodes without increasing width (Cygan et al. [4]).
Used in the runtime analysis of the treewidth DP in Theorem 5.

pith-pipeline@v1.3.0-daily-deepseek · 18143 in / 35992 out tokens · 324381 ms · 2026-08-03T10:15:56.505939+00:00 · methodology

0 comments

read the original abstract

A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their neighbourhoods. This model is used to capture the idea of vertices having roles in a contact network, consistent with the set of roles of their contacts. We define an extension of the role colouring problem to temporal graphs. Temporal roles are defined via an automaton with states and transitions capturing both the current colour of a vertex and information about its current and past adjacencies. We show, by a reduction from the static problem, that the temporal role colouring problem is NP-complete. To contend with this intractability, we explore several parameterisations. We give fixed-parameter tractability results with respect to the number of states of the automaton combined with either the vertex-interval-membership width or the tree-interval-membership width of the temporal graph. We further show the problem is in FPT parameterised by the treewidth of the underlying graph, the lifetime of the temporal graph and the number of colours combined.

Figures

Figures reproduced from arXiv: 2607.29272 by Ella Yates, Jessica Enright, Kitty Meeks, Puck Rombach.

**Figure 1.** Figure 1: A role graph R representing roles in a restaurant with vertices {C, K, M, W} representing customers, kitchen staff, managers and wait staff respectively and a graph that is R-role colourable. that defines what an acceptable role colouring looks like. A graph G is R-role colourable if there is a colouring c of the vertices such that c(NG(v)) = NR(c(v)) for every vertex v ∈ V (G), where NG and NR denote the … view at source ↗

**Figure 2.** Figure 2: The role graph R and the automaton AR constructed by the hardness reduction. 3 Vertex-Interval-Membership Width In this section we give an fpt-algorithm for temporal role colouring with respect to the vertex-interval-membership width ω of the temporal graph G and the number of states ρ of the automaton A. Bumpus and Meeks [3] give an algorithm which computes ω in time O(ωΛ) where Λ is the latest time an ed… view at source ↗

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 2 linked inside Pith

[1]

https://sociopatterns.org/, [Accessed 25-06-2026]

SocioPatterns. https://sociopatterns.org/, [Accessed 25-06-2026]

2026
[2]

SAGE publications Ltd (2024)

Borgatti, S.P., Agneessens, F., Johnson, J.C., Everett, M.G.: Analyzing social net- works. SAGE publications Ltd (2024)

2024
[3]

Algorithmica 85(3), 688–716 (2023)

Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. Algorithmica 85(3), 688–716 (2023)

2023
[4]

Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 5. Springer (2015)

2015
[5]

arXiv preprint arXiv:2404.19453 (2024)

Enright, J., Hand, S.D., Larios-Jones, L., Meeks, K.: Structural parameters for dense temporal graphs. arXiv preprint arXiv:2404.19453 (2024)

Pith/arXiv arXiv 2024
[6]

arXiv preprint arXiv:2505.15699 (2025)

Enright, J., Hand, S.D., Larios-Jones, L., Meeks, K.: Families of tractable problems with respect to vertex-interval-membership width and its generalisations. arXiv preprint arXiv:2505.15699 (2025)

Pith/arXiv arXiv 2025
[7]

MIT Press (2023)

Esparza, J., Blondin, M.: Automata theory: An algorithmic approach. MIT Press (2023)

2023
[8]

Theoretical computer science349(1), 67–81 (2005)

Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theoretical computer science349(1), 67–81 (2005)

2005
[9]

Internet research 5(1), 19–22 (2004)

Golder, S.A., Donath, J.: Social roles in electronic communities. Internet research 5(1), 19–22 (2004)

2004
[10]

In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining

Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of online social net- works. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 611–617 (2006)

2006
[11]

The Journal of mathematical sociology1(1), 49–80 (1971)

Lorrain, F., White, H.C.: Structural equivalence of individuals in social networks. The Journal of mathematical sociology1(1), 49–80 (1971)

1971
[12]

Journal of Theoretical Biology220(3), 303–321 (2003)

Luczkovich, J.J., Borgatti, S.P., Johnson, J.C., Everett, M.G.: Defining and mea- suring trophic role similarity in food webs using regular equivalence. Journal of Theoretical Biology220(3), 303–321 (2003)

2003
[13]

Journal of Discrete Algorithms35, 1–8 (2015)

Purcell, C., Rombach, P.: On the complexity of role colouring planar graphs, trees and cographs. Journal of Discrete Algorithms35, 1–8 (2015)

2015
[14]

In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis

Scripps, J., Tan, P.N., Esfahanian, A.H.: Node roles and community structure in networks. In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis. pp. 26–35 (2007)

2007
[15]

Social Networks5(2), 193–234 (1983)

White, D.R., Reitz, K.P.: Graph and semigroup homomorphisms on networks of relations. Social Networks5(2), 193–234 (1983)

1983

[1] [1]

https://sociopatterns.org/, [Accessed 25-06-2026]

SocioPatterns. https://sociopatterns.org/, [Accessed 25-06-2026]

2026

[2] [2]

SAGE publications Ltd (2024)

Borgatti, S.P., Agneessens, F., Johnson, J.C., Everett, M.G.: Analyzing social net- works. SAGE publications Ltd (2024)

2024

[3] [3]

Algorithmica 85(3), 688–716 (2023)

Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. Algorithmica 85(3), 688–716 (2023)

2023

[4] [4]

Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 5. Springer (2015)

2015

[5] [5]

arXiv preprint arXiv:2404.19453 (2024)

Enright, J., Hand, S.D., Larios-Jones, L., Meeks, K.: Structural parameters for dense temporal graphs. arXiv preprint arXiv:2404.19453 (2024)

Pith/arXiv arXiv 2024

[6] [6]

arXiv preprint arXiv:2505.15699 (2025)

Enright, J., Hand, S.D., Larios-Jones, L., Meeks, K.: Families of tractable problems with respect to vertex-interval-membership width and its generalisations. arXiv preprint arXiv:2505.15699 (2025)

Pith/arXiv arXiv 2025

[7] [7]

MIT Press (2023)

Esparza, J., Blondin, M.: Automata theory: An algorithmic approach. MIT Press (2023)

2023

[8] [8]

Theoretical computer science349(1), 67–81 (2005)

Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theoretical computer science349(1), 67–81 (2005)

2005

[9] [9]

Internet research 5(1), 19–22 (2004)

Golder, S.A., Donath, J.: Social roles in electronic communities. Internet research 5(1), 19–22 (2004)

2004

[10] [10]

In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining

Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of online social net- works. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 611–617 (2006)

2006

[11] [11]

The Journal of mathematical sociology1(1), 49–80 (1971)

Lorrain, F., White, H.C.: Structural equivalence of individuals in social networks. The Journal of mathematical sociology1(1), 49–80 (1971)

1971

[12] [12]

Journal of Theoretical Biology220(3), 303–321 (2003)

Luczkovich, J.J., Borgatti, S.P., Johnson, J.C., Everett, M.G.: Defining and mea- suring trophic role similarity in food webs using regular equivalence. Journal of Theoretical Biology220(3), 303–321 (2003)

2003

[13] [13]

Journal of Discrete Algorithms35, 1–8 (2015)

Purcell, C., Rombach, P.: On the complexity of role colouring planar graphs, trees and cographs. Journal of Discrete Algorithms35, 1–8 (2015)

2015

[14] [14]

In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis

Scripps, J., Tan, P.N., Esfahanian, A.H.: Node roles and community structure in networks. In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis. pp. 26–35 (2007)

2007

[15] [15]

Social Networks5(2), 193–234 (1983)

White, D.R., Reitz, K.P.: Graph and semigroup homomorphisms on networks of relations. Social Networks5(2), 193–234 (1983)

1983