Temporalizing digraphs via linear-size balanced bi-trees
share
In a directed graph D on vertex set v_1,… ,v_n, a forward arc is an arc v_iv_j where i<j. A pair v_i,v_j is forward connected if there is a directed path from v_i to v_j consisting of forward arcs. In the Forward Connected Pairs Problem (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 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 RFCPP of FCPP, where the input is a strong digraph D and a set of requests R consisting of pairs {x_i,y_i}, there is no constant c>0 such that one can always find an enumeration realizing c.|R| forward connected pairs {x_i,y_i} (in either direction).
READ FULL TEXT