TR-2018-05

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



Abstract

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}
}


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