DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.59

Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity

Authors: Paweł Gawrychowski and Mateusz Wasylkiewicz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

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 𝒪(nlog⁴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 𝒪(nlog²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 𝒪(nlog n) time algorithm.

Cite as

Paweł Gawrychowski and Mateusz Wasylkiewicz. Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ESA.2024.59,
  author =	{Gawrychowski, Pawe{\l} and Wasylkiewicz, Mateusz},
  title =	{{Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{59:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.59},
  URN =		{urn:nbn:de:0030-drops-211301},
  doi =		{10.4230/LIPIcs.ESA.2024.59},
  annote =	{Keywords: perfect matching, cubic graphs, bridgeless graphs, link-cut tree}
}

Document

DOI: 10.4230/LIPIcs.ESA.2021.73

Restricted t-Matchings via Half-Edges

Authors: Katarzyna Paluch and Mateusz Wasylkiewicz

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract

For a bipartite graph G we consider the problem of finding a maximum size/weight square-free 2-matching and its generalization - the problem of finding a maximum size/weight K_{t,t}-free t-matching, where t is an integer greater than two and K_{t,t} denotes a bipartite clique with t vertices on each of the two sides. Since the weighted versions of these problems are NP-hard in general, we assume that the weights are vertex-induced on any subgraph isomorphic to K_{t,t}. We present simple combinatorial algorithms for these problems. Our algorithms are significantly simpler and faster than those previously known. We dispense with the need to shrink squares and, more generally subgraphs isomorphic to K_{t,t}, the operation which occurred in all previous algorithms for such t-matchings and instead use so-called half-edges. A half-edge of edge e is, informally speaking, a half of e containing exactly one of its endpoints. Additionally, we consider another problem concerning restricted matchings. Given a (not necessarily bipartite) graph G = (V,E), a set of k subsets of edges E₁, E₂, …, E_k and k natural numbers r₁, r₂, …, r_k, the Restricted Matching Problem asks to find a maximum size matching of G among such ones that for each 1 ≤ i ≤ k, M contains at most r_i edges of E_i. This problem is NP-hard even when G is bipartite. We show that it is solvable in polynomial time if (i) for each i the graph G contains a clique or a bipartite clique on all endpoints of E_i; in the case of a bipartite clique it is required to contain E_i and (ii) the sets E₁, …, E_k are almost vertex-disjoint - the endpoints of any two different sets have at most one vertex in common.

Cite as

Katarzyna Paluch and Mateusz Wasylkiewicz. Restricted t-Matchings via Half-Edges. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 73:1-73:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{paluch_et_al:LIPIcs.ESA.2021.73,
  author =	{Paluch, Katarzyna and Wasylkiewicz, Mateusz},
  title =	{{Restricted t-Matchings via Half-Edges}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{73:1--73:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.73},
  URN =		{urn:nbn:de:0030-drops-146541},
  doi =		{10.4230/LIPIcs.ESA.2021.73},
  annote =	{Keywords: restricted 2-matchings}
}

Search Results

Documents authored by Wasylkiewicz, Mateusz

Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity

Abstract

Cite as

Restricted t-Matchings via Half-Edges

Abstract

Cite as

Thanks for your feedback!

Could not send message