LIPIcs.IPEC.2017.18.pdf
- Filesize: 0.51 MB
- 13 pages
Document
Finding Connected Secluded Subgraphs
Authors
-
Part of:
Volume:
12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-03-02
Cite As Get BibTex
Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, and Pedro Montealegre. Finding Connected Secluded Subgraphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.IPEC.2017.18
Abstract
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough results and led to development of new techniques both within the traditional P vs NP dichotomy and within parameterized complexity. The Pi-Subgraph problem asks whether an input graph contains an induced subgraph on at least k vertices satisfying graph property Pi. For many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Pi-Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k+t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the Connected Secluded Pi-Subgraph problem is FPT when parameterized by just t for many important graph properties Pi.
Subject Classification
Keywords
- Secluded subgraph
- forbidden subgraphs
- parameterized complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
-
Shiri Chechik, Matthew P. Johnson, Merav Parter, and David Peleg. Secluded connectivity problems. In ESA 2013, volume 8125 of LNCS, pages 301-312. Springer, 2013.
- Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput., 45(4):1171-1229, 2016. URL: http://dx.doi.org/10.1137/15M1032077.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
- Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
- Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, and Alexander S. Kulikov. Parameterized complexity of secluded connectivity problems. Theory Comput. Syst., 61(3):795-819, 2017. URL: http://dx.doi.org/10.1007/s00224-016-9717-x.
- Falk Hüffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Isolation concepts for clique enumeration: Comparison and computational experiments. Theor. Comput. Sci., 410(52):5384-5397, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.05.008.
- Hiro Ito and Kazuo Iwama. Enumeration of isolated cliques and pseudo-cliques. ACM Trans. Algorithms, 5(4):40:1-40:21, 2009. URL: http://dx.doi.org/10.1145/1597036.1597044.
-
Matthew P. Johnson, Ou Liu, and George Rabanca. Secluded path via shortest path. In SIROCCO 2014, volume 8576 of LNCS, pages 108-120. Springer, 2014.
- Christian Komusiewicz, Falk Hüffner, Hannes Moser, and Rolf Niedermeier. Isolation concepts for efficiently enumerating dense subgraphs. Theor. Comput. Sci., 410(38-40):3640-3654, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.04.021.
- John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. URL: http://dx.doi.org/10.1016/0022-0000(80)90060-4.
- Dániel 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.
- Christos H. Papadimitriou and Mihalis Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci., 53(2):161-170, 1996. URL: http://dx.doi.org/10.1006/jcss.1996.0058.
- René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding secluded places of special interest in graphs. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 5:1-5:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.5.
- Mihalis Yannakakis. The effect of a connectivity requirement on the complexity of maximum subgraph problems. J. ACM, 26(4):618-630, 1979. URL: http://dx.doi.org/10.1145/322154.322157.