Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
<|reference_start|>Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity: Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither constructive nor algorithmic, Biedl, Bose, Demaine, and Lubiw [J. Algorithms 38(1)] showed how to implement a later constructive proof by Frink in $\mathcal{O}(n\log^{4}n)$ time using a fully dynamic 2-edge-connectivity structure. Then, Diks and Sta\'nczyk [SOFSEM 2010] described a faster approach that only needs a fully dynamic connectivity structure and works in $\mathcal{O}(n\log^{2}n)$ time. Both algorithms, while reasonable simple, utilize non-trivial (2-edge-)connectivity structures. We show that this is not necessary, and in fact a structure for maintaining a dynamic tree, e.g. link-cut trees, suffices to obtain a simple $\mathcal{O}(n\log n)$ time algorithm.<|reference_end|>
@article{gawrychowski2024finding,
    title={Finding perfect matchings in bridgeless cubic multigraphs without
  dynamic (2-)connectivity},
    author={Pawe{l} Gawrychowski and Mateusz Wasylkiewicz},
    journal={arXiv preprint arXiv:2405.03856},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.03856},
    primaryClass={cs.DS cs.DM}
}