DIMACS TR: 2004-26
Maximal induced matchings of minimum/maximum size
Authors: Yury L. Orlovich and Igor E. Zverovich
ABSTRACT
Let ${\rm IMatch}(G)$ be the set of all maximal induced matchings
of a graph $G$. We define $\sigma(G) = \min\{|M|: M \in {\rm
IMatch}(G)\}$ and $\Sigma(G) = \max\{|M|: M \in {\rm
IMatch}(G)\}$. Stockmeyer and Vazirani~\cite{StockmeyerV82} and
Cameron~\cite{Cameron89} independently proved that the decision
problem corresponding to the problem of computing $\Sigma(G)$ is
NP-complete. We improve this result. Then we show NP-completeness
for $\sigma(G)$. We prove that WEIGHTED INDUCED MATCHING Problem
can be solved in polynomial time for $(G_1, G_2, \ldots,
G_{17})$-free graphs, see Figure~\ref{sigma-figure3}. Also,
INDUCED MATCHING Problem can be solved in polynomial time for
$(H_1, H_2, \ldots, H_{30})$-free graphs, see
Figure~\ref{sigma-figure4}. The latter result extends results of
Kobler and Rotics~\cite{KoblerR03}, and Boliac and
Lozin~\cite{BoliacL01}. We give corollaries that generalize a
result of Lozin~\cite{Lozin02a} and prove a conjecture of
Lozin~\cite{Lozin02b} in a generalized form.
2000 Mathematics Subject Classification: 68Q15 (68Q17, 05C69, 05C70).
Keywords: Induced matchings, square-line graph, triangle-free graph, independent set,
NP-complete problem
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-26.ps.gz
DIMACS Home Page