{
"type": "article-journal",
"id": "https://doi.org/10.4230/lipics.stacs.2008.1361",
"categories": [
"Computer Science",
"000 Computer science, knowledge, general works"
],
"language": "eng",
"author": [
{
"family": "Kanj",
"given": "Iyad A."
},
{
"family": "Pelsmajer",
"given": "Michael J."
},
{
"family": "Xia",
"given": "Ge"
},
{
"family": "Schaefer",
"given": "Marcus"
}
],
"editor": [
{
"family": "Herbstritt",
"given": "Marc"
}
],
"issued": {
"date-parts": [
[
2008
]
]
},
"abstract": "We study extremal questions on induced matchings in several natural\n graph classes. We argue that these questions should be asked for\n twinless graphs, that is graphs not containing two vertices with\n the same neighborhood. We show that planar twinless graphs always\n contain an induced matching of size at least $n/40$ while there are\n planar twinless graphs that do not contain an induced matching of\n size $(n+10)/27$. We derive similar results for outerplanar graphs\n and graphs of bounded genus. These extremal results can be applied\n to the area of parameterized computation. For example, we show\n that the induced matching problem on planar graphs has a kernel of\n size at most $40k$ that is computable in linear time; this\n significantly improves the results of Moser and Sikdar (2007). We\n also show that we can decide in time $O(91^k + n)$ whether a planar\n graph contains an induced matching of size at least $k$.",
"DOI": "10.4230/lipics.stacs.2008.1361",
"publisher": "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany",
"title": "On the Induced Matching Problem",
"version": "1.0"
}