Document Open Access Logo

Parameterized Complexity of Secluded Connectivity Problems

Authors Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.408.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Fedor V. Fomin
Petr A. Golovach
Nikolay Karpov
Alexander S. Kulikov

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, and Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 408-419, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.408

Abstract

The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure, which is the total weight of vertices in its closed neighborhood. In order to minimize the risk of intercepting the information, we are interested in selecting a secluded path, i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure of the tree is minimized. In this work, we obtain the following results about parameterized complexity of secluded connectivity problems. We start from an observation that being parameterized by the size of the exposure, the problem is fixed-parameter tractable (FPT). More precisely, we give an algorithm deciding if a graph G with a given cost function w:V(G)->N contains a secluded path of exposure at most k with the cost at most C in time O(3^{k/3}(n+m) log W), where W is the maximum value of w on an input graph G. Similarly, Secluded Steiner Tree is solvable in time O(2^{k}k^2 (n+m) log W). The main result of this paper is about "above guarantee" parameterizations for secluded problems. We show that Secluded Steiner Tree is FPT being parameterized by r+p, where p is the number of the terminals, l the size of an optimum Steiner tree, and r=k-l. We complement this result by showing that the problem is co-W[1]-hard when parameterized by r only. We also investigate Secluded Steiner Tree from kernelization perspective and provide several lower and upper bounds when parameters are the treewidth, the size of a vertex cover, maximum vertex degree and the solution size. Finally, we refine the algorithmic result of Chechik et al. by improving the exponential dependence from the treewidth of the input graph.
Keywords
  • Secluded path
  • Secluded Steiner tree
  • parameterized complexity

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: fast subset convolution. In STOC 2007, pages 67-74. ACM, 2007. Google Scholar
  3. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In ICALP 2013, Part I, volume 7965 of Lecture Notes in Computer Science, pages 196-207. Springer, 2013. Google Scholar
  4. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. Google Scholar
  5. 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
  6. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In IWPEC 2006, volume 4169 of Lecture Notes in Computer Science, pages 239-250. Springer, 2006. Google Scholar
  7. Shiri Chechik, Matthew P. Johnson, Merav Parter, and David Peleg. Secluded connectivity problems. CoRR, abs/1212.6176, 2012. Google Scholar
  8. Shiri Chechik, Matthew P. Johnson, Merav Parter, and David Peleg. Secluded connectivity problems. In ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 301-312. Springer, 2013. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS 2011, pages 150-159. IEEE, 2011. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  13. Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, and Alexander S. Kulikov. Parameterized complexity of secluded connectivity problems. CoRR, abs/1502.03989, 2015. Google Scholar
  14. Fedor V Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In SODA 2014, pages 142-151, 2014. Google Scholar
  15. Jianhang Gao, Qing Zhao, and Ananthram Swami. The thinnest path problem for secure communications: A directed hypergraph approach. In Proceedings of the 50th Annual Allerton Conference on Communication, Control, and Computing, 2012, pages 847-852. IEEE, 2012. Google Scholar
  16. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  17. Alexander Gilbers. Visibility Domains and Complexity. PhD thesis. Rheinische Friedrich-Wilhelms-Universität Bonn, Bonn, 2013. Google Scholar
  18. Matthew P. Johnson, Ou Liu, and George Rabanca. Secluded path via shortest path. In SIROCCO 2014, volume 8576 of Lecture Notes in Computer Science, pages 108-120. Springer, 2014. Google Scholar
  19. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  20. M. Naor, L.J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In FOCS 1995, pages 182-191. IEEE, 1995. Google Scholar
  21. Jesper Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica, 65(4):868-884, 2013. 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