Repair Complexity in Fully Dynamic Maximal Matching: Discovery–Propagation Tradeoffs, Conditional Hardness, and Reproducible Real-Data Evidence

Abstract

Fully dynamic maximal matching is conventionally analyzed through update time, yet the loss of a matched edge exposes a more fundamental question: what information must be preserved, propagated, or rediscovered before maximality can be restored? We develop a repair-centered framework for studying this information requirement. In an exact explicit-summary model, we prove the per-epoch tradeoff P + D ≥ r, where r denotes potentially changed neighbor states, P those communicated to query-visible state, and D those that must be resolved through discovery. We then reduce Pătraşcu’s Multiphase problem to one-shot triggered maximal-matching repair, obtaining a conditional polynomial barrier on preprocessing, candidate-update, or trigger-repair cost within the stated output-stable model. To characterize repeated repair, we derive the exact future-burden decomposition Q = k[AG + Cov(a,g)], separating recurrence, scan intensity, degree evolution, and their interaction. We evaluate these results using differential instrumentation, exhaustive gadget audits, synthetic stress experiments, and three real temporal graph traces. The empirical evidence reveals an important boundary: although neighborhood change is associated with discovery cost on AS-CAIDA, this relationship largely disappears after controlling for degree. Together, the theoretical and empirical results identify dynamic matching repair as an information-allocation problem and distinguish provable repair constraints from workload-dependent manifestations.