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:
@techreport{egres-18-05,
AUTHOR | = | {Li, Yanjun and Szab{\'o}, J{\'a}cint}, |
TITLE | = | {An Edmonds-Gallai-Type Decomposition for the $j$-Restricted $k$-Matching Problem}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2018}, |
NUMBER | = | {TR-2018-05} |