Can I read Temporalizing Digraphs via Linear-size Balanced Bi-trees on EtoBox?

Temporalizing Digraphs via Linear-size Balanced Bi-trees by Bessy, Stéphane; Thomassé, Stéphan; Viennot, Laurent is a scholarly article available to read on EtoBox.

What is Temporalizing Digraphs via Linear-size Balanced Bi-trees about?

In a directed graph $D$ on vertex set $v_1,\dots ,v_n$, a \emph{forward arc} is an arc $v_iv_j$ where $i<j$. A pair $v_i,v_j$ is \emph{forward connected} if there is a directed path from $v_i$ to $v_j$ consisting of forward arcs. In the {\tt Forward Connected Pairs Problem} ({\tt FCPP}), the input is a strongly connected digraph $D$, and the output is the maximum number of forward connected pairs in some vertex enumeration of $D$. We show that {\tt FCPP} is in APX, as one can efficiently enumerate the vertices of $D$ in order to achieve a quadratic number of forward connected pairs. For this, we construct a linear size balanced bi-tree $T$ (an out-tree and an in-tree with same size which roots are identified). The existence of such a $T$ was left as an open problem motivated by the study of temporal paths in temporal networks. More precisely, $T$ can be constructed in quadratic time (in the number of vertices) and has size at least $n/3$. The algorithm involves a particular depth-first search tree (Left-DFS) of independent interest, and shows that every strongly connected directed graph has a balanced separator which is a circuit. Remarkably, in the request version {\tt RFCPP} of {

Author

Bessy, Stéphane; Thomassé, Stéphan; Viennot, Laurent

Published

2023

Language

EN