Source author record

Radovan Červený

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Faster FPT Algorithm for 5-Path Vertex Cover

The problem of $d$ -Path Vertex Cover, $d$ -PVC lies in determining a subset $F$ of vertices of a given graph $G=(V,E)$ such that $G \setminus F$ does not contain a path on $d$ vertices. The paths we aim to cover need not to be induced. It is known that the $d$ -PVC problem is NP-complete for any $d \ge 2$ . When parameterized by the size of the solution $k$ , 5-PVC has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since $d$ -PVC is a special case of $d$ -Hitting Set, an algorithm running in $\mathcal{O}(4.0755^kn^{\mathcal{O}(1)})$ time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.

preprint2022arXiv

On Kernels for d-Path Vertex Cover

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$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.