An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913238216605696 |
|---|---|
| author | Liu, Yuxi Xiao, Mingyu |
| author_facet | Liu, Yuxi Xiao, Mingyu |
| contents | An induced subgraph is called an induced matching if each vertex is a degree-1 vertex in the subgraph. The \textsc{Almost Induced Matching} problem asks whether we can delete at most $k$ vertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size $k$ of the deletion set as the parameter. First, we prove a $6k$-vertex kernel for this problem, improving the previous result of $7k$. Second, we give an $O^*(1.6765^k)$-time and polynomial-space algorithm, improving the previous running-time bound of $O^*(1.7485^k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14116 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Improved Kernel and Parameterized Algorithm for Almost Induced Matching Liu, Yuxi Xiao, Mingyu Data Structures and Algorithms An induced subgraph is called an induced matching if each vertex is a degree-1 vertex in the subgraph. The \textsc{Almost Induced Matching} problem asks whether we can delete at most $k$ vertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size $k$ of the deletion set as the parameter. First, we prove a $6k$-vertex kernel for this problem, improving the previous result of $7k$. Second, we give an $O^*(1.6765^k)$-time and polynomial-space algorithm, improving the previous running-time bound of $O^*(1.7485^k)$. |
| title | An Improved Kernel and Parameterized Algorithm for Almost Induced Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.14116 |