{"ID":2868937,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16143","arxiv_id":"2509.16143","title":"On the Structural Parameterizations of 2-Club with Triangle Constraints","abstract":"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 \u003e= 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.","short_abstract":"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-2...","url_abs":"https://arxiv.org/abs/2509.16143","url_pdf":"https://arxiv.org/pdf/2509.16143v1","authors":"[\"Ashwin Jacob\",\"Diptapriyo Majumdar\",\"Raghav Sakhuja\"]","published":"2025-09-19T16:48:39Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}