On Distance-3 Matchings and Induced Matchings

For a finite undirected graph

G

 = (

V

,

E

) and positive integer

k

 ≥ 1, an edge set

M

 ⊆ 

E

is a

distance-k

matching

if the mutual distance of edges in

M

is at least

k

in

G

. For

k

 = 1, this gives the usual notion of matching in graphs, and for general

k

 ≥ 1, distance-

k

matchings were called

k-separated matchings

by Stockmeyer and Vazirani. The special case

k

 = 2 has been studied under the names

induced matching

(i.e., a matching which forms an induced subgraph in

G

) by Cameron and

strong matching

by Golumbic and Laskar in various papers.

Finding a maximum induced matching is

$\mathbb{NP}$

-complete even on very restricted bipartite graphs but for

k

 = 2, it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in

G

corresponds to an independent vertex set in the square

L

(

G

)

2

of the line graph

L

(

G

) of

G

which, by a result of Cameron, is chordal for any chordal graph

G

.

We show that, unlike for

k

 = 2, for a chordal graph

G

,

L

(

G

)

3

is not necessarily chordal, and finding a maximum distance-3 matching remains

$\mathbb{NP}$

-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-3 matching problem can be solved in polynomial time. Moreover, we obtain various new results for induced matchings.