Graph downsizing: a fast heuristic for querying closely connected subgraphs
Open Access
- 20 February 2026
- journal article
- research article
- Published by Springer Nature in Journal of Heuristics
- Vol. 32 (1) , 9
Abstract
The vertex connectivity of a graph is the minimum number of vertices whose removal disconnects the graph, and it is a fundamental notion that measures the level of interconnectedness of vertices. Mining subgraphs with high vertex connectivity has wide applications in robust and efficient communication networks and the organization of task groups. However, existing approaches often neglect size constraints, leading to subgraphs that are either too large or too small for practical use. Therefore, in this paper, we introduce the size constraint and formulate the graph downsizing problem: Given a graph G with n vertices and a positive integer $$\tau <n$$ , find an induced subgraph of size $$n-\tau $$ that maximizes vertex connectivity. We first analyze the computational complexity of the graph downsizing problem and show that the problem is hard in several aspects. To solve the problem in practice, we use a nesting tree structure to represent relations between maximal cohesive subgraphs in G . This structure allows us to develop an efficient heuristic, called inundation downsizing algorithm, to find highly vertex-connected subgraphs of different sizes. Experimental results reveal that our heuristic is able to produce almost optimal solutions on real-world datasets with up to 1 million vertices while incurring small time costs.
Keywords
Funding Information
- Chinese Government Scholarship (201906030067)
- University of Auckland
This publication has 32 references indexed in Scilit:
- A method for routing and data aggregating in cluster‐based wireless sensor networksInternational Journal of Communication Systems, 2021
- Towards k-vertex connected component discovery from large networksWorld Wide Web, 2019
- Who Should Be Invited to My Party: A Size-Constrained k-Core Problem in Social NetworksJournal of Computer Science and Technology, 2019
- Effective k-Vertex Connected Component Detection in Large-Scale Networks2017
- Graph Theory2017
- Environmental parameters monitoring in precision agriculture using wireless sensor networksJournal of Cleaner Production, 2015
- Wireless Sensor Networks Framework for Water Resource Management that Supports QoS in the Kingdom of Saudi ArabiaProcedia Computer Science, 2013
- A Linear Time Implementation of SPQR-Trees2001
- Finding and counting given length cyclesAlgorithmica, 1997
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995