An Edmonds-Gallai-Type Decomposition for the $j$-Restricted $k$-Matching Problem

Yanjun Li, Jácint Szabó

Published in:
The Electronic Journal of Combinatorics, Volume 27, Issue 1, 2020. DOI link


Given a non-negative integer $j$ and a positive integer $k$, a $j$-restricted $k$-matching in a simple undirected graph is a $k$-matching, so that each of its connected components has at least $j+1$ edges. The maximum non-negative node weighted $j$-restricted $k$-matching problem was recently studied by Li who gave a polynomial-time algorithm and a min-max theorem for $0 \leq j < k$, and also proved the NP-hardness of the problem with unit node weights and $2 \leq k \leq j$. In this paper we derive an Edmonds-Gallai-type decomposition theorem for the $j$-restricted $k$-matching problem with $0 \leq j < k$, using the analogous decomposition for $k$-piece packings given by Janata, Loebl and Szabó, and give an alternative proof to the min-max theorem of Li.

Bibtex entry:

AUTHOR = {Li, Yanjun and Szab{\'o}, J{\'a}cint},
TITLE = {An Edmonds-Gallai-Type Decomposition for the $j$-Restricted $k$-Matching Problem},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-05}

Last modification: 22.11.2022. Please email your comments to Tamás Király!