# Report from WADS

I just returned from Victoria, BC, where the University of Victoria (under the capable local organization of Ulrike Stege) was the host for WADS, the Symposium on Algorithms and Data Structures. (The acronym made more sense when it was calling itself a workshop.)

Each of the three days of the workshop was scheduled to begin with an invited talk, although one of them had to be rescheduled due to United Airlines cancelling the flight from San Francisco to Victoria that should have carried one of the speakers. Apparently that connection has frequent issues; my taxi driver back to the airport was quite familiar with the phenomenon. My own connections involved Alaska Airlines and Seattle instead, but that didn't prevent three out of four of my flights from being delayed. Fortunately a scheduled two-hour layover saved me from missing the one non-delayed flight. Anyway, the three speakers were Bodo Manthey on smoothed analysis of local search (based on the principles that smoothed instances are unlikely to have small local steps and are likely to have large optimal solution values relative to any local minimum), Cyrus Shahabi on adding "spatial" to social networks (e.g. to infer social connections from colocation in order to design recommendation systems that put you into a bubble where you and your friends see the same recommendations), and Bernard Chazelle on what happens when you mix Markov processes (each state's new value gets replaced by a convex combination of neighboring states' values) with dynamic graphs (the definition of neighboring changes based on some function of the values).

Each day also had one of my own talks, on parametric closures, cycle bases, and contact graphs of circular arcs; I've put my talk slides online here, here, and here. And in addition I ended up being asked to chair two of the sessions. So my choice of which contributed talks to see was somewhat constrained, and there were several I would have liked to see but didn't. My recollections below of individual papers and talks are necessarily going to be somewhat haphazard, and I've probably gotten some speaker names and results wrong.

The first and last contributed talks that I saw were both by Ke Chan. In the first one, Wednesday morning, Chan presented a paper by Adrian Dumitrescu and Csaba Tóth giving an exponential bound on the number of convex polygons in a triangulated point set, tight to within a polynomial factor. It involved a cute trick for reducing the problem to convex position: by choosing an origin within one of the triangles, mapping the points radially to the unit circle, and careful retriangulation, all of the convex polygons containing the origin could be placed in bijection with the convex polygons of the new set, preserving the points belonging to each polygon but not which ones were vertices. Ke later presented the last talk of the conference, his own work with Dumitrescu on median-of-medians selection, in which he conjectured that one of the exercises in CLRS is wrong: if you modify the standard groups-of-5 deterministic selection algorithm to use groups of 3 or 4 instead, the natural recurrence for its runtime solves to \( O(n\log n) \) instead of linear, but it may not be possible to find an input that is as bad as the recurrence suggests, and slight modifications to the algorithm can be proven to be linear.

Also on Wednesday morning, Michael Kerber spoke on work with Sergio Cabello in which they solve motion planning problems by subdividing the free space of a moving object by a quadtree, whose cells are either completely free, completely obstructed, or mixed (still needing subdivision to determine whether they can be passed through). To test whether the obstructed cells completely separate the start and goal positions, they use a union-find data structure augmented by parity bits that can be used to detect a cycle of obstacles that crosses the start-goal line segment an odd number of times. But I think there are additional interesting data structural questions to study for this problem. In particular, some mixed cells might be completely surrounded by a ring of free cells, making it useless to subdivide them: any path through them could be replaced by a path through the ring. Can we detect these useless cells quickly somehow?

One of the Wenesday afternoon talks was by Fahad Panolan on the parameterized complexity of matroid girth. The girth of a matroid is the size of its smallest circuit (or equivalently of its smallest dependent set); for graphic matroids it's the same as the graph girth, for transversal matroids it's the size of the smallest Hall set (a subset of one side of a bipartite graph that cannot be the set of endpoints of a matching), for binary matroids it's the size of the smallest "even set" (apparently a notorious open problem in parameterized complexity) and for linear matroids of low rank it includes the problem of detecting whether a point set is in general position or not. The paper presented strong complexity-based evidence that the problem is not FPT for linear matroids when parameterized by rank or solution size, but is FPT when parameterized by a combination of rank and field size. It would be interesting to clarify whether field size can be replaced by field characteristic here, or whether the lower bounds for large fields work even when those fields have low characteristic.

If WADS had a best presentation award (it doesn't), my vote would have gone to Bill Bird, who spoke Thursday morning on his work with Wendy Myrvold on algorithms to generate all non-isomorphic colorings of graphs and for determining the distinguishing numbers of graphs (the minimum number of colors needed in a coloring that destroys all the symmetries of the graph). His algorithms aren't necessarily faster than previously-known ones, but they use significantly less memory, something that can be even more of a bottleneck than runtime when things are exponential. Unfortunately seeing this one meant that I missed the parallel talk by Chang and Yen, that among other things used Courcelle's theorem to prove fixed parameter tractability of finding polygonal contact representations of planar graphs parameterized by polygon complexity and graph treewidth.

There was only one Thursday afternoon session, making time for the conference excursion to Butchart Gardens followed by a nice beachside dinner. I had a choice between parameterized graph algorithms versus data structures, and ended up choosing the algorithms. The first paper of the session, by Li, Wang, Chen, and Cao, was on finding a spanning tree with at least \( k \) internal nodes. It was known that, if the given graph contains an independent set whose neighborhood has at most half its size, then the problem can be reduced to a smaller one, and previous approaches involved finding a depth-first spanning tree and (if it's not itself good enough but the graph is still large) using its leaves as the independent set, but that leads to a kernel of size \( 3k. \) Instead, the new paper shows that using 6-opt local moves on the tree to reduce its number of leaves leads to a \( 2k \)-size kernel and an \( O(4^k) \)-time parameterized algorithm.

Two other talks on Thursday, one in the morning and one in the afternoon, both considered puzzles in which you are trying to get from one point in a large state space to another by a sequence of local moves. The morning's paper, by a group of Japanese authors with David Kirkpatrick, involved getting from one coloring of a graph to another by swapping the colors of adjacent vertices, using as few swaps as possible. It's \( \mathsf{NP} \)-hard even for cubic planar bipartite graphs, but when there are only two colors it can be solved optimally by finding a minimum-weight collection of paths connecting pairs of opposite-colored mismatched vertices. In the afternoon, Amer Mouawad spoke about getting from one independent set to another by a sequence of 2-opt moves (removing one vertex and adding another). Without even trying to minimize the number of moves, it's hard for graphs of bounded treewidth, pathwidth, bandwidth, etc., although it can be solved polynomially for bounded tree-depth. Mouawad and his co-authors showed that nevertheless it's fixed-parameter tractable, parameterized by the independent set size, for a much broader class of sparse graphs including the graphs of bounded degeneracy and the nowhere-dense graphs.

There was a brief business meeting during the conference dinner. The WADS conference series has been organized for the last 26 years by Frank Dehne and Jörg Sack, but at the meeting Jörg announced that Frank would be stepping down, with Faith Ellen taking his place. I don't think the location for the next WADS (in two years) has been decided yet; in any case it wasn't announced.

Friday we could all sleep in because of the delayed invited talk, except for a couple of unfortunate attendees who left the dinner early and didn't hear the announcement about the changed schedule. Yannik Stein spoke first, about his work with Korman, Mulzer, van Renssen, Roeloffzen, and Seiferth on time-space tradeoffs for Voronoi diagrams. If you have only constant working memory, but linear read-only input memory and write-only output memory, you can still construct a Voronoi diagram in quadratic time. Stein's method trades off this bound with the usual sequential time bound for Voronoi diagrams by computing a good sample of the input, using it to divide the problem into many independent constant-space subproblems, and running all the subproblems in parallel so that when they need to scan the input they can all do so in a single batch.

In the same session, Amir Nayyeri spoke about an interesting definition of the distance between two points in the plane (or some higher dimensional space) given some sample of points on a manifold, that is supposed to capture the property that paths through the manifold are cheaper than paths across space. To define the length of a curve, one integrates the local feature size (distance to the nearest sample) along the curve; if you follow a polygonal path through sample points the result is approximately the sum of squares of edge lengths, but the definition works more generally. With only a single sample point, the optimal curve between any two points can be found by viewing the points on the plane through the two points and the sample as complex numbers (with the sample at zero), squaring them all, and then either connecting the two given points by a line segment (if they started within 90 degrees of each other) or by a two-segment path through the origin (otherwise). For larger samples they form a Voronoi diagram, place gateway points along the boundaries of the cells, and use the single-sample method within each cell, giving a polynomial time approximation scheme for the optimal curve.

Finally, in the afternoon session, Thatchaphol Saranurak spoke about the dynamic optimality conjecture. There are now two candidates for a self-adjusting online binary search tree data structure that might have a constant competitive ratio against all offline strategies for adjusting a binary search tree to be fast on an input sequence: splay trees and another data structure based on a greedy solution to a geometric reformulation of the problem (augmenting a point set to prevent any two points of the augmented set from determining an empty rectangle). If either of these methods is competitive, it must in particular be competitive against a deque, which can access items at the start and end of the sorted list only in constant time per operation, because it's not hard to simulate a deque by a binary search tree. However, only an inverse-Ackermann competitive ratio was known for splay trees. This talk presented an exponential-of-inverse-Ackermann competitive ratio for the greedy strategy, based on showing that the augmented point set avoids a certain pattern in the shape of a W. But more than this specific result, I think it's also interesting for handling insertion and deletion operations directly; past work in this area instead assumed a static set of keys.

I also have some photographs of attendees that I took during the conference; I haven't yet finished processing them but will put up another post here once I do.