Edge-disjoint branchings in temporal digraphs

Victor Campos¹ ; Raul Lopes¹ ; Andrea Marino² ; Ana Silva

¹Universidade Federal do Ceará
²Università degli Studi di Firenze

The electronic journal of combinatorics, Tome 28 (2021) no. 4

Résumé

A temporal digraph ${\cal G}$ is a triple $(G, \gamma, \lambda)$ where $G$ is a digraph, $\gamma$ is a function on $V(G)$ that tells us the time stamps when a vertex is active, and $\lambda$ is a function on $E(G)$ that tells for each $uv\in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $v\in V(G)$. In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding $k$ edge-disjoint spanning branchings respectively rooted in given $R_1,\cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal digraphs. A branching ${\cal B}$ is vertex-spanning if the root is able to reach each vertex $v$ of $G$ at some time where $v$ is active, while it is temporal-spanning if each $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings ${\cal B}_1$ and ${\cal B}_2$ are edge-disjoint if they do not use the same edge of $G$, and are temporal-edge-disjoint if they can use the same edge of $G$ but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are $\mathsf{NP}$-complete, even under very strict assumptions.

Détail

DOI : 10.37236/10229

Classification : 05C20, 05C85, 68Q25
Mots-clés : spanning branching, base static digraph