The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)

Abstract

We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\mathcal{S}$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=({\mathcal{V}}_H,{\mathcal{A}}_H)$ of $D$ such that (a) $\mathcal{S}\subseteq {\mathcal{V}}_H$, (b) $H$ is the union of $k$ directed walks in $D$, and (c) the underlying graph of $H$ includes a Steiner tree for $\mathcal{S}$ in $D$. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem.

An extended abstract published in: Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbanska, Pawel Zylinski, The Snow Team Problem - (Clearing Directed Subgraphs by Mobile Agents). FCT 2017: 190-203

References in corpus (3)

• The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
• On Directed Steiner Trees with Multiple Roots
• Approximating Directed Steiner Problems via Tree Embedding