Computational complexity of maximum distance-(k, l) matchings in graphs

Abstract

In this paper, we introduce the concept of a distance-(k, l) matching of a graph, which is a subset of edges of this graph such that the number of intermediate edges in the shortest path between any two edges of this set lies between k and l. We prove that the problem MAXIMUM DISTANCE-(k, l) MATCHING, which asks whether a graph contains a distance-(k, l) matching of size exceeding a given number, is NP-complete for arbitrary given or variable k and l, and that the weighted variant of this problem is strongly NP-complete even for bipartite graphs. We also present several upper bounds on the size of a maximum distance-(k, l) matching.