  Expander graphs play a central role in graph theory and algorithms. With a
number of powerful algorithmic tools developed around them, such as the
Cut-Matching game, expander pruning, expander decomposition, and algorithms for
decremental All-Pairs Shortest Paths (APSP) in expanders, to name just a few,
the use of expanders in the design of graph algorithms has become ubiquitous.
Specific applications of interest to us are fast deterministic algorithms for
cut problems in static graphs, and algorithms for dynamic distance-based graph
problems, such as APSP.
  Unfortunately, the use of expanders in these settings incurs a number of
drawbacks. For example, the best currently known algorithm for decremental APSP
in constant-degree expanders can only achieve a $(\log
n)^{O(1/\epsilon^2)}$-approximation with $n^{1+O(\epsilon)}$ total update time
for any $\epsilon$. All currently known algorithms for the Cut Player in the
Cut-Matching game are either randomized, or provide rather weak guarantees.
This, in turn, leads to somewhat weak algorithmic guarantees for several
central cut problems: for example, the best current almost linear time
deterministic algorithm for Sparsest Cut can only achieve approximation factor
$(\log n)^{\omega(1)}$. Lastly, when relying on expanders in distance-based
problems, such as dynamic APSP, via current methods, it seems inevitable that
one has to settle for approximation factors that are at least $\Omega(\log n)$.
  In this paper we propose the use of well-connected graphs, and introduce a
new algorithmic toolkit for such graphs that, in a sense, mirrors the above
mentioned algorithmic tools for expanders. One of these new tools is the
Distanced Matching game, an analogue of the Cut-Matching game for
well-connected graphs. We demonstrate the power of these new tools by obtaining
better results for several of the problems mentioned above.
