CS Paper Radar

Strong aggregation of the Markov chains associated with matching models based on the automorphism group of their compatibility graphs

Moyi Yang, Jean-Michel Fourneau

cs.PF ·submitted 2026-09-15 08:54 UTC · v1
theory

Abstract

We extend the analysis of strong aggregation to general compatibility graphs, focusing on item counts rather than positions, and exploring generalized greedy matching disciplines. We prove that under a condition of automorphism-based transition consistency, the associated Markov chain is strongly aggregable for an arbitrary graph with a non-trivial automorphism group. Furthermore, we extend our analysis to non-greedy matching disciplines, distinguishing scenarios where compatible items can or cannot coexist within the same state. This result is illustrated with a simple compatibility graph with a rich automorphism structure: the odd rings. For all scenarios, we investigate the strong aggregation properties of the resulting Markov chains. This work enhances the theoretical understanding of lumpability in stochastic matching models and provides a foundation for analyzing complex graph structures.

Closest papers

Nearest neighbours by meaning across the whole index.

Perturbation equivalence in labelled Markov chains

cs.LO cs.FL ·2026-09-11 ·Syyeda Zainab Fatmi, Stefan Kiefer, James C. A. Main, David Parker
theory similarity 0.59
Abstract

Behavioural equivalences, such as language equivalence and probabilistic bisimilarity, are fundamental techniques for reducing the size of probabilistic models. However, these equivalences are sensitive to the precise values of transition probabilities, making them unsuitable in applications where probabilities are subject to approximation. Motivated by settings in which the support graph of a labelled Markov chain is known but the transition probabilities are uncertain, we study robust variants of these equivalences. We introduce universal (perturbation) equivalence, which captures a variant of equivalence that is resilient to all perturbations of transition probabilities: two states or distributions are universally equivalent if they remain equivalent under every assignment of transition probabilities consistent with the support graph. We also consider the dual notion of existential (perturbation) equivalence, which holds whenever there exists an assignment of transition probabilities that yields equivalence. We establish that, for states, universal language equivalence coincides with universal probabilistic bisimilarity and develop a characterisation that yields a polynomial-time partition refinement algorithm. We implement the algorithm and demonstrate experimentally that it is effective as a technique for robust model reduction. We further show that universal language equivalence for distributions is closely related to the state case, and prove NL-completeness of deciding universal equivalence for both states and distributions. We prove that, for states, existential language equivalence coincides with existential probabilistic bisimilarity and deterministic witness transition functions always suffice, leading to an NP-completeness result. In contrast, we show that existential language equivalence for distributions is complete for the existential theory of the reals.

0.32

Stability in stochastic hypergraph matching III: general reneging

cs.DM math.PR ·2026-09-14 ·Doan Dai Nguyen, Ana Bušić
similarity 0.53
Abstract · 43 pages

In many real-life matching problems, waiting agents might abandon before being matched, such as patients deceasing before receiving organs, passengers/drivers cancelling ride requests, or raw materials/intermediary products degrading in production lines. This poses the need for incorporating reneging in stochastic matching models. In this work, we consider matching models on hypergraphs with batch arrivals and general-weight matchings. Since our model allows fractional weights, we may not be able to talk about individual items, and thus reneging is not required to be independent between items of the same class. For the simplicity sake's, we assume items arrive at discrete time. We show that stability depends on the exact nature of reneging, in stark contrast with the non-reneging case where it depends on the arrivals only through the arrival rates. To our best knowledge, this is the first such sensitivity result in stochastic matching. We uncover a new stabilising mechanism which exists neither in the non-reneging case nor in the graph case, which explains why incorporating reneging in stochastic matching is not straightforward. Together with balancing mechanism as hinted in the online assignment framework for the non-reneging case, it gives a criterion necessary and sufficient for stability. Finally, whilst verifying stability is a hard problem, we give a family of MaxWeight-type policies parameterised by $\varepsilon > 0$, which are maximally stabilising for all $\varepsilon$ sufficiently small. Unfortunately there is no effective bound for $\varepsilon$, but we show how to adjust its value during implementation.

0.42

A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists

cs.DS ·2026-10-29 ·Shuichi Miyazaki, Suguru Tamaki
similarity 0.52
Abstract · 13 pages

We study Stable Marriage with Ties and Incomplete lists (SMTI) under weak stability. For an instance with $n$ agents on each side, we give an exact algorithm that returns a maximum-cardinality weakly stable matching in $O^*(22.74^n)$ time. To the best of our knowledge, this is the first exact algorithm for this problem running in single-exponential time.

0.53

A simplified proof of the FPRAS for counting perfect matchings

cs.DS math.CO ·2026-10-19 ·Chenghua Liu, Boning Meng
similarity 0.51
Abstract

We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.

0.26

Degree Stability of Parallel Greedy Matching in Random Graphs

cs.DM cs.DSmath.PR ·2026-10-18 ·Vishvajeet N, Shrinidhi Teganahally Sridhara
hot direction similarity 0.51
Abstract · 49 pages

We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for $Θ(\log^{1+ε} n)$ rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of $\mathbb{G}(n,p)$ yields $O(1)$ variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for $Ω(\log^{1+ε} n)$ rounds.

0.27

Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

cs.DS ·2026-09-22 ·Sara Ahmadian, Edith Cohen, Mohammad Roghani
benchmark similarity 0.51
Abstract

Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.

0.08

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.50
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

0.26

A Structural Framework for Succession: Continuation, Recognition, and Realization

cs.AI ·2026-11-16 ·Ilya A. Shkrob
similarity 0.50
Abstract · 45 pages with tables and diagrams

Succession asks whether an entity encountered later is the same entity that entered an arrangement earlier. For an artificial system that is fine-tuned, distilled, or copied, it has to be answered. We look for a mathematical structure weak enough to cover any such case and strong enough to support general theorems, so that results follow from the structure's conditions rather than from a particular pipeline or criterion. Succession is modeled on state/modification graphs with relational lifts that compose along paths. Within this framework we separate four questions that are often conflated: which continuations a representation admits, which descendants are compatible with a modification, which are recognized as continuing the identity, and which are realized. The framework allows one to address systematically questions of symmetry, computational complexity, recoverability, and robustness to partial realization, and we establish what the structure settles in each case before any particular criterion of identity is chosen.

0.29