Abstract
In this work, we study the Induced Matching problem: Given an undirected graph G and an integer ?, is there an induced matching M of size at least ?? An edge subset M is an induced matching in G if M is a matching such that there is no edge between two distinct edges of M. Our work looks into the parameterized complexity of Induced Matching with respect to "below guarantee" parameterizations. We consider the parameterization u  ? for an upper bound u on the size of any induced matching. For instance, any induced matching is of size at most n/2 where n is the number of vertices, which gives us a parameter n/2  ?. In fact, there is a straightforward 9^{n/2  ?} ⋅ n^O(1)time algorithm for Induced Matching [Moser and Thilikos, J. Discrete Algorithms]. Motivated by this, we ask: Is Induced Matching FPT for a parameter smaller than n/2  ?? In search for such parameters, we consider MM(G)  ? and IS(G)  ?, where MM(G) is the maximum matching size and IS(G) is the maximum independent set size of G. We find that Induced Matching is presumably not FPT when parameterized by MM(G)  ? or IS(G)  ?. In contrast to these intractability results, we find that taking the average of the two helps  our main result is a branching algorithm that solves Induced Matching in 49^{(MM(G) + IS(G))/ 2  ?} ⋅ n^O(1) time. Our algorithm makes use of the GallaiEdmonds decomposition to find a structure to branch on.
BibTeX  Entry
@InProceedings{koana:LIPIcs.STACS.2023.39,
author = {Koana, Tomohiro},
title = {{Induced Matching Below Guarantees: Average Paves the Way for FixedParameter Tractability}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {39:139:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17691},
URN = {urn:nbn:de:0030drops176914},
doi = {10.4230/LIPIcs.STACS.2023.39},
annote = {Keywords: Parameterized Complexity, Below Guarantees, Induced Matching, GallaiEdmonds Decomposition}
}
Keywords: 

Parameterized Complexity, Below Guarantees, Induced Matching, GallaiEdmonds Decomposition 
Collection: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 
Issue Date: 

2023 
Date of publication: 

03.03.2023 