Skip to content

Eric Price: Edge-connectivity via Network-Coding

by on February 21, 2012

I’m not sure what my favorite “surprising” algorithm of all time is, but my favorite algorithm from the last couple years is for single-source edge connectivity via network coding (Ho Yee Cheung, Lap Chi Lau, Kai Man Leung, FOCS 2011).

The nicest, simplest case is for single-source edge connectivity on a DAG. If the source s has degree d, we will compute edge connectivity to all other nodes in O(md^2) time. We associate with each vertex v a subspace S_v of (F_q)^d, for q >> m^2 . At the beginning, S_s it the entire space, and S_v = {0} for v != s. We then visit each vertex in topological order. At each vertex v, we scan through the outgoing edges. For each edge out to a vertex u, we choose a random element x of S_v. We then update S_u to be the the subspace spanned by S_u and x. With probability 1-dn/q, at the end the edge connectivity to each vector v is the dimension of S_v.

Updating each subspace can be done in O(d^2) time, giving total time O(md^2). Correctness follows from network coding analysis: for any vertex t consider the min-cut of (s-t), which has size equal to the edge connectivity R. Then R vectors were sent from the component containing s to the component containing t, so every subspace in the component containing t is in the span of those R vectors; hence the dimension of S_t is at most R.

To show that the dimension is at least R with high probability, note that we can think of each “message” x sent from v to u as a random linear combination of the “messages” received by v, with the source receiving the d elementary unit vectors along dummy edges D_1, …, D_d. Define a variable k_{e, e’} to be the coefficient of the message sent across edge e in the message sent across e’, where the endpoint of e is the same as the start point of e’. Then the ith coefficient of the message sent along each edge e is sum_{paths ending at e and starting at D_i} product_{(e, e’) consecutive on path} k_{e, e’}.

Consider the R disjoint paths from s to t. We can create an R x d matrix M, where row contains the message received by t along one of the paths. We can regard M as a random variable over the variables k. If k_{e, e’} = 1 for (e, e’) along one of the R disjoint paths and 0 otherwise, then M will have full rank. Hence det(M) is a non-zero polynomial. But det(M) has degree at most dn, so the probability that det(M) is zero is at most dn/q by the Schwarz-Zippel lemma. But if M has full rank, then the R received messages are independent so S_t has dimension R as desired.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: