An explicit randomized algorithm with certified competitive ratio giving an explicit randomized algorithm for edge-weighted oblivious bipartite matching and observing that the finite-grid unweighted relaxation of the factor-revealing program coincides exactly with a Mahdian--Yan program.
Abstract
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.
We study the online preemptive matching problem, in which the edges of a graph arrive sequentially and the algorithm must maintain a matching by accepting or rejecting arriving edges and possibly discarding previously accepted ones. We prove a new upper bound of $0.5661$ on the competitive ratio achievable for the problem. This bound applies to arbitrary randomized algorithms, bipartite graphs and if we allow the algorithm to output a fractional solution. Our result improves upon the strongest previously known upper bound of $2-\sqrt{2} \approx 0.585$, due to Huang et al. [SODA'19]. Previous hardness constructions relied on edge sequences described by vertex arrivals where each arriving vertex reveals its edges to yet unvaried vertices. Under such sequences, Huang et al. showed that there exists a non-preemptive online algorithm with competitive ratio $\sim0.567$ (or $2-\sqrt{2}$ for fractional solutions). Consequently, our hardness construction is the first result which shows hardness for instances where the optimal algorithm employs preemption.
Peter Kiss, Mohammad Sharifi· International Colloquium on...· 1 citation
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.
Rong Fu, Yongtai Liu, Xiaowen Ma et al.· 0 citations
An ordered Ruzsa-Szemeredi graph is a graph whose edge set is partitioned into equal-size matchings, each induced in the suffix of the ordering that begins with it. Behnezhad and Ghafari introduced them to parametrize the update time of fully dynamic matching, but almost nothing is known about the numbers themselves. Writing f(n) for the largest number of parts when the matchings have size two, we determine f(n) exactly for every order from five to nineteen, narrow order twenty to two consecutive values, and give an explicit asymptotic construction. The engine is a bijection between ordered decompositions and K_4-peelings of the complete graph, each step deleting a perfect matching from four vertices that currently span a clique. This yields the counting bound floor(n(n-4)/4) at once and reduces equality to whether a cubic or near-cubic remainder is reachable. Structural lemmas cut the candidates to connected bridgeless graphs, and a contraction correspondence carries odd orders to the even census one larger, leaving a finite case analysis that we discharge by isomorphism-free reverse search. The bound is attained only at orders five through nine and eleven, and missed by exactly one at every other order we reach. Order eleven is thus an isolated exception rather than a parity phenomenon: the natural equality conjecture fails, and fails irregularly. Upper bounds are certified by fail-closed sweeps over complete cubic censuses, and every decomposition is re-checked against the definition by an independent verifier. Which of its two values order twenty takes remains open.
We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new $\widetilde{O}(n^{3/2})$-bit protocol for computing a maximum matching in general graphs. While the same upper bound can be obtained by simulating the classic algorithms of Micali-Vazirani and Gabow, our protocol is conceptually simple and avoids the intricacies of finding a maximal set of shortest augmenting paths; (2) a new $\widetilde{O}(n)$-bit protocol for negative-cycle detection and negative-weight single-source shortest paths. Our protocol simplifies that of Blikstad et al. by replacing a long chain of reductions with a more direct approach based on vertex potentials; (3) a combinatorial $\widetilde{O}(n)$-bit protocol for computing a maximum matching in bipartite graphs, obtained by reinterpreting the near-linear communication protocol of Blikstad et al. through a discretized analysis. Together, these results provide simpler protocols for several basic graph problems. We hope they will inspire further advances on the communication complexity of a wide range of graph problems.
Yu Cheng, Tianle Jiang, Pachara Sawettamalya et al.· 0 citations
We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number $k$. For ISI, we give a randomized $O^*(k^{O(k)})$-time algorithm, showing that ISI is fixed-parameter tractable under this parameter and resolving an open question of Hanaka et al. [WALCOM 2026]. Our algorithm is optimal under the Exponential Time Hypothesis (ETH), and is based on a reduction to Exact Multicolored Matching solvable via algebraic techniques. For MCIS, we present a randomized $O^*(2^{O(k^2)})$-time algorithm via a reduction to a weighted variant of Exact Multicolored Matching, and we prove a matching ETH-based lower bound by showing that a $k$-by-$k$ binary matrix feasibility problem with list-constrained rows and columns admits no $O^*(2^{o(k^2)})$-time algorithm, which may be of independent interest. These results reveal that, in this setting, MCIS is strictly harder than ISI. Finally, for the three-graph variant 3-MCIS, we show that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.
This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a limited time. The algorithm must make irrevocable fractional matching decisions while the relevant vertices are simultaneously available. We extend the classic Water-Filling algorithm, also known as Balance and originally introduced by Kalyanasundaram and Pruhs (TCS 2000), to the fully online setting. Using an online primal-dual framework, we prove that the generalized Water-Filling algorithm achieves a competitive ratio of $2-\sqrt{2}\approx 0.586$ in the fully online model, and that this analysis is tight. To surpass the $2-\sqrt{2}$ barrier, we incorporate the ideas of eager matching and history-based pricing into Water-Filling. We show that the resulting algorithm achieves an improved competitive ratio of $0.599$, thereby establishing that Water-Filling is not optimal in the fully online setting. On the hardness side, we further improve the known upper bound for fractional fully online matching, reducing the previous best bound of $0.6297$ due to Eckl et al. (ORL 2021) to $0.6132$.
Zhiyi Huang, Z. Tang, Xiaowei Wu et al.· 0 citations