As a fundamental graph problem, community search is applied in various areas, e.g., social networks, the world wide web, and biology. A common requirement from real applications is to return a community with a bounded size while most existing solutions do not constrain community size. Recent studies on size-constrained community search still have some critical issues, e.g., the existence of a better cohesiveness objective, some queries returning empty results, and inefficiency on partial queries. Thus, in this paper, we study the size-constrained truss community search (STCS). Given a graph $G$ , a query vertex $q$ , and size constraint $[l,h]$ , the STCS problem aims to find a subgraph containing $q$ with the largest min-support among all connected subgraphs having at least $l$ and at most $h$ vertices. We prove the STCS problem is NP-hard and APX-hard unless P = NP. An effective heuristic is proposed to quickly find a high-quality initial result. Then, a branch and bound algorithm is introduced to find the exact result, with novel optimizations, e.g., budget-cost-based bounding and branching strategies. Extensive experiments verify that the community quality returned by our algorithm is better and our algorithm is faster by up to 5 orders of magnitude, compared with the state-of-the-art.

In this paper, we study the problem of maximal biclique enumeration on large signed bipartite graphs. Given a signed bipartite graph $G=(U,V,E,s)$ , a parameter $\theta \in [0.5, 1.0]$ , our goal is to efficiently enumerate all maximal $\theta$ -bicliques in $G$ , where a maximal $\theta$ -biclique $B(L,R)$ is a complete subgraph of $G$ with (1) the proportion of positive neighbors for each vertex in $B$ is at least $\theta$ , and (2) $B$ is not contained in another biclique $B^{\prime }$ , while $B^{\prime }$ also satisfies (1). This problem has many applications, such as biclustering for genes, recommendation of similar groups, collaboration in communities, etc. However, it is computationally challenging due to its #P-completeness. Besides, we prove that even determining the maximality of a $\theta$ -biclique is NP-hard. To the best of our knowledge, there is no efficient and scalable solution to this problem in the literature. In this paper, we first propose a branch-and-bound framework, namely ${\sf MSiBE}$ , which enumerates all maximal $\theta$ -bicliques in a depth-first manner. Then, we develop three effective optimizations to improve the performance of ${\sf MSiBE}$ . (1) The local information of each search space is utilized to enhance the pruning capacity. (2) When expanding the partial biclique, we always focus on the side with fewer candidates first, by which fruitless search branches can be skipped early. (3) We implement ${\sf MSiBE}$ with efficient array reordering techniques and set intersection strategy. To further accelerate the computation, we introduce useful graph reduction techniques. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by up to 3 orders of magnitude.

Computing Multi-source Shortest Path query with Assembly points (MSPA) is a fundamental graph problem. The MSPA problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the MSPA problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.