mathematical language, we say that a cut (S, V − S) is b -expanding, if the edges crossing this cut have total weight at least b times min{|S|, |V − S|}. A graph H(V, F) is said to be a b-expander, for some constant b, if for every for subset S ⊆ V, the cut (S, V − S) is b -expanding. Expander graphs have no small graph separators. Here, we will be interested in traffic graphs that are b-expanders for some constant b, and where the maximum degree of a node is at most d for some constant d. (The degree of a vertex is the sum of weights of all edges incident to it. We assume that the degree of each vertex is at least 1.) An important property of this class of graphs is that there is an efficient test to distinguish constant degree expander graphs from graphs with small separators. Indeed, this test is based on the spectral method, which works very well for constant degree expanders.

We said earlier that a clever choice of traffic graph will reveal a better way to partition the road network graph. How do we make this clever choice? The idea behind the new algorithm is to search for the best “expanding” traffic graph: which means among all expanding traffic graphs pick one that leads to the smallest traffic jams. This might seem counterintuitive. Shouldn’t locating the worst cut correspond to finding a traffic pattern that leads to the worst traffic jams?

To understand this point more clearly, let us introduce some notation. Let G(V, E) be the graph that we wish to partition, and H(V, F) be an expander graph on the same vertex set that we use as the traffic graph to route a traffic flow in G. Recall that this means that one unit of flow must be shipped between each pair of nodes connected by an edge in F. (In fact, the algorithm must allow fractional edges in F, which our description will ignore.) Suppose a is such that the sparsest cut in G(V, E) separates the set of vertices S ⊆ V from V − S, by cutting only a|S| edges. Thus a is a measure of how sparse the optimum cut is. Now, regardless of how the flow corresponding to H(V, F) is routed in G(V, E), at least |S| units of flow (traffic) must be routed between S and V – S. Since this must be routed through a bottleneck containing only a|S| edges, it follows that the worst edge-congestion must be at least 1/a. The real issue in designing an approximation algorithm for sparsest cuts is this: how much larger can the edge-congestion be than this lower bound of 1/a If it is no larger than C/a, then it will follow that we can approximate the sparsest cut (at least its numerical value) to within a factor of C in the worst case. To obtain the best results, we must try to minimize C. In other words, we wish to pick an expanding traffic graph which leads to the smallest traffic jams.

The main result in ARV⁶ on expander flows states that for any graph G(V, E) there is an expander graph H(V, F) that can be routed in G(V, E) with congestion at most O ( log n /a ). Moreover, using the powerful computational hammer of the ellipsoid algorithm for linear programming, the expander graph H(V, F) as well as its routing in G(V, E) minimizing edge-congestion can be computed in polynomial time. This gives an algorithm for sparsest cuts, different from the geometric one presented earlier, yet achieves the same O( log n ) approximation factor in the worst case. It also serves as a starting point for a new framework for

designing very efficient algorithms for finding sparse cuts.

In the rest of this section, we will sketch the proof of the main expander flows result of ARV. ⁶ To do so, we shall generalize the router/toll-collector game from Section 1. 2 to incorporate the selection of an expanding traffic graph. The existence of an expanding traffic graph that achieves the desired O ( log n ) bound will follow from understanding the equilibrium of the game. Since we are interested in the equilibrium solution, rather than detailing an efficient procedure for getting to equilibrium, it is easier to formulate the game as lasting for a single round.

In the generalized game, the toll-collector not only specifies a toll for each edge (the sum of all edge tolls is n, the number of vertices in G), but also a set of prizes. Each prize is associated with a cut in the graph, and is collected when a path crosses the cut. The number of possible cuts is 2ⁿ of course, and the toll collector selects some subset of cuts to place prizes on, such that the sum of all cut prizes is 1. We associate with each pair of vertices the total prize for moving from one vertex to another—the sum of cut prizes for all cuts that separate the two vertices. The task of the routing player is to select a pair of vertices, separated by total cut prize of at least b (where b is a given constant), such that the total toll paid in moving between these vertices is as small as possible. The goal of the toll player is to assign edge tolls and cut prizes to maximize the toll paid by the routing player. It can be shown using linear programming duality that this payoff is essentially the congestion of the best expander flow. The main idea is that the flow player’s optimal strategy is specified by a probability distribution over pairs of vertices, which we may view as defining the desired expander graph (for any balanced cut, a random edge from this graph must cross the cut with probability at least b ).

Let us consider how the toll player can maximize his take. Assume that G(V, E) has a balanced separator with an edges crossing the cut. Then by assigning a prize of 1 to this cut and a toll of 1/a on each edge of this cut, the toll player can force the routing player to pay at least 1/a, simply because the routing player is forced to route flow between two vertices on opposite sides of this optimal cut. Can the toll player force the route player to pay a lot more? We show that he cannot force him to pay more than O( log n /a ): no matter how the toll player determines tolls and picks a set of cuts, the routing player can always pick a pair of vertices which are separated by a b fraction of the cuts, and such that the cheapest path between them costs O( log n /a ). The proof of this fact relies upon the geometric view from the previous section.

To make this connection, we start by viewing the set of cuts as defining a hypercube—each cut corresponds to a dimension, and each vertex gets a ± 1 label depending upon which side of the cut it lies. It is natural to associate each vertex in the graph with a vertex of the d-dimensional hypercube, where d is the number of cuts. We observed in the previous section that the d-dimensional hypercube can be embedded on the surface of a unit sphere in ℜ^d and satisfy the triangle inequality. By the main geometric theorem of ARV, it follows that there are two large almost antipodal