Maybe it’s a Saturday afternoon, your mother’s birthday is the following Tuesday, the mail truck has already come by your house, and you want to know the nearest post office that’s open on weekends so you can mail your mother’s birthday card in time for it to get to her by her birthday. This is the kind of problem solved (more abstractly) by my new preprint: “Reactive proximity data structures for graphs” (with Goodrich and Mamano, arXiv:1803.04555, to appear at LATIN 2018).

First, let me explain the “reactive” in the title. Basically it means that if you ask the same question at different times, different post offices will be open or closed, but they aren’t going to suddenly move to new locations. Much of the past research in dynamic graph algorithms uses a model of data in which a given graph is changing by the addition or removal of edges (or sometimes vertices) and each query tests the properties of the graph after each change. That is, maybe the city is putting in new roads, or closing existing ones, and you want to find a new route to the post office. Instead, we are looking at a model in which the graph is fixed, but there is a dynamic subset of its vertices, and each update changes this subset. You can think of it as switching on or switching off the vertex (or opening or closing the post office). This model is not new; it was introduced (as far as I know) by Frigioni and Italiano (“Dynamically switching vertices in planar graphs”, Algorithmica 2000), who mixed these updates with edge updates, and it appears in a more pure form in my paper “All maximal independent sets and dynamic dominance for sparse graphs” (SODA 2005 and ACM Trans. Alg. 2009). In our new paper, we call this the reactive model to distinguish it from other kinds of dynamic graph models.

Frigioni and Italiano studied whether pairs of vertices can reach each other through the switched-on part of the network, and my older paper studied whether everything in the graph is adjacent to a switched-on vertex. In the new paper we study the post office problem: where is the nearest switched-on vertex to a given query vertex? The solution we give applies to any graph family with a separator theorem. It consists of a static routing table from every vertex to every separator vertex, a priority queue at each separator vertex of the distances to all the switched-on vertices, and a recursive structure on each side of the separator. Each separator vertex provides a candidate solution to the query (its distance from the query vertex plus its distance to the nearest switched-on vertex) and the best candidate is the query answer. We have to be careful, though, to allow candidate answers in which the nearby switched-on vertex is on the same side of the separator as the query, because the solution path might still cross the separator in this case.

In a previous paper with Sid Gupta, Sid and I showed that road networks belong to a class of graphs with a separator theorem, even though they are typically nonplanar. So this method applies to the post office problem with actual post offices. But the nonlinear space requirements of our new data structure are a bit of a limitation, preventing it from being used for, say, the entire US road network. Our experiments also showed that, when the query answer is nearby (e.g. when post offices are densely distributed) it may be better to solve each query by Dijkstra’s algorithm (with early termination when it finds a switched-on vertex). In a large grid-like road network, we would expect this naive query algorithm to take time roughly proportional to the square of the distance to the result, which could be much smaller than our data structure’s time of the square root of the whole network. Maybe there’s a way of making a multi-scale distance-sensitive version of our data structure?

Finally, this seems like a good opportunity for a note about academic salami-slicing. In general, I’m against it: I think it’s preferable to publish one longer and stronger paper than to split the same material into two weaker ones, even though splitting can leave you with a better-looking publication record. In this case, our graph post office data structure was originally intended to have been part of my earlier work with a superset of the same authors on stable redistricting in road networks, where we needed it as a subroutine to make our nearest neighbor chain algorithm for stable matching more efficient. But the committee for SIGSPATIAL 2017 (where we published the stable redistricting paper) only allowed us four pages, so something had to be cut from it, and we decided that the post office data structure was the most self-contained and large enough piece. Now it’s a separate paper.