License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1361
URN: urn:nbn:de:0030-drops-13618
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1361/
Go to the corresponding LIPIcs Volume Portal

Kanj, Iyad A. ; Pelsmajer, Michael J. ; Xia, Ge ; Schaefer, Marcus

On the Induced Matching Problem

pdf-format:
22011.KanjIyad.Paper.1361.pdf (0.2 MB)

Abstract

We study extremal questions on induced matchings in several natural
graph classes. We argue that these questions should be asked for
twinless graphs, that is graphs not containing two vertices with
the same neighborhood. We show that planar twinless graphs always
contain an induced matching of size at least $n/40$ while there are
planar twinless graphs that do not contain an induced matching of
size $(n+10)/27$. We derive similar results for outerplanar graphs
and graphs of bounded genus. These extremal results can be applied
to the area of parameterized computation. For example, we show
that the induced matching problem on planar graphs has a kernel of
size at most $40k$ that is computable in linear time; this
significantly improves the results of Moser and Sikdar (2007). We
also show that we can decide in time $O(91^k + n)$ whether a planar
graph contains an induced matching of size at least $k$.

BibTeX - Entry

@InProceedings{kanj_et_al:LIPIcs:2008:1361,
  author =	{Iyad A. Kanj and Michael J. Pelsmajer and Ge Xia and Marcus Schaefer},
  title =	{{On the Induced Matching Problem}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{397--408},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1361},
  URN =		{urn:nbn:de:0030-drops-13618},
  doi =		{10.4230/LIPIcs.STACS.2008.1361},
  annote =	{Keywords: Induced matching, bounded genus graphs, parameterized algorithms, kernel}
}

Keywords: Induced matching, bounded genus graphs, parameterized algorithms, kernel
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI