Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the$k$-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical$k$-truss problem aims to find the$k$-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the$k$-truss, we consider a novel problem called theminimum$k$-truss problem, which seeks to identify a$k$-truss with the minimum number of vertices, where$k\geq 2$is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithmMTEnumthat is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts,MTEnumstill faces practical efficiency issues which may be due to the fact that the$k$-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based frameworkDSA, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model callededge-based$s$-plex ($s$-eplex). With the hereditary property of$s$-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithmDSA. In particular,DSAruns up to five orders of magnitude faster than the baselineMTEnum.

The s -bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than n-s vertices are removed, where n is the number of vertices inside. Finding the largest s -bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of O* (2 n ), where O* suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to O* (λ n s ) where λ s is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.

Community search has widespread applications in areas such as advertising, friend recommendation, and protein complex identification. In this paper, we revisit the Size-bounded Community Search (SCS) problem, which aims to identify a connected subgraph containing a query vertex q and between l and h vertices, while maximizing the minimum degree of the subgraph. Existing state-of-the-art exact solutions for SCS face challenges in practical efficiency due to ineffective strategies for searching candidate solutions and suboptimal method for finding optimal solution. To address these challenges, we propose a novel branch-and-bound algorithm that efficiently locating a subset of candidate solutions with favorable structural properties, forming the basis for three progressively refined frameworks to determine the optimal solution. Furthermore, we enhance practical performance through a new heuristic, two reduction rules, and a query decomposition technique. Extensive experiments on 12 large real-world graphs demonstrate that our most efficient framework significantly outperforms state-of-the-art methods, achieving an average speedup of two orders of magnitude while consistently identifying communities with higher cohesion.

The$k$-vertex connected ($k$-VC) subgraph, which remains connected with fewer than$k$vertices being removed, is an essential structure in graph mining. It has found many applications, such as survivable network design and web search optimization. However, existing studies focus on mining maximal$k$-VCs, which are excessively large yet less cohesive in real applications. In this paper, we study theminimum$k$-VC search (MinVC)problem, seeking to find a$k$-VC with the minimum number of vertices. We formally prove that this problem is NP-hard and then propose two algorithms to obtain the exact solution. The basic method, calledEnum, follows a branch-and-bound framework with some pruning rules, which directly enumerates all possible vertex sets. Nonetheless, it suffers from the efficiency issues due to the non-hereditary property of the$k$-VC model. To address this challenge, we propose an advanced method, calledVCtoB, which divides theMinVCproblem into several new sub-problems, called thefixed-size$k$-VCproblems. Each of them can be solved efficiently by exploiting the hereditary property of the$s$-bundle model. Finally, our empirical experiments on 139 real-world networks demonstrate thatVCtoBachieves performance improvement of up to six orders of magnitude over the baseline.