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.
展开▼
机译：与查找满足给定属性的诱导子图有关的问题构成了图算法中研究最多的领域之一。这些问题已引起突破性的结果，并导致在传统的P vs NP二分法内以及参数化复杂度内开发新技术。 Pi-Subgraph问题询问输入图是否至少在满足图属性Pi的k个顶点上包含诱导子图。对于许多应用程序，希望找到的子图与图的其余部分的连接尽可能少，这会引起“孤立的Pi-子图”问题。在此，输入k是所需子图的大小，输入t是对该子图在其余图中具有的邻居数的限制。已经从参数化的角度研究了这个问题，不幸的是，即使通过k + t进行参数化，对于许多图形属性Pi来说，它仍然是W [1] -hard。我们发现当寻找满足Pi的连通诱导子图时，情况发生了变化。尤其是，我们表明，对于许多重要的图形属性Pi，仅通过t进行参数化时，连通偏僻Pi子图问题就是FPT。
展开▼
