2026-07-23T06:52:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5598 2024-03-06T10:36:38Z ddc:004 open_access

On Kernelization and Approximation for the Vector Connectivity Problem Kratsch, Stefan Sorge, Manuel parameterized complexity kernelization approximation 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 \subseteq 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kratsch and Manuel Sorge 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.377 urn:nbn:de:0030-drops-55985 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.377 eng https://creativecommons.org/licenses/by/3.0/legalcode