论文标题
S-Club的参数化复杂性，具有三角形和种子约束
The Parameterized Complexity of s-Club with Triangle and Seed Constraints
论文作者
论文摘要
S-Club问题要求，对于给定的无向图$ g $，$ g $是否包含一个顶点套装$ s的大小，至少$ k $，以便$ g [s] $，$ s $引起的$ g $的子图，最多为$ s $。我们考虑了$ s $ club的变体，其中另外一个要求$ g [s] $的每个顶点至少包含在$ g [s] $中的$ \ ell $ triangles中，$ g [s] $的每个边缘至少包含在$ g [s] $中，或者$ g [s] $或$ s $ s $ s $ s $ s $ $ s $ n eve $ w $ w $ w $ w $ w $ w $我们表明，当通过解决方案尺寸$ k $参数化时，这些变体是w [1] - hard，这使得它们比无约束的$ s $ club问题更难。从积极的一面来看，当$ \ ell = 1 $的情况下，以及当$ g [w] $（由种子顶点集合的$ g [w] $）是一个集团时，我们会获得一些fpt算法。
The s-Club problem asks, for a given undirected graph $G$, whether $G$ contains a vertex set $S$ of size at least $k$ such that $G[S]$, the subgraph of $G$ induced by $S$, has diameter at most $s$. We consider variants of $s$-Club where one additionally demands that each vertex of $G[S]$ is contained in at least $\ell$ triangles in $G[S]$, that each edge of $G[S]$ is contained in at least $\ell$~triangles in $G[S]$, or that $S$ contains a given set $W$ of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size $k$, making them significantly harder than the unconstrained $s$-Club problem. On the positive side, we obtain some FPT algorithms for the case when $\ell=1$ and for the case when $G[W]$, the graph induced by the set of seed vertices, is a clique.
