Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
type: Item
instance of: scholarly article
title: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
zbMATH Open document ID: 1082.68592
author: Daniel Kobler
author: Udi Rotics
published in: Algorithmica
publication date: 2005-02-11T00:00:00Z
review text: In a graph \(G\) a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of \(G\). The maximum induced matching (abbreviated MIM) problem is to find the maximum size of an induced matching for a given graph \(G\). This problem is known to be NP-hard even on bipartite graphs or on planar graphs. We present a polynomial time algorithm which given a graph \(G\) either finds a maximum induced matching in \(G\), or claims that the size of a maximum induced matching in \(G\) is strictly less than the size of a maximum matching in \(G\). We show that the MIM problem is NP-hard on line-graphs, claw-free graphs, chair-free graphs, Hamiltonian graphs and \(r\)-regular graphs for \(r \geq 5\). On the other hand, we present polynomial time algorithms for the MIM problem on (\(P_5,D_m\))-free graphs, on (bull, chair)-free graphs and on line-graphs of Hamiltonian graphs.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 2133719
zbMATH Keywords: Induced matching
zbMATH Keywords: Line-graphs
zbMATH Keywords: Claw-free graphs
zbMATH Keywords: Bull
zbMATH Keywords: Regular graphs
zbMATH Keywords: Polynomial algorithms
MaRDI profile type: Publication
full work available at URL: s00453-003-1035-4
OpenAlex ID: W2032987509
DOI: 10.1007/S00453-003-1035-4
description: scientific article; zbMATH DE number 2133719