Structural Parameterizations for Induced and Acyclic Matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916946852708352 |
|---|---|
| author | Lampis, Michael Vasilakis, Manolis |
| author_facet | Lampis, Michael Vasilakis, Manolis |
| contents | 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 $\mathrm{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^{\mathrm{tw}}n^{\mathcal{O}(1)}$ and a lower bound of $(3-\varepsilon)^{\mathrm{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^{\mathrm{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^{\mathrm{tw}} n^{\mathcal{O}(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 $3^{\mathrm{cw}} n^{\mathcal{O}(1)}$, which is optimal under the pw-SETH from our previous result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14161 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Structural Parameterizations for Induced and Acyclic Matching Lampis, Michael Vasilakis, Manolis Data Structures and Algorithms Computational Complexity 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 $\mathrm{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^{\mathrm{tw}}n^{\mathcal{O}(1)}$ and a lower bound of $(3-\varepsilon)^{\mathrm{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^{\mathrm{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^{\mathrm{tw}} n^{\mathcal{O}(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 $3^{\mathrm{cw}} n^{\mathcal{O}(1)}$, which is optimal under the pw-SETH from our previous result. |
| title | Structural Parameterizations for Induced and Acyclic Matching |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2502.14161 |