Menger's Theorem for Temporal Paths (Not Walks)

arXiv2206.15251MaRDI QIDQ6403628FDOQ6403628

Authors: Allen Ibiapina, Raul Lopes, Andrea Marino, Ana Silva 

Publication date: 30 June 2022

Abstract: A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its lifetime $au$. Walks are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasingly (i.e., non-decreasing) depending on the scenario. Paths are temporal walks where each vertex is not traversed twice. A temporal vertex is a pair $(u,i)$ where $u$ is a vertex and $iin[au]$ a timestep. In this paper we focus on the questions: (i) are there at least $k$ paths from a single source $s$ to a single target $t$, no two of which internally intersect on a temporal vertex? (ii) are there at most $h$ temporal vertices whose removal disconnects $s$ from $t$? Let $k^{\ast }$ be the maximum value $k$ for which the answer to (i) is YES, and let $h^{*}$ be the minimum value $h$ for which the answer to (ii) is YES. In static graphs, $k^{\ast }$ and $h^{*}$ are equal by Menger's Theorem and this is a crucial property to solve efficiently both (i) and (ii). In temporal graphs such equality has been investigated only focusing on disjoint walks rather than disjoint paths. We prove that, when dealing with non-strictly increasing temporal paths, $k^{\ast }$ is equal to $h^{*}$ if and only if $k^{\ast }$ is 1. We show that this implies a dichotomy for (i), which turns out to be polynomial-time solvable when $kle2$, and NP-complete for $kge3$. In contrast, we also prove that Menger's version does not hold in the strictly increasing model and give hardness results also for this case. Finally, we give hardness results and an XP algorithm for (ii).

This page was built for publication: Menger's Theorem for Temporal Paths (Not Walks)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403628)