
arXiv: 2107.12245
In this paper we study the kernelization of the $d$-Path Vertex Cover ($d$-PVC) problem. Given a graph $G$, the problem requires finding whether there exists a set of at most $k$ vertices whose removal from $G$ results in a graph that does not contain a path (not necessarily induced) with $d$ vertices. It is known that $d$-PVC is NP-complete for $d\geq 2$. Since the problem generalizes to $d$-Hitting Set, it is known to admit a kernel with $\mathcal{O}(dk^d)$ edges. We improve on this by giving better kernels. Specifically, we give kernels with $\mathcal{O}(k^2)$ vertices and edges for the cases when $d=4$ and $d=5$. Further, we give a kernel with $\mathcal{O}(k^4d^{2d+9})$ vertices and edges for general $d$.
FOS: Computer and information sciences, expansion lemma, \(d\)-hitting set, Computer science, 004, \(d\)-path vertex cover, d-Path Vertex Cover, Parameterized complexity, d-Hitting Set, Expansion Lemma, kernelization, Computer Science - Data Structures and Algorithms, Kernelization, Data Structures and Algorithms (cs.DS), parameterized complexity
FOS: Computer and information sciences, expansion lemma, \(d\)-hitting set, Computer science, 004, \(d\)-path vertex cover, d-Path Vertex Cover, Parameterized complexity, d-Hitting Set, Expansion Lemma, kernelization, Computer Science - Data Structures and Algorithms, Kernelization, Data Structures and Algorithms (cs.DS), parameterized complexity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
