Linear time algorithm for maximum distance-k matching in interval graphs

Give a finite undirected graph $G = (V, E)$ and a positive integer $k \geq 1$, a distance-k matching is an edge set $D\subset E$ that the pairwise distance of edges in D is at least k in G. The famous matching is distance −1 matching and induced matching is distance −2 matching. Finding a maximum induced matching is NP-hard even on special bipartite graphs. However, it can be done efficiently on various classes of graphs such as interval graphs and chordal graphs. Moreover, Maximum distance-3 matching is NP-hard on chordal graphs. Nevertheless, maximum distance-k matching can be found efficiently on strongly chordal graphs, interval graphs and circular-arc graphs. In this paper, we first prove that if G is an interval graph, the k-th of its line graph, $L(G)^{k}$, is also an interval graph. Finally, we present a linear algorithm for maximum distance-k matching on interval graphs.