On Kernelization and Approximation for the Vector Connectivity Problem

Authors Stefan Kratsch, Manuel Sorge



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.377.pdf
  • Filesize: 460 kB
  • 12 pages

Document Identifiers

Author Details

Stefan Kratsch
Manuel Sorge

Cite AsGet BibTex

Stefan Kratsch and Manuel Sorge. On Kernelization and Approximation for the Vector Connectivity Problem. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.IPEC.2015.377

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) 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.
Keywords
  • parameterized complexity
  • kernelization
  • approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. Google Scholar
  2. Endre Boros, Pinar Heggernes, Pim van 't Hof, and Martin Milanič. Vector connectivity in graphs. Networks, 63(4):277-285, 2014. Google Scholar
  3. Ferdinando Cicalese, Martin Milanič, and Romeo Rizzi. On the complexity of the vector connectivity problem. Theor. Comput. Sci., 591:60-71, 2015. Google Scholar
  4. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and IDs. ACM T. Alg., 11(2):13:1-13:20, 2014. Google Scholar
  5. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In Proc. 30th STACS, pages 92-103. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  6. Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702-730, 2015. Google Scholar
  7. Stasys Jukna. Extremal combinatorics - with applications in computer science. Texts in theoretical computer science. Springer, 2001. Google Scholar
  8. Dàniel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail