The SD–KE decomposition through the Larson matching interface
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.
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}
}
EUVIMED