On the complexity of the vector connectivity problem

Ferdinando Cicalese, Martin Milanič, Romeo Rizzi

We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph $G$ with a requirement $r(v)$ for each vertex $v$, VecCon asks for a minim…