Short paths on one-way roads and Robbins’ theorem

Suppose our city is connected by a road network, and traffic is allowed to travel in both directions across a road. Our city is considering to make all of the roads one-way. Is there a way to pick a direction for each road and still be able to go between any two parts of the city? In other words, is there a way to orient the edges of the road network such that it is strongly connected? (Such an orientation is called a strong orientation.)

This question was answered back in 1939 by Robbins. Assuming our road network is connected, we only need to check to make sure that there is no bridge—not a civil engineer’s bridge, but a road that, when we remove it, the road network becomes disconnected. Having no bridge is an obvious necessary condition for admitting a strong orientation; if there is a bridge, then no matter which way we orient it, we’ll get stuck on one side of it. The other direction of Robbins’ theorem can be shown through an ear decomposition.

However, Robbins’ theorem does not ensure that you can quickly go from one part of the city to another in this one-way road network. For example, consider a cycle graph on n vertices. There are only two strong orientations of a cycle graph (think: clockwise and counter-clockwise). In each of these orientations, some origin-destination pairs will have distance n-1, whereas in the two-way road network the travel time is at most n/2.

This leads to the question—When can the roads be made one-way so that we can quickly travel between every two points? More formally, when does a graph admit an orientation in which the pairwise distances are all at most k?

A necessary condition is that there be no “distance-k bridge”—an edge that belongs to every path of length at most k between two vertices. In other words, the subgraph obtained by removing any single edge should also have diameter at most k.

If this “no distance-k bridge” condition were also sufficient, then this would provide an elegant generalization of Robbins’ theorem. Alas, it is not sufficient.

For example, consider the complete graph on 4 vertices. If a single edge is removed, the remaining graph has diameter 2. However, no orientation of the 4-vertex complete graph has diameter at most 2. (Try it out!)

It turns out that the problem: “given an undirected graph, does it admit an orientation that has diameter at most k?” is NP-complete. The special case k=2 was shown to be NP-complete by Chvátal and Thomassen in 1978. This suggests that there is no “nice” analogue of Robbins’ theorem for diameter-constrained orientations.

Advertisements

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