22 października 2024 11:15
[Seminarium ZOK] Mateusz Wasylkiewicz: Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
Abstract: Petersen's theorem, one of the earliest results in graph
theory, states that every 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
O(n*log^4(n)) time using a fully dynamic 2-edge-connectivity structure.
Then, Diks and Stańczyk [SOFSEM 2010] described a faster approach that
only needs a fully dynamic connectivity structure and works in
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 O(n*log(n)) time algorithm.
Joint work with Paweł Gawrychowski. The paper was published at track S
of the European Symposium on Algorithms 2024.