Paper Info
Title
Improved induced matchings in sparse graphs
Abstract
An induced matching in a graph G = ( V , E ) is a matching M such that ( V , M ) is an induced subgraph of G . Clearly, among two vertices with the same neighbourhood (called twins ) at most one is matched in any induced matching, and if one of them is matched then there is another matching of the same size that matches the other vertex. Motivated by this, Kanj et al.  [10] studied induced matchings in twinless graphs. They showed that any twinless planar graph contains an induced matching of size at least n 40 and that there are twinless planar graphs that do not contain an induced matching of size greater than n 27 + O ( 1 ) . We improve both these bounds to n 28 + O ( 1 ) , which is tight up to an additive constant. This implies that the problem of deciding whether a planar graph has an induced matching of size k has a kernel of size at most 28 k . We also show for the first time that this problem is fixed parameter tractable for graphs of bounded arboricity. Kanj et al. also presented an algorithm which decides in O ( 2 159 k + n ) -time whether an n -vertex planar graph contains an induced matching of size k . Our results improve the time complexity analysis of their algorithm. However, we also show a more efficient O ( 2 25.5 k + n ) -time algorithm. Its main ingredient is a new, O ∗ ( 4 l ) -time algorithm for finding a maximum induced matching in a graph of branch width at most l .
Year
DOI
Venue
2010
10.1016/j.dam.2010.08.026
Discrete Applied Mathematics
Keywords
Field
DocType
planar graphs,sparse graphs,fpt algorithm,induced matching
Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Induced subgraph,Time complexity,Arboricity,Planar graph,Mathematics,Bounded function,Dense graph
Journal
Volume
Issue
ISSN
158
18
Discrete Applied Mathematics
Citations 
PageRank 
References 
5
0.48
19
Authors
4
Name
Order
Citations
PageRank
Rok Erman1101.64
Łukasz Kowalik225822.43
Matjaz Krnc382.60
Tomasz Waleń470639.62