Efficient Computing of Disaster-Disjoint Paths: Greedy and Beyond

In a network topology
$G$
, we say a set of st-paths are disaster-disjoint if no disaster strikes more than one path. In this poster, we explore the basic capabilities and limitations of greedy and more advanced algorithms for computing maximal collections of such paths in planar networks. An algorithm is greedy if it generates consecutive paths
$P_{1}, P_{2},\ldots$
according to a simple rule. In the simplest setting, the only rule is that
$P_{i+1}$
is the closest clockwise disaster-disjoint from
$P_{i}$
. We find that the simplest greedy may fail even when 1)
$G$
is planar, 2) each disaster region is connected, and 3) each node failure (apart from s and
$t$
) is considered possible. Adding a simple rule explained in [1] yields a correct polynomial-time algorithm for the above problem. Finally, we digest a recent related near-linear runtime algorithm of [2] solving a more general problem and discuss the underlying relations among the foundations of these algorithms.