TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 07.01.2016

isti-logo

Page Content

to Navigation

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.


Date
Speaker
Location
Language
07.01.2016
16:15
Manuel Sorge
TEL 512
English

 

Back to the research colloquium site.

 

 

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe