DIMACS TR: 2004-26

Maximal induced matchings of minimum/maximum size

Authors: Yury L. Orlovich and Igor E. Zverovich

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