2009 | OriginalPaper | Chapter
On Distance-3 Matchings and Induced Matchings
Authors : Andreas Brandstädt, Raffaele Mosca
Published in: Graph Theory, Computational Intelligence and Thought
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.