More Like this

1. A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities

   https://doi.org/10.4230/LIPIcs.ISAAC.2021.72  

   Enoch, Julian; Fox, Kyle; Mesica, Dor; Mozes, Shay (November 2021, 32nd International Symposium on Algorithms and Computation)

   Ahn, Hee-Kap; Sadakane, Kunihiko (Ed.)

   We give an O(k³ Δ n log n min(k, log² n) log²(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of max(k²,k log² n) over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses O(k) invocations of an O(k³ n log³ n)-time algorithm for maximum flow algorithm in a planar graph with k apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the k-apex graphs that arise in our modification of Wang’s procedure faster than the algorithm of Borradaile et al. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan [JACM 1988]. 

   more » « less
2. A Structure Theorem for Pseudo-Segments and Its Applications

   https://doi.org/10.4230/LIPIcs.SoCG.2024.59  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   We prove a far-reaching strengthening of Szemerédi’s regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such graphs can be partitioned into a bounded number of parts of roughly the same size such that almost all of the bipartite graphs between pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every n-vertex simple topological graph with no k pairwise disjoint edges has at most n(log n)^O(log k) edges. 

   more » « less
3. Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝

   https://doi.org/10.1145/3564246.3585250  

   Sun, Xiaorui (June 2023, ACM)

   The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order $$n$$, an algorithm with $$n^{(\log n + O(1))}$$ running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an $$n^{(1 / 4 + o(1))\log n}$$ running time (Rosenbaum 2013). The isomorphism testing for $$p$$-groups of (nilpotent) class 2 and exponent $$p$$ has been identified as a major barrier to obtaining an $$n^{o(\log n)}$$ time algorithm for the group isomorphism problem. Although the $$p$$-groups of class 2 and exponent $$p$$ have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an $$n^{O(\log n)}$$ running time. In this paper, we present an isomorphism testing algorithm for $$p$$-groups of class 2 and exponent $$p$$ with running time $$n^{O((\log n)^{5/6})}$$ for any prime $p > 2$. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces. 

   more » « less
4. Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs

   https://doi.org/10.4230/LIPIcs.ICALP.2022.21  

   Bezakova, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Stefankovic, Daniel (January 2022, International Colloquium on Automata, Languages, and Programming (ICALP))

   Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L_p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS’13). The non-linearity of L_p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L_p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n, d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime. 

   more » « less
5. Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs

   Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel (June 2022, ICALP 2022)

   Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L^p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of L^p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L^p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n,d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime. 

   more » « less