A Linear Kernel for Planar Vector Domination
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916798124785664 |
|---|---|
| author | Sahili, Mahabba El Abu-Khzam, Faisal N. |
| author_facet | Sahili, Mahabba El Abu-Khzam, Faisal N. |
| contents | Given a graph $G$, an integer $k\geq 0$, and a non-negative integral function $f:V(G) \rightarrow \mathcal{N}$, the Vector Domination problem asks whether a set $S$ of vertices, of cardinality $k$ or less, exists in $G$ so that every vertex $v \in V(G)\setminus S$ has at least $f(v)$ neighbors in $S$. The problem generalizes several domination problems and it has also been shown to generalize Bounded-Degree Vertex Deletion (BDVD). In this paper, the parameterized version of Vector Domination is studied when the input graph is planar. A linear problem kernel is presented. A direct consequence is a kernel bound for BDVD that is linear in the parameter $k$ only. Previously known bounds are functions of both the target degree and the input parameter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_09374 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Linear Kernel for Planar Vector Domination Sahili, Mahabba El Abu-Khzam, Faisal N. Combinatorics Computational Complexity Discrete Mathematics Given a graph $G$, an integer $k\geq 0$, and a non-negative integral function $f:V(G) \rightarrow \mathcal{N}$, the Vector Domination problem asks whether a set $S$ of vertices, of cardinality $k$ or less, exists in $G$ so that every vertex $v \in V(G)\setminus S$ has at least $f(v)$ neighbors in $S$. The problem generalizes several domination problems and it has also been shown to generalize Bounded-Degree Vertex Deletion (BDVD). In this paper, the parameterized version of Vector Domination is studied when the input graph is planar. A linear problem kernel is presented. A direct consequence is a kernel bound for BDVD that is linear in the parameter $k$ only. Previously known bounds are functions of both the target degree and the input parameter. |
| title | A Linear Kernel for Planar Vector Domination |
| topic | Combinatorics Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2312.09374 |