Structural Parameterizations for Induced and Acyclic Matching
摘要
We revisit the (structurally) parameterized complexity of Induced Matching and Acyclic Matching, two problems where we seek to find a maximum independent set of edges whose endpoints induce, respectively, a matching and a forest. Chaudhary and Zehavi [WG ’23, SIDMA ’25] recently studied these problems parameterized by treewidth, denoted by \(\textrm{tw}\) . We resolve several of the problems left open in their work and extend their results as follows: (i) for Acyclic Matching, Chaudhary and Zehavi gave an algorithm of running time \(6^{\textrm{tw}}n^{\mathcal {O}(1)}\) and a lower bound of \((3-\varepsilon )^{\textrm{tw}}n^{\mathcal {O}(1)}\) (under the SETH); we close this gap by, on the one hand giving a more careful analysis of their algorithm showing that its complexity is actually \(5^{\textrm{tw}} n^{\mathcal {O}(1)}\) , and on the other giving a pw-SETH-based lower bound showing that this running time cannot be improved (even for pathwidth), (ii) for Induced Matching we show that their \(3^{\textrm{tw}} n^{\mathcal {O}(1)}\) algorithm is optimal under the pw-SETH (in fact improving over this for pathwidth is equivalent to falsifying the pw-SETH) by adapting a recent reduction for Bounded Degree Vertex Deletion, (iii) for both problems we give FPT algorithms with single-exponential dependence when parameterized by clique-width and in particular for Induced Matching our algorithm has running time \(3^{\textrm{cw}} n^{\mathcal {O}(1)}\) , which is optimal under the pw-SETH from our previous result.