Temporal Cycle Detection and Acyclic Temporalizations

doi:10.1007/978-3-032-09120-8_8

Temporal Cycle Detection and Acyclic Temporalizations

2026-01-01

0

PRE

AI

DOI：10.1007/978-3-032-09120-8_8

Original

Original request for help

Save

Abstract

En 中文

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 TEMPORALIZATION. 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 are also interested in ACYCLIC TEMPORALIZATION where we bound the lifetime of the resulting temporal digraph. For these two problems, 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 temporalizations resulting from arbitrary vertex orderings which solve all but one specific case.

Keywords:

Temporal graphs

Search algorithms

Connectivity

Cycles

Directed acyclic graphs

Detection

Temporalization

NP-completeness

Fixed-parameter tractability

Polynomial-time algorithms

Bounded lifetime

Temporal Cycle Detection and Acyclic Temporalizations

Abstract

Journal

Organization