Fault-Tolerant Spanners and their Applications

Hairong Zhao, NJIT

Spanners are spanning subgraphs that contain short paths between
the vertices that are connected by an edge in the original graph.
Spanners provide a sparse or economic representation of graphs.
They have many applications in robotics, graph theory, network
topology design, distributed systems. Fault-tolerant spanners, are
spanning subgraphs that remain as spanners even after removing a
vertex or an edge. Fault-tolerant spanners are natural extensions
of spanners to graphs resistant to edge and vertex removal.

In this talk, I will discuss two different techniques of
constructing ``good'' fault-tolerant spanners. First, I will show that a
generalized greedy algorithm constructs $k$-fault tolerant
geometric spanners such that both the vertex degree and total
weight are optimal. I will also describe an efficient algorithm
for constructing near optimal fault-tolerant geometric spanners.
Then I will present a new different algorithm that constructs $1$-fault
tolerant spanners of planar graphs which at the same time is at
most a constant factor heavier than the minimum-weight
2-Edge-connected (or 2-vertex-connected) spanning subgraphs. This
is the first non-trivial result about fault-tolerant spanners
besides geometric graphs. Finally, I will demonstrate an
application of our spanner result to design a quasi-polynomial
time approximation scheme (QPTAS) for constructing a
minimum-weight 2-Edge-connected (or 2-vertex-connected) spanning
subgraphs of a weighted planar graph. Our result improves upon a
very recent result by Czumaj et.al. that finds a
$(1+\epsilon)$-approximation in time $n^{O(w(G)/OPT(G))}$.

Joint work with
Andre Berger (Emory), Artur Czumaj(NJIT),
Michelangelo Grigni(Emory), and Papa Sissokho (Emory)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%