P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework and complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.
Abstract
We study degeneracy guided list compression for greedy graph coloring when graph structure is available before colors are sampled. Our exposure calibrated ordering framework assigns each vertex an independent uniform list according to its backward neighborhood in a color independent order. Its certified instantiation, Profiled Structure Aware Asymmetric Palette Sparsification, or P-SAPST, reverses a minimum degree removal sequence and obtains every backward exposure from the removal profile. For each fixed profile, we characterize the exact local budget required by independent uniform lists under history robust greedy recovery. The profile yields linear list volume on high degree forests and on a core fringe family where reciprocal rank allocation requires Theta(n log^2 n) sampled colors. Exact conflict expectation, concentration, and a dense exposure barrier complete the theoretical description. The evaluation contains 40,320 runs over SAPBench and two SNAP networks. At the theorem scale, P-SAPST reduces mean list size by 47.6 percent relative to calibrated APST while attaining 99.8 percent observed greedy success. P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework. On stress graphs with 250,000 vertices and up to 1,251,868 edges, Lite obtains a payload ratio of 0.865, while calibrated APST obtains 7.886. On email Enron, the corresponding ratios are 0.193 and 5.814. Compression is strongest on hub dominated and power law graphs and disappears near the dense exposure barrier. The method complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.
Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper, we propose a novel"Certify-then-Rectify"framework that bridges the gap between the speed of heuristic search and the rigor of exact retrieval. Rather than discarding HNSW, our approach first employs a distribution-free statistical certifier to dynamically evaluate the quality of a standard HNSW search with minimal overhead. If certification indicates that the retrieved neighbors are of low quality, the framework safely escalates to a rigorous exact recovery algorithm. To make this exact recovery computationally feasible, we reinterpret the HNSW graph as a geometric spanner and utilize Extreme Value Theory to stochastically estimate its maximum empirical stretch factor. This allows us to mathematically bound the maximum distance of true nearest neighbors. Extensive evaluations on benchmark datasets demonstrate that our tiered framework delivers the average-case speed of HNSW while ensuring the worst-case correctness of exact search and outperforming other applicable approaches.
Minghao Li, Raghav Mittal, Sanjivni Rana et al.· 0 citations
Symmetric Numerical Three-Dimensional Matching (SN3DM) asks whether three disjoint labeled classes with identical weight multisets can be partitioned into class-transversal triples of one common target sum. Its theme is role recovery under marginal symmetry: identical numerical catalogues force the asymmetric source roles to be reconstructed from incidence structure alone. This tutorial develops three complementary hardness results for that symmetry restriction. Part I gives a unary-polynomial reduction from N3DM. Source roles become ports in one common occurrence set, a uniquely forced filler system reserves one main incidence per port, bipartite edge coloring restores the output-class labels, and a no-carry mixed-radix encoding packs four coordinates into positive integers. Hence SN3DM is strongly NP-complete. Part II studies Max-SN3DM, for which strong NP-hardness alone does not exclude a PTAS. Two numerical compilers lift Petrank's perfect-completeness gap for bounded 3DM to unary Max-N3DM, and a defect-stability lemma shows that a symmetric matching of size 13n - d yields a source matching of size at least n - 21d, where n is the multiset cardinality, and d is a symmetric defect. Hence, for some epsilon>0, it is NP-hard to separate perfect instances from those of optimum at most (1- epsilon) times perfect, so no PTAS exists unless P = NP. Every maximal legal triple matching is a 3-approximation, placing the problem in APX. Part III supplies the approximation-preserving reduction Part II does not claim. An exact pair compiler and a one-live-port separation map degree-three Maximum 3DM to unary Max-SN3DM with OPT(Max-SN3DM) = Gamma + OPT(Max-3DM) for a fixed offset Gamma and one-for-one optimum-error transfer. The L-reduction has constants alpha = 764 and beta = 1, so Max-SN3DM is APX-complete. The two are incomparable; worked yes / no instances audit each construction.
We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe between two free vertices must be accepted immediately. We give an explicit randomized algorithm with certified competitive ratio $0.698$, improving the previous best guarantee of $0.659$ (Huang, Sun, Wu, and Zhao, FOCS 2025). The result is computer-assisted and verified by a reproducible exact-integer computation. The same algorithm has a $0.698$-competitive online implementation for the vertex-weighted random-arrival model, improving the previous $0.696$ unweighted guarantee of Mahdian and Yan (STOC 2011) and the $0.686$ vertex-weighted guarantee of Peng and Tang (EC 2025). Our algorithm, Harmonic Ranking, is a role-symmetric generalization of \textsc{Ranking}. It assigns an independent random rank $x_z$ to each vertex and probes a potential edge $uv$ in decreasing order of \[ w_{uv}\frac{h(x_u)h(x_v)}{h(x_u)+h(x_v)}. \] This harmonic priority arises from a budget-balanced gain split and a mutual-proposal interpretation. The analysis lifts two cutoff curves into indicators, reducing the exponential-size factor-revealing problem to a polynomial-size directed minimum-cut instance. A maximum-flow computation with rounded-down integer capacities gives a rigorous certificate. Independently, we observe that the finite-grid unweighted relaxation of our factor-revealing program coincides exactly with a Mahdian--Yan program.
In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting position, while the graph is revealed only locally at visited vertices. Although the problem has attracted considerable attention, previous work has focused exclusively on deterministic algorithms. Randomized strategies are often substantially harder to analyze because of a fundamental challenge inherent to exploration. In this work, we give the first positive result showing that randomization can improve competitive guarantees in online graph exploration. To this end, we focus on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration. Our main contribution is \(\textsc{RandHeavyTest}\), a randomized algorithm for online exploration of cycles whose competitive ratio we prove to be at most 1.315. This establishes a strict separation from the deterministic setting, where the optimal competitive ratio is $\thickapprox 1.366$, and thus gives the first provable advantage of randomization in online graph exploration. A key step towards this result is a new, simplified optimal deterministic algorithm, \(\textsc{HeavyTest}\), whose formulation naturally suggests the randomized variant. We complement our upper bounds with lower bounds of 1.115 for arbitrary randomized algorithms and 1.207 for the natural class of so-called forward-greedy algorithms, which includes \(\textsc{RandHeavyTest}\).
Júlia Baligács, Jan Hkazla, Lena Volk· 0 citations
We show that every weighted hypergraph on $n$ vertices admits a spectral $\varepsilon$-sparsifier with $O(n\log n/\varepsilon^2)$ hyperedges, strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.
List-coloring, introduced independently by Vizing and by Erd\H{o}s, Rubin, and Taylor in the 1970s, generalizes ordinary vertex coloring by assigning to each vertex its own set of admissible colors. A graph is chromatic-choosable if its list chromatic number equals its chromatic number. The previous survey on list-coloring by D R Woodall (2001), emphasized defective choosability, the list-coloring conjectures, and different methods used for list-coloring. This survey reviews major developments on list-coloring and chromatic-choosability, with emphasis on graph classes for which equality is known, graph classes exhibiting a nontrivial gap, and the principal methods used to prove such results. The survey covers embedded graphs, perfect graphs, complete bipartite and multipartite graphs, claw-free graphs, line graphs, powers of graphs, graph products, and selected variants of list-coloring.
Nandana K Vasudevan, K. Somasundaram, N. Narayanan· 0 citations