Collective Graph Exploration Parameterized by Vertex Cover

We initiate the study of the parameterized complexity of the {\sc Collective Graph Exploration} ({\sc CGE}) problem. In {\sc CGE}, the input consists of an undirected connected graph $G$ and a collection of $k$ robots, initially placed at the same vertex $r$ of $G$, and each one of them has an energy budget of $B$. The objective is to decide whether $G$ can be \emph{explored} by the $k$ robots in $B$ time steps, i.e., there exist $k$ closed walks in $G$, one corresponding to each robot, such that every edge is covered by at least one walk, every walk starts and ends at the vertex $r$, and the maximum length of any walk is at most $B$. Unfortunately, this problem is $\mathsf{\text{NP}}$-hard even on trees [Fraigniaud {\em et~al.}, 2006]. Further, we prove that the problem remains $\mathsf{\text{W[1]}}$-hard parameterized by $k$ even for trees of treedepth $3$. Due to the $\mathsf{\text{para-NP}}$-hardness of the problem parameterized by treedepth, and motivated by real-world scenarios, we study the parameterized complexity of the problem parameterized by the vertex cover number ($\mathsf{v}\mathsf{c}$) of the graph, and prove that the problem is fixed-parameter tractable ($\mathsf{\text{FPT}}$) parameterized by $\mathsf{v}\mathsf{c}$. Additionally, we study the optimization version of {\sc CGE}, where we want to optimize $B$, and design an approximation algorithm with an additive approximation factor of $O(\mathsf{v}\mathsf{c})$.