In recent years, there has been a growing research interest in identifying “tenuous groups,” whose members have sparse connections, within social networks. However, existing work has predominantly focused on single-query scenarios, struggling to address the more prevalent multi-query situations found in the real world, such as assigning suitable reviewers to a large batch of papers. In this paper, we are the first to formulate the Multi-Query Keyword-based Tenuous Group (M-KTG) problem. The objective of M-KTG is to maximize the total keyword coverage for a set of group queries while satisfying a series of complex constraints, such as user frequency limits. As an NP-hard combinatorial optimization problem, the immense computational complexity of M-KTG makes it challenging for traditional serial algorithms to produce high-quality results within an acceptable timeframe. To tackle this challenge, we first propose a high-performance parallel algorithm for single queries. At its core is a parallel KTG solver (KTG-P) that employs an adaptive task splitting mechanism to dynamically decompose the vast search space into tasks suitable for concurrent execution on multi-core processors. We then apply this parallel solver to two serial strategies designed for M-KTG: a heuristic-based greedy algorithm (MKC) and a divide-and-conquer algorithm (GDC), developing their corresponding parallel versions, MKC-P and GDC-P. Our experiments on three real-world social networks demonstrate that our proposed parallel algorithms not only achieve significantly better solution quality than baseline methods but also exhibit substantial performance improvements over their serial counterparts.