On distance-3 matchings and induced matchings
For a finite undirected graph G=(V,E) G = ( V , E ) and positive integer k?1 k ? 1 , an edge set M?E M ? E is a distance-k matching  if the pairwise distance of edges in M M is at least k k in G G . For k=1 k = 1 , this gives the usual notion of matching in graphs, and for general k?1 k ? 1 , distance-k k matchings were called k-separated matchings  by Stockmeyer and Vazirani. The special case k=2 k = 2 has been studied under the names induced matching  (i.e., a matching which forms an induced subgraph in G G ) by Cameron and strong matching by Golumbic and Laskar in various papers. Finding a maximum induced matching is NP N P -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 G G corresponds to an independent vertex set in the square L(G)2 L ( G ) 2 of the line graph L(G) L ( G ) of G G which, by a result of Cameron, is chordal for any chordal graph G G . We show that, unlike for k=2 k = 2 , for a chordal graph G G , L(G)3 L ( G ) 3 is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) ( 2 k + 1 ) matching for k?1 k ? 1 , remains NP N P -complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k k matching problem can be solved in polynomial time for every k?1 k ? 1 . Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.
chordal graphs strongly chordal graphs distance-k k matching k k k k k maximum distance-k k matching problem k k k k k maximum induced matching problem