License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.43
URN: urn:nbn:de:0030-drops-82178
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8217/
Habib, Michel ;
Mouatadid, Lalla
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Abstract
We study the maximum induced matching problem on a graph G.
Induced matchings correspond to independent sets in L^2(G), the square of the line graph of G.
The problem is NP-complete on bipartite graphs.
In this work, we show that for a number of graph families with forbidden vertex orderings, almost all forbidden patterns on three vertices are preserved when taking the square of the line graph.
These orderings can be computed in linear time in the size of the input graph.
In particular, given a graph class \mathcal{G} characterized by a vertex ordering, and a graph G=(V,E) \in \mathcal{G} with a corresponding vertex ordering \sigma of V, one can produce (in linear time in the size of G) an ordering on the vertices of L^2(G), that shows that L^2(G) \in \mathcal{G} - for a number of graph classes \mathcal{G} - without computing the line graph or the square of the line graph of G.
These results generalize and unify previous ones on showing closure under L^2(\cdot) for various graph families.
Furthermore, these orderings on L^2(G) can be exploited algorithmically to compute a maximum induced matching on G faster. We illustrate this latter fact in the second half of the paper where we focus on cocomparability graphs, a large graph class that includes interval, permutation, trapezoid graphs, and co-graphs, and we present the first \mathcal{O}(mn) time algorithm to compute a maximum weighted induced matching on cocomparability graphs; an improvement from the best known \mathcal{O}(n^4) time algorithm for the unweighted case.
BibTeX - Entry
@InProceedings{habib_et_al:LIPIcs:2017:8217,
author = {Michel Habib and Lalla Mouatadid},
title = {{Maximum Induced Matching Algorithms via Vertex Ordering Characterizations}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {43:1--43:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-054-5},
ISSN = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8217},
URN = {urn:nbn:de:0030-drops-82178},
doi = {10.4230/LIPIcs.ISAAC.2017.43},
annote = {Keywords: Maximum induced matching, Independent set, Vertex ordering charac- terization, Graph classes, Fast algorithms, Cocomparability graphs}
}
|
Keywords: |
|
Maximum induced matching, Independent set, Vertex ordering charac- terization, Graph classes, Fast algorithms, Cocomparability graphs |
|
Collection: |
|
28th International Symposium on Algorithms and Computation (ISAAC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.12.2017 |
