English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this work, we study the Induced Matching problem: Given an undirectedgraph $G$ and an integer $\ell$, is there an induced matching $M$ of size atleast $\ell$? An edge subset $M$ is an induced matching in $G$ if $M$ is amatching such that there is no edge between two distinct edges of $M$. Our worklooks 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 ofvertices, which gives us a parameter $n / 2 - \ell$. In fact, there is astraightforward $9^{n/2 - \ell} \cdot n^{O(1)}$-time algorithm for InducedMatching [Moser and Thilikos, J. Discrete Algorithms]. Motivated by this, weask: Is Induced Matching FPT for a parameter smaller than $n / 2 - \ell$? Insearch 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 maximumindependent set size of $G$. We find that Induced Matching is presumably notFPT when parameterized by $MM(G) - \ell$ or $IS(G) - \ell$. In contrast tothese 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 useof the Gallai-Edmonds decomposition to find a structure to branch on.

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