Document Open Access Logo

Finding Secluded Places of Special Interest in Graphs

Authors René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, Ondrej Suchý

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.5.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

René van Bevern
Till Fluschnik
George B. Mertzios
Hendrik Molter
Manuel Sorge
Ondrej Suchý

Cite As Get BibTex

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.5

Abstract

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.

Subject Classification

Keywords
  • Neighborhood
  • Feedback Vertex Set
  • Vertex Deletion
  • Separator
  • Dominating Set

Metrics

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

References

  1. R. van Bevern. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. PhD thesis, TU Berlin, 2014. Google Scholar
  2. R. van Bevern. Towards optimal and expressive kernelization for d-Hitting Set. Algorithmica, 70(1):129-147, 2014. Google Scholar
  3. R. van Bevern, H. Moser, and R. Niedermeier. Approximation and tidying - a problem kernel for s-Plex Cluster Vertex Deletion. Algorithmica, 62(3-4):930-950, 2012. Google Scholar
  4. L. Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Process. Lett., 58(4):171-176, 1996. Google Scholar
  5. S. Chechik, M. Johnson, M. Parter, and D. Peleg. Secluded connectivity problems. In Proc. 23rd ESA, volume 8125 of LNCS, pages 301-312. Springer, 2013. Google Scholar
  6. M. Dom, D. Lokshtanov, and S. Saurabh. Kernelization lower bounds through colors and IDs. ACM TALG, 11(2):13, 2014. Google Scholar
  7. R. Downey, V. Estivill-Castro, M. Fellows, E. Prieto, and F. Rosamond. Cutting up is hard to do: the parameterized complexity of k-Cut and related problems. Electr. Notes Theor. Comput. Sci., 78:209-222, 2003. URL: http://dx.doi.org/10.1016/S1571-0661(04)81014-4.
  8. S. Fafianie and S. Kratsch. A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. In Proc. 40th MFCS, volume 9235 of LNCS, pages 299-310. Springer, 2015. Google Scholar
  9. M. Fellows, J. Guo, H. Moser, and R. Niedermeier. A complexity dichotomy for finding disjoint solutions of vertex deletion problems. ACM ToCT, 2(2):5, 2011. Google Scholar
  10. M. Fellows, D. Hermelin, F. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  11. F. Fomin, P. Golovach, N. Karpov, and A. Kulikov. Parameterized complexity of secluded connectivity problems. In Proc. 35th FSTTCS, volume 45 of LIPIcs, pages 408-419. Schloss Dagstuhl, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.408.
  12. F. Fomin, P. Golovach, and J. Korhonen. On the parameterized complexity of cutting a few vertices from a graph. In Proc. 38th MFCS, volume 8087 of LNCS, pages 421-432. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40313-2_38.
  13. A. Giannopoulou, D. Lokshtanov, S. Saurabh, and O. Suchý. Tree deletion set has a polynomial kernel (but no OPT^O(1) approximation). In Proc. 34th FSTTCS, volume 29 of LIPIcs, pages 85-96. Schloss Dagstuhl, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.85.
  14. F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier. Isolation concepts for clique enumeration: Comparison and computational experiments. Theor. Comput. Sci., 410(52):5384-5397, 2009. Google Scholar
  15. F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier. Fixed-parameter algorithms for cluster vertex deletion. Theor. Comput. Syst., 47(1):196-217, 2010. Google Scholar
  16. F. Hüffner, C. Komusiewicz, and M. Sorge. Finding highly connected subgraphs. In Proc. 41st SOFSEM, volume 8939 of LNCS, pages 254-265. Springer, 2015. Google Scholar
  17. H. Ito, K. Iwama, and T. Osumi. Linear-time enumeration of isolated cliques. In Proc. 13th ESA, volume 3669 of LNCS, pages 119-130. Springer, 2005. Google Scholar
  18. C. Komusiewicz, F. Hüffner, H. Moser, and R. Niedermeier. Isolation concepts for efficiently enumerating dense subgraphs. Theor. Comput. Sci., 410(38-40):3640-3654, 2009. Google Scholar
  19. J. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. Google Scholar
  20. D. Lokshtanov, N. Misra, G. Philip, M. Ramanujan, and S. Saurabh. Hardness of r-dominating set on graphs of diameter (r + 1). In Proc. 8th IPEC, volume 8246 of LNCS, pages 255-267. Springer, 2013. Google Scholar
  21. D. Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.007.
  22. S. Seidman. Network structure and minimum degree. Soc. Networks, 5(3):269-287, 1983. Google Scholar
  23. S. Thomassé. A 4k² kernel for feedback vertex set. ACM TALG, 6(2), 2010. URL: http://dx.doi.org/10.1145/1721837.1721848.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact