On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E)G=(V,E) and positive integer k≥1k≥1, an edge set M⊆EM⊆E is a distance-k matching   if the pairwise distance of edges in MM is at least kk in GG. For k=1k=1, this gives the usual notion of matching in graphs, and for general k≥1k≥1, distance-kk matchings were called k-separated matchings   by Stockmeyer and Vazirani. The special case k=2k=2 has been studied under the names induced matching   (i.e., a matching which forms an induced subgraph in GG) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NPNP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in GG corresponds to an independent vertex set in the square L(G)2L(G)2 of the line graph L(G)L(G) of GG which, by a result of Cameron, is chordal for any chordal graph GG.We show that, unlike for k=2k=2, for a chordal graph GG, L(G)3L(G)3 is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1)(2k+1) matching for k≥1k≥1, remains NPNP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-kk matching problem can be solved in polynomial time for every k≥1k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.