Minimum sum vertex cover: kernelization and parameterized algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911838462017536 |
|---|---|
| author | Cao, Yixin Gai, Ling Liu, Jingyi Wang, Jianxin |
| author_facet | Cao, Yixin Gai, Ling Liu, Jingyi Wang, Jianxin |
| contents | Given an ordering of the vertices of a graph, the cost of covering an edge is the smaller number of its two ends. The minimum sum vertex cover problem asks for an ordering that minimizes the total cost of covering all edges. We consider parameterized complexity of this problem, using the largest cost~$k$ of covering a single edge as the parameter. Note that the first $k$ vertices form a (not necessarily minimal) vertex cover of the graph, and the ordering of vertices after $k$ is irrelevant. We present a $(k^2 + 2 k)$-vertex kernel and an $O(m + 2^kk! k^4)$-time algorithm for the minimum sum vertex cover problem, where $m$ is the size of the input graph. Since our parameter~$k$ is polynomially bounded by the vertex cover number of the input graph, our results also apply to that parameterization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18497 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimum sum vertex cover: kernelization and parameterized algorithms Cao, Yixin Gai, Ling Liu, Jingyi Wang, Jianxin Data Structures and Algorithms Given an ordering of the vertices of a graph, the cost of covering an edge is the smaller number of its two ends. The minimum sum vertex cover problem asks for an ordering that minimizes the total cost of covering all edges. We consider parameterized complexity of this problem, using the largest cost~$k$ of covering a single edge as the parameter. Note that the first $k$ vertices form a (not necessarily minimal) vertex cover of the graph, and the ordering of vertices after $k$ is irrelevant. We present a $(k^2 + 2 k)$-vertex kernel and an $O(m + 2^kk! k^4)$-time algorithm for the minimum sum vertex cover problem, where $m$ is the size of the input graph. Since our parameter~$k$ is polynomially bounded by the vertex cover number of the input graph, our results also apply to that parameterization. |
| title | Minimum sum vertex cover: kernelization and parameterized algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.18497 |