On Kernelization and Approximation for the Vector Connectivity Problem

Stefan Kratsch, Manuel Sorge

In the Vector Connectivity problem we are given an undirected graph $G=(V,E)$, a demand function $\varphi :V\to \{0,\dots ,d\}$, and an integer $k$. The question is whether there exi…