Parameterized Algorithms for Minimum Sum Vertex Cover
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916086880927744 |
|---|---|
| author | Aute, Shubhada Panolan, Fahad |
| author_facet | Aute, Shubhada Panolan, Fahad |
| contents | Minimum sum vertex cover of an $n$-vertex graph $G$ is a bijection $ϕ: V(G) \to [n]$ that minimizes the cost $\sum_{\{u,v\} \in E(G)} \min \{ϕ(u), ϕ(v) \}$. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is $16/9$ [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than $1.014$ for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results.
1. MSVC can be solved in $2^{2^{O(k)}} n^{O(1)}$ time, where $k$ is the size of a minimum vertex cover.
2. MSVC can be solved in $f(k)\cdot n^{O(1)}$ time for some computable function $f$, where $k$ is the size of a minimum clique modulator. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_05085 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Algorithms for Minimum Sum Vertex Cover Aute, Shubhada Panolan, Fahad Data Structures and Algorithms Minimum sum vertex cover of an $n$-vertex graph $G$ is a bijection $ϕ: V(G) \to [n]$ that minimizes the cost $\sum_{\{u,v\} \in E(G)} \min \{ϕ(u), ϕ(v) \}$. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is $16/9$ [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than $1.014$ for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. 1. MSVC can be solved in $2^{2^{O(k)}} n^{O(1)}$ time, where $k$ is the size of a minimum vertex cover. 2. MSVC can be solved in $f(k)\cdot n^{O(1)}$ time for some computable function $f$, where $k$ is the size of a minimum clique modulator. |
| title | Parameterized Algorithms for Minimum Sum Vertex Cover |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.05085 |