On the Structural Parameterizations of 2-Club with Triangle Constraints
For researchers in parameterized complexity, this paper extends the structural parameterization of s-Club variants to triangle constraints, but the results are incremental as they apply known techniques to a new problem variant.
The paper studies the Vertex r-Triangle s-Club problem, which asks for a large vertex subset with bounded diameter and triangle constraints, and provides FPT algorithms parameterized by treewidth, an XP algorithm parameterized by h-index, and a kernel of O(fes) edges parameterized by feedback edge number.
Given an undirected graph G = (V, E) and an integer k, the s-Club asks if Gcontains a vertex subset S of at least k vertices such that G[S] has diameter at most s. Recently, Vertex r-Triangle s-Club, and Edge r-Triangle s-Club that generalize the notion of s-Club have been studied by Garvardt et al. [TOCS-2023, IWOCA-2022] from the perspective of parameterized complexity. Given a graph G and an integer k, the Vertex r-Triangle s-Club asks if there is an s-Club S with at least k vertices such that every vertex u \in S is part of at least r triangles in G[S]. In this paper, we initiate a systematic study of Vertex r-Triangle s-Club for every integer r >= 1 from the perspective of structural parameters of the input graph. In particular, we provide FPT algorithms for Vertex r-Triangle 2-Club when parameterized by the treewidth (tw) of the input graph, and an XP algorithm when parameterized by the h-index of the input graph. Additionally, when parameterized by the feedback edge number (fes) of the input graph. We provide a kernel of O(fes) edges for Vertex r-Triangle s-Club.