Temporal Cycle Detection and Acyclic Temporization
Davi de Andrade, Júlio Araújo, Allen Ibiapina, Andrea Marino, Jason Schoeters, Ana Silva · 2025
Read Temporal Cycle Detection and Acyclic Temporization by Davi de Andrade, Júlio Araújo, Allen Ibiapina, Andrea Marino, Jason Schoeters, Ana Silva (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02694.txt.
Introduction
Davi de Andrade and co-authors study cycles in temporal graphs, where edges carry time stamps. Their 2025 paper extends the classic idea of a loop in a directed graph to settings where travel must respect time order. Several sensible definitions of a temporal cycle arise, and each spawns its own questions.
Two problems anchor the work. One asks whether a given time-stamped graph contains a temporal cycle. The other asks how to assign times to a plain graph's edges so that no temporal cycle forms, sometimes within a set lifetime. The authors give fast search methods for some cases and hardness proofs for others. Simple vertex orderings, they show, settle almost all cases of the timing task.
Catalog record
| CREATOR | Davi de Andrade, Júlio Araújo, Allen Ibiapina, Andrea Marino, Jason Schoeters, Ana Silva |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02694
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Temporal Cycle Detection and Acyclic Temporization Davi de Andrade, Júlio Araújo, Allen Ibiapina, Andrea Marino, Jason Schoeters, Ana Silva Abstract In directed graphs, a cycle can be seen as a structure that allows its vertices to loop back to themselves, or as a structure that allows pairs of vertices to reach each other through distinct paths. We extend these concepts to temporal graph theory, resulting in multiple interesting definitions of a “temporal cycle”. For each of these, we consider the problems of Cycle Detection and Acyclic Temporization . For the former, we are given an input temporal digraph, and we want to decide whether it contains a temporal cycle. Regarding the latter, for a given input (static) digraph, we want to time the arcs such that no temporal cycle exists in the resulting temporal digraph. We’re also interested in Acyclic Temporization where we bound the lifetime of the resulting temporal digraph. Multiple results are presented, including polynomial and fixed parameter tractable search algorithms, polynomial-time reductions from 3-SAT and Not All Equal 3-SAT , and temporizations resulting from arbitrary vertex orderings which cover (almost) all cases. Universidade Federal do Ceará, [email protected] Universidade Federal do Ceará, [email protected] IRIF, CNRS & Université Paris Cité, [email protected] by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL) Universita degli Studi di Firenze, [email protected] funded by Italian PNRR CN4 Centro Nazionale per la Mobilità Sostenibile, NextGeneration EU - CUP, B13C22001000001. MUR of Italy, under PRIN Project n. 2022ME9Z78 - NextGRAAL: Next-generation algorithms for constrained GRAph visuALization, PRIN PNRR Project n. P2022NZPJA - DLT-FRUIT: A user centered framework for facilitating DLTs FRUITion. Universita degli Studi di Firenze, [email protected] by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL), and partially funded by Italian PNRR CN4 Centro Nazionale per la Mobilità Sostenibile, NextGeneration EU - CUP, B13C22001000001. MUR of Italy, under PRIN PNRR Project n. P2022NZPJA - DLT-FRUIT: A user centered framework for facilitating DLTs FRUITion. Universidade Federal do Ceará, [email protected] ccs Networks Network algorithms ccs Networks Network dynamics ccs Networks Network structure ccs Theory of computation Problems, reductions and completeness ccs Theory of computation Dynamic graph algorithms ccs Theory of computation Fixed parameter tractability ccs Theory of computation Backtracking ccs Mathematics of computing Paths and connectivity problems ccs Mathematics of computing Graph algorithms keywords temporal graphs, search algorithms, connectivity, cycles, directed acyclic graphs, detection, temporization, NP-completeness, fixed-parameter tractability, polynomial-time algorithms, bounded lifetime † † copyright: Davi de Andrade, Júlio Araújo, Allen Ibiapina, Andrea Marino, Jason Schoeters, and Ana Silva † † runningauthor: D. de Andrade, J. Araújo, A. Ibiapina, A. Marino, J. Schoeters, A. Silva 1 Introduction A temporal digraph with lifetime \tau is a pair \mathcal{D}=(D,\lambda) where D is a directed graph (or digraph), called underlying digraph, and \lambda is a function from A(G) to 2^{[\tau]} , called time function , or temporization . Temporal graphs are powerful for analyzing dynamic relationships and patterns over time. They are widely applied in social networks (e.g., trend detection, influencer analysis), epidemiology (disease spread modeling), and transportation (route optimization), and in general in contexts where evolving connections are key to understanding behavior, predicting events, and optimizing performance [ 19 , 20 , 12 , 16 ] . In temporal digraphs, a path 1 1 1 All paths are considered to be directed paths. from a vertex x to a vertex y , called a temporal x,y -path , is meaningful only if the times on its arcs follow a strictly increasing or non-decreasing sequence. The former, known as strict model , is applied, for example, in the representation of a public transportation system where each arc in the path corresponds to a bus or train that must be taken at a time which is later than the previous transport. The latter, called non-strict model , allows transitions to occur instantaneously. This is useful for scenarios like daily route availability, where multiple routes may be traversed in the same day if they are accessible. Cycles in static digraphs. In static digraphs, a cycle is a simple non-trivial path that starts and finishes at the same vertex. Cycles are fundamental structures within digraphs and they come up in a wide variety of applications, from computer science to engineering, biology, and social network analysis. For example, cycles are important in network routing to avoid routing loops and enhance efficiency. In operating systems and databases, deadlocks can be represented as cycles in a resource-allocation graph. In biochemical networks and protein interaction networks, cycles can represent feedback loops or recurring processes. The study of cycles, cycle detection, and cycle characterization is therefore central to graph theory and its applications in the real world. The following fundamental properties of cycles in static digraphs trivially hold and are equivalent in the static context: (i) there exists a vertex x in the cycle such that from x we can traverse the cycle and go back to x ; (ii) there exists a pair of vertices x,y in the cycle, such that x is able to reach y and y is able to reach x using the arcs involved in the cycle; (iii) for every vertex x in the cycle, starting from x , we can traverse the cycle and go back to x ; and (iv) for every pair of vertices x,y in the cycle, x is able to reach y and y is able to reach x using the arcs involved in the cycle. As said, for static digraphs, all of the four statements are equivalent and, note that (iii) is the for every version of (i) and (iv) is the for every version of (ii) . Cycle Definitions in Temporal graphs. Inspired by the properties (i) - (iv) above, we can define cycles in temporal digraphs, looking for cycles in the underlying digraph whose times satisfy such properties. Interestingly, while these properties are equivalent in static digraphs, in temporal digraphs they differ, and it makes sense to study both the for every and the there exists variations. We define the following types of cycles, considering (now and in the rest of the paper) only non-trivial temporal paths. In particular, given a temporal digraph \mathcal{D}=(D,\lambda) and a cycle C of D , we say that C is a temporal: simple-cycle if there exists a temporal x,x -path P such that E(P)=E(C) , for some x\in V(C) ; weak-cycle if there exist a temporal x,y -path P and a temporal y,x -path P^{\prime} such that E(P)\cup E(P^{\prime})=E(C) , for some pair x,y\in V(C) ; strong-cycle if there exists a temporal x,x -path P such that E(P)=E(C) , for every x\in V(C) . (a) (b) (c) Figure 1 : Examples of a simple-cycle, weak-cycle, and strong-cycle respectively, using the non-strict model. See Figure 1 for an example using the non-strict model. Figure 1 a corresponds to a simple-cycle as there is a vertex, namely v , able to go back to itself. Figure 1 b corresponds to a weak-cycle, as there is a pair of vertices, namely v and u , such that v is able to go to u and u is able to go to v . Note that this is not a simple-cycle because the two paths do not compose to allow v (or any other vertex) to go back to