2025/02/20 by Michael Lampis, Lampis, Michael, Manolis Vasilakis +1 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.2502.14161
openalex publication_date 2025/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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] recently studied these problems parameterized by treewidth, denoted by 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 6twnO(1) and a lower bound of (3-ε)twnO(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 5tw nO(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 3tw nO(1) algorithm is optimal under the pw-SETH (in fact improving over this for pathwidth or even for cutwidth 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 3cw nO(1), which is optimal under the pw-SETH from our previous result.