Kratsch, Stefan ;
Sorge, Manuel
On Kernelization and Approximation for the Vector Connectivity Problem
Abstract
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) vertexdisjoint paths to S; this abstractly captures questions about placing servers in a network, or warehouses on a map, relative to demands. The problem is NPhard already for instances with d=4 (Cicalese et al., Theor. Comput. Sci. 2015), admits a logfactor approximation (Boros et al., Networks 2014), and is fixedparameter tractable in terms of k (Lokshtanov, unpublished 2014).
We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector dConnectivity where the upper bound d on demands is a constant. For Vector dConnectivity we give a factor dapproximation algorithm and construct a vertexlinear kernelization, i.e., an efficient reduction to an equivalent instance with f(d)k=O(k) vertices. For Vector Connectivity we get a factor optapproximation and we show that it has no kernelization to size polynomial in k+d unless NP \subseteq coNP/poly, making f(d)\poly(k) optimal for Vector dConnectivity. Finally, we provide a writeup for fixedparameter tractability of Vector Connectivity(k) by giving a different algorithm based on matroid intersection.
BibTeX  Entry
@InProceedings{kratsch_et_al:LIPIcs:2015:5598,
author = {Stefan Kratsch and Manuel Sorge},
title = {{On Kernelization and Approximation for the Vector Connectivity Problem}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {377388},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5598},
URN = {urn:nbn:de:0030drops55985},
doi = {10.4230/LIPIcs.IPEC.2015.377},
annote = {Keywords: parameterized complexity, kernelization, approximation}
}
19.11.2015
Keywords: 

parameterized complexity, kernelization, approximation 
Seminar: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Issue date: 

2015 
Date of publication: 

19.11.2015 