-
A Lower Bound for Light Spanners in General Graphs by Greg Bodwin and Jeremy Flics. This paper resolved one of my favorite problems in a direction that is completely surprising to me: The optimal lightness bound of \((2k-1)(1+\epsilon)\)-spanner for general graph should have a dependency on \(\epsilon\). Before this paper came out, I believed that there should be no dependency on \(\epsilon\). This paper proves me wrong.
-
“Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more” by Adam Karczmarz and Da Wei Zheng. This paper seems to solve a problem Christian Wulff-Nilsen and I failed to solve in our SODA24 paper: designing a distance oracles for weighted minor-free digraphs with a subqudratic space.
-
“Bounding epsilon-scatter dimension via metric sparsity” by Romain Bourneuf and Marcin Pilipczuk. The notion of \(\epsilon\)-scatter dimension is a beautiful concept introduced just recently by Abbassi, Banerjee, Byrka, Chalermsook, Gadekar, Khodamoradi, Marx, Sharma, and Spoerhase in the context of clustering problem. The bound on \(\epsilon\)-scatter dimension they obtained is very large. I love to see improved bounds here.
-
“Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances” by Yu Chen and Zihan Tan. The Okamura-Seymour instance in undirected planar graphs has been extensively studied in metric embedding and is an inspiration for the notorious \(\ell_1\) embedding conjecture of planar graphs. This paper is about the Okamura-Seymour instance in directed graphs.
-
Parks and Recreation: Color Fault-Tolerant Spanners Made Local by Merav Parter, Asaf Petruschka, Shay Sapir, and Elad Tzailk. Previously, Petruschka, Sapir, and Tzalik introduced a very interesting notion of color fault-tolerant spanners: This kind of spanners could tolerate up to \(\Omega(n)\) failures. However, the construction is sequential and inefficient. The new SODA paper gives a different algorithm that is amenable to distributed implementation.
-
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths by Lily Wang and Greg Bodwin. Suppose that \(f\) edges of your graph fail, an \(f\)-fault replacement path is the shortest path between two endpoints \(u\) and \(v\) in the graph obtained by removing all the failed edges. Remarkably, Afek, Bremler-Barr, Kaplan, Cohen, and Merritt showed that you can partition the replacement path into \(f+1\) subpaths that are shortest in the input graph. This can be generalized: one can partition any \(f\)-fault replacement path into \(k+1\) subpaths where each is an \((f − k)\)-edge-failure replacement for any \(0 \leq k \leq f\). (The result by Afek et al. is when \(k = f\), and the case \(k = 0\) is trivial.) Is this additive relationship between \(f\) and \(k\) tight? Nope. The work by Lily Wang and Greg Bodwin obtains a surprising multiplicative trade-off: \(O(k)\) paths, each of which is an \(O(f/k)\)-edge-failure replacement.
-
“Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets” by Shimon Kogan and Merav Parter. I am curious about light hopsets in this paper. Light spanners have been studied extensively. This is the first time I have heard about light hopsets. Are they related?
-
“Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies” by Yaowei Long, Seth Pettie, and Thatchaphol Saranurak. Expander graphs and hierarchies have been very instrumental to recent algorithmic breakthroughs. This is another one, but not for faster computation; it is for constructing a labeling scheme.
-
“New Separations and Reductions for Directed Hopsets and Preservers” by Gary Hoppenworth, Yinzhan Xu, and Zixuan Xu.
-
“Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition” by Julia Chuzhoy and Merav Parter.
-
“A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs” by Chandra Chekuriand Rhea Jain. This paper follows up on the \(O(\log k)\)-approximation for directed Steiner tree in planar graphs by Friggstad and Mousavi. It is worth knowing that in undirected planar graphs, both problems admit a PTAS. The big question: is \(O(1)\)-approximation possible for the Directed Steiner Tree problem in planar graphs?
-
Weak coloring numbers of minor-closed graph classes by Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Weak coloring number is an important parameter to understand in planar and minor-free graphs. This paper gives a set of results related to this parameter for various minor-closed graph classes.
-
Planar graphs in blowups of fans by Vida Dujmovic, Gwenael Joret, Piotr Micek, Pat Morin, and David R. Wood. A \(b\)-blowup of a graph \(H\) is a graph \(G\) obtained by replacing each vertex with a clique of size \(b\) and replacing each edge with the complete bipartite graph between the vertices in the corresponding cliques of the two endpoints. This paper shows that any \(n\)-vertex planar graph is a subgraph of a \(O(\sqrt{n}\log^2n)\)-blowup of a fan. The picture looks something like this (taken from their paper):