Finding connected secluded subgraphs

Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, Pedro Montealegre

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

2 Citas (Scopus)


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 Π-Subgraph problem asks whether an input graph contains an induced subgraph on at least k vertices satisfying graph property Π. 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 Π-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 Π, even when parameterized by k + t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Π. In particular, we show that the Connected Secluded Π-Subgraph problem is FPT when parameterized by just t for many important graph properties Π.

Idioma originalInglés
Título de la publicación alojada12th International Symposium on Parameterized and Exact Computation, IPEC 2017
EditoresDaniel Lokshtanov, Naomi Nishimura
EditorialSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (versión digital)9783959770514
EstadoPublicada - 1 feb. 2018
Publicado de forma externa
Evento12th International Symposium on Parameterized and Exact Computation, IPEC 2017 - Vienna, Austria
Duración: 6 sep. 20178 sep. 2017

Serie de la publicación

NombreLeibniz International Proceedings in Informatics, LIPIcs
ISSN (versión impresa)1868-8969


Conferencia12th International Symposium on Parameterized and Exact Computation, IPEC 2017


Profundice en los temas de investigación de 'Finding connected secluded subgraphs'. En conjunto forman una huella única.

Citar esto