EUVIMEDEUVIMED entdecken
Crossref

The SD–KE decomposition through the Larson matching interface

Kevin Pereyra

Journal of Combinatorial Mathematics and Combinatorial Computing · 22.07.2026 · 131 · 273-300

DOI: 10.61091/jcmcc131-14 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Combinatorial Mathematics and Combinatorial Computing, online erschienen am 22.07.2026. Verfasst von Kevin Pereyra.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We relate two decompositions that isolate König–Egerváry structure: the SD–KE decomposition, defined by the classical Edmonds–Sterboul–Deming obstructions, and Larson’s critical independence decomposition, whose complement is \(2\)-bicritical. Let \(I\) be a maximum critical independent set, set \(L(G)=I\cup N_G(I)\), \(L^c(G)=V(G)\setminus L(G)\), and \(B=N_G(I)\). We first prove a normal form for maximum matchings: each maximum matching is obtained from a maximum matching of \(G[L^c(G)]\), a matching crossing from a subset \(X\subseteq B\) into exposed vertices on the \(L^c(G)\) side, and a maximum matching of \(G[L(G)-X]\). The possible sets \(X\) are the crossing profiles. For a crossing profile \(X\) and a maximum matching \(P\) of \(G[L(G)-X]\), view \(P\) as a matching of \(G[L(G)]\). Let \(\Lambda_I(G)\) be the union of the vertices on \(P\)-augmenting paths in \(G[L(G)]\), over all crossing profiles and all residual maximum matchings. We prove \(SD(G)=L^c(G)\cup\Lambda_I(G),\) and \(KE(G)=L(G)\setminus\Lambda_I(G).\) Thus the SD vertices on the Larson König–Egerváry side are precisely those reached by augmenting corridors forced by admissible crossings.

Zitieren

APA

Pereyra, K. (2026). The SD–KE decomposition through the Larson matching interface. Journal of Combinatorial Mathematics and Combinatorial Computing, 131, 273-300. https://doi.org/10.61091/jcmcc131-14

Vancouver

Pereyra K. The SD–KE decomposition through the Larson matching interface. Journal of Combinatorial Mathematics and Combinatorial Computing. 2026;131:273-300. doi:10.61091/jcmcc131-14

BibTeX
@article{Pereyra2026,
  author = {Pereyra, Kevin},
  title = {The SD–KE decomposition through the Larson matching interface},
  journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
  year = {2026},
  volume = {131},
  pages = {273--300},
  doi = {10.61091/jcmcc131-14}
}
Kostenlos starten →