论文标题
诱导的匹配以下保证：平均铺平了固定参数障碍的道路
Induced Matching below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
论文作者
论文摘要
在这项工作中，我们研究了引起的匹配问题：鉴于无向图$ g $和整数$ \ ell $，是否有诱导的匹配$ m $的大小至少$ \ ell $？如果$ m $是匹配，则边缘子集$ m $是$ g $的引起匹配，因此两个不同的边缘之间没有$ m $的边缘。我们的工作从“低于保证”参数化方面介绍了诱导匹配的参数化复杂性。我们将上限$ u $ $ $ $ u $ $ u $的参数化$ u - \ ell $在任何引起的匹配的大小上。例如，任何感应的匹配最多都是$ n / 2 $，其中$ n $是顶点的数量，这为我们提供了一个参数$ n / 2 - \ ell $。实际上，有一个直接的$ 9^{n/2 - \ ell} \ cdot n^{o（1）} $ - 诱导匹配的时间算法[Moser和Thilikos，J。离散算法]。在此的动机上，我们问：是否将匹配的fpt匹配到小于$ n / 2- \ ell $的参数？在搜索此类参数时，我们考虑$ mm（g） - \ ell $，$ is（g） - \ ell $，其中$ mm（g）$是最大匹配大小，$ is（g）$是$ g $的最大独立集尺寸。我们发现，当通过$ mm（g） - \ ell $或$是（g） - \ ell $参数化时，诱导的匹配可能不是FPT。与这些顽固性结果相反，我们发现取决于两者的平均值 - 我们的主要结果是一种分支算法，该算法求解了$ 49^{（g） + IS（g） + IS（g）/ 2- \ ell} \ cdot n^{o（g） + is（g） + is（g） + is（g） + is（g） + cd {o（g）{o（g））} $。我们的算法利用加莱 - 埃德蒙兹分解来找到一个要分支的结构。
In this work, we study the Induced Matching problem: Given an undirected graph $G$ and an integer $\ell$, is there an induced matching $M$ of size at least $\ell$? 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 - \ell$ 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 - \ell$. In fact, there is a straightforward $9^{n/2 - \ell} \cdot 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 - \ell$? In search for such parameters, we consider $MM(G) - \ell$ and $IS(G) - \ell$, 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) - \ell$ or $IS(G) - \ell$. 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 - \ell} \cdot n^{O(1)}$ time. Our algorithm makes use of the Gallai-Edmonds decomposition to find a structure to branch on.
