License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.39
URN: urn:nbn:de:0030-drops-176914
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17691/
Go to the corresponding LIPIcs Volume Portal

Koana, Tomohiro

Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability

pdf-format:
LIPIcs-STACS-2023-39.pdf (0.9 MB)

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 Gallai-Edmonds 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 Fixed-Parameter Tractability}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17691},
  URN =		{urn:nbn:de:0030-drops-176914},
  doi =		{10.4230/LIPIcs.STACS.2023.39},
  annote =	{Keywords: Parameterized Complexity, Below Guarantees, Induced Matching, Gallai-Edmonds Decomposition}
}

Keywords: Parameterized Complexity, Below Guarantees, Induced Matching, Gallai-Edmonds Decomposition
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

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