Top ten algorithms preprints of 2010

There were 643 preprints posted to the data structures and algorithms (cs.DS) section of arXiv.org in 2010, up from 499 in 2009 and 334 in 2008. Here is a very idiosyncratic top-ten of this year's crop (in chronological order, my own papers excluded).

• An \( O(\log\log n) \)-Competitive Binary Search Tree with Optimal Worst-Case Access Times, Prosenjit Bose, Karim Douïeb, Vida Dujmović, and Rolf Fagerberg, arXiv:1003.0139. When given random update sequences, binary search trees must take logarithmic time per update. But in most applications, the update sequences are not random. A very important open problem in data structures, the dynamic optimality conjecture, asks whether there is an adaptive binary search tree data structure that takes advantage of all possible non-randomness in the input, by achieving a constant competitive ratio when its time performance is compared against that of a rotation-based binary tree that performs the optimal sequence of rotations for a given input sequence. More specifically the conjecture is that splay trees are that optimal structure. While it is not known how to achieve constant competitive ratios, it is known how to get within a doubly-logarithmic factor of the optimal rotation sequence, but the known solutions paid the double-log penalty even in the worst case time per update. The new "zipper tree" data structure keeps the double-log competitive ratio of the best online algorithms, but combines it with the logarithmic worst-case update times of non-adaptive binary search tree data structures, getting the best of both worlds.

• Are there any good digraph width measures?, Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar, arXiv:1004.1485. Here "good" means something that acts like treewidth does for undirected graphs, in that bounded width leads to efficient algorithms for a big well-defined class of optimization problems. We would also like our width measures to be closed under something resembling graph minors (the lack of this closure makes other measures such as clique-width more difficult to use). And in addition, we would like an answer that is not just the trivial one of throwing away the edge orientations and using treewidth. The answer to the question seems to be "no".

• Optimal Stochastic Planarization, Anastasios Sidiropoulos, arXiv:1004.1666. If G is a graph of bounded genus g, then it's possible to randomly choose how to cut and unfold the surface on which G is embedded into a planar surface, in polynomial time, in such a way that the distortion of the distances of G caused by the cutting and unfolding operations is only logarithmic in g. The result can be used to extend approximation algorithms from planar graphs to bounded-genus graphs with only a logarithmic dependence on g in the approximation ratio.

• MapReduce Parallel Cuckoo Hashing and Oblivious RAM Simulations, Michael T. Goodrich and Michael Mitzenmacher, arXiv:1007.1259. Uses the cuckoo hashing data structure to provide optimal simulations of the PRAM model in the MapReduce framework, allowing a lot of past research on parallel algorithms to be ported to cloud computing.

• Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal, Daniel Lokshtanov, Dániel Marx, Saket Saurabh, arXiv:1007.5450. This paper shows tight connections between the strong exponential time hypothesis in exact exponential-time algorithms to fixed-parameter-tractable algorithms on graphs of bounded treewidth, implying that improvements to the treewidth-based algorithms are unlikely without reparameterization or simultaneous improvements to more basic problems like SAT.

• Determinant Sums for Undirected Hamiltonicity, Andreas Björklund, arXiv:1008.0541. Many problems of searching through the permutations of a set of items (such as the Hamiltonian cycle problem of permuting the vertices of a graph so that each pair that is adjacent in the cyclic permutation is also adjacent in the input graph) can be solved by a dynamic programming algorithm that is sufficiently well known to be the subject of an xkcd cartoon. But since Bellman, Held, and Karp found this in the early 1960s, no better time was known, even for the Hamiltonian cycle problem although the exponential space of the dynamic programming algorithm had been reduced to polynomial by several authors using inclusion-exclusion on numbers of walks. By counting numbers of weighted cycle covers mod 2 instead, and applying algebraic methods involving the Schwartz–Zippel lemma to solve this cycle cover counting problem, Björklund significantly reduces the time complexity of the Hamiltonian cycle problem, to \( O(1.657^n) \).

• Finding Topological Subgraphs is Fixed-Parameter Tractable, Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan, arXiv:1011.1827. Kuratowski's theorem states that a graph is planar if and only if it does not have a subgraph isomorphic to a subdivision of \( K_5 \) or \( K_{3,3} \). So how does one solve this "subgraph isomorphic to a subdivision of H" problem? For the specific cases of \( K_5 \) or \( K_{3,3} \) it was known, but this paper solves the more general problem of finding a topological \( H \)-minor, in polynomial time for any fixed \( H \). The result is closely analogous to but not the same as the problem of finding a minor (subgraph isomorphic to a vertex-expansion of \( H \)).

• The Power of Simple Tabulation Hashing, Mihai Pătraşcu and Mikkel Thorup, arXiv:1011.5200. A very simple multiplication-free hash function, looking up and xoring together random numbers from a table indexed by the bytes of the hash keys, performs well for many hashing algorithms despite its low degree of independence. (Previously.)

• Computing the Diameter Polynomially Faster than APSP, Raphael Yuster, arXiv:1011.6181. Fast matrix multiplication techniques can be used to find the farthest pair of points in an unweighted digraph, more quickly than known fast matrix multiplication techniques for finding all pairwise distances. Possibly this means that diameter is easier than all pairs shortest paths, or possibly it means that the all pairs problem can also be sped up in the same way; either one would be interesting. (Previously.)

• The Least Spanning Area of a Knot and the Optimal Bounding Chain Problem, Nathan M. Dunfield and Anil N. Hirani, arXiv:1012.3030. Every simple closed curve in 3d is the boundary of a two-dimensional Seifert surface; the curve is unknotted if and only if this surface can be chosen to be topologically a disk, and it's an important open question whether unknottedness (ore more generally the minimum genus of a Seifert surface) can be determined in polynomial time. In this paper it's shown that a different optimal-Seifert-surface problem does have a polynomial solution: given a piecewise-linear closed curve in 3d, it's possible to find in polynomial time the Seifert surface of minimum area. The authors are hopeful that similar techniques will also lead to a polynomial time solution of the minimum genus problem.

Comments: