On Minimum Maximal Distance-k Matchings

Abstract

We study the computational complexity of several problems connected with the problems of finding a maximal distance-k matching of minimum cardinality or minimum weight. We introduce the class of k-equimatchable graphs which is an edge analogue of k-equipackable graphs. We prove that the recognition of k-equimatchable graphs is co-NP-complete for any fixed k≥2. We also prove that the problem of finding a minimum weight maximal distance-2l matching in chordal graphs is hard to approximate within a factor of εln|V(G)| for a fixed ε unless P=NP. Finally, we show NP-hardness of the minimum maximal induced matching problem in several restricted graph classes.