A Parameterized Perspective on Uniquely Restricted Matchings
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912539850309632 |
|---|---|
| author | Chaudhary, Juhi Sau, Ignasi Zehavi, Meirav |
| author_facet | Chaudhary, Juhi Sau, Ignasi Zehavi, Meirav |
| contents | Given a graph G, a matching is a subset of edges of G that do not share an endpoint. A matching M is uniquely restricted if the subgraph induced by the endpoints of the edges of M has exactly one perfect matching. Given a graph G and a positive integer \ell, Uniquely Restricted Matching asks whether G has a uniquely restricted matching of size at least \ell. In this paper, we study the parameterized complexity of Uniquely Restricted Matching under various parameters. Specifically, we show that Uniquely Restricted Matching admits a fixed-parameter tractable (FPT) algorithm on line graphs when parameterized by the solution size. We also establish that the problem is FPT when parameterized by the treewidth of the input graph. Furthermore, we show that Uniquely Restricted Matching does not admit a polynomial kernel with respect to the vertex cover number plus the size of the matching unless NP \subseteq coNP/poly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12004 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Parameterized Perspective on Uniquely Restricted Matchings Chaudhary, Juhi Sau, Ignasi Zehavi, Meirav Data Structures and Algorithms Discrete Mathematics Given a graph G, a matching is a subset of edges of G that do not share an endpoint. A matching M is uniquely restricted if the subgraph induced by the endpoints of the edges of M has exactly one perfect matching. Given a graph G and a positive integer \ell, Uniquely Restricted Matching asks whether G has a uniquely restricted matching of size at least \ell. In this paper, we study the parameterized complexity of Uniquely Restricted Matching under various parameters. Specifically, we show that Uniquely Restricted Matching admits a fixed-parameter tractable (FPT) algorithm on line graphs when parameterized by the solution size. We also establish that the problem is FPT when parameterized by the treewidth of the input graph. Furthermore, we show that Uniquely Restricted Matching does not admit a polynomial kernel with respect to the vertex cover number plus the size of the matching unless NP \subseteq coNP/poly. |
| title | A Parameterized Perspective on Uniquely Restricted Matchings |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2508.12004 |