direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

On Kernelization and Approximation for the Vector Connectivity Problem

Manuel Sorge (TU Berlin)


In the Vector Connectivity problem we are given an undirected graph G=(V,E), a demand function phi: V -> {0,...,d}, and an integer k. The question is whether there exists a set S of at most k vertices such that every vertex v in V\S has at least phi(v) vertex-disjoint paths to S; this abstractly captures questions about placing servers in a network, or warehouses on a map, relative to demands. The problem is NP-hard already for instances with d=4 (Cicalese et al., Theor. Comput. Sci. 2015), admits a log-factor approximation (Boros et al., Networks 2014), and is fixed-parameter tractable in terms of k (Lokshtanov, unpublished 2014).
We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector d-Connectivity where the upper bound d on demands is a constant. For Vector d-Connectivity we give a factor d-approximation algorithm and construct a vertex-linear kernelization, i.e., an efficient reduction to an equivalent instance with f(d)k=O(k) vertices. For Vector Connectivity we get a factor opt-approximation and we show that it has no kernelization to size polynomial in k+d unless NP ‚äÜ coNP/poly, making f(d)\poly(k) optimal for Vector d-Connectivity. Finally, we provide a write-up for fixed-parameter tractability of Vector Connectivity(k) by giving a different algorithm based on matroid intersection.

This is joint work with Stefan Kratsch.

Manuel Sorge
TEL 512


Back to the research colloquium site.



Zusatzinformationen / Extras