Polynomial algorithm finds small blocking sets in graphs
Detection and Construction of Small Blocking Sets via Critical Independent Sets and Matching Decomposition
Discrete Mathematics
Summary
Sometimes, it’s useful to find a special group of points in a network where the number of points matches exactly the number of their immediate neighbors, and this group is smaller than half the entire network. The authors solved a long-standing question about how hard it is to find such groups in any connected network by creating a step-by-step recipe (algorithm) that runs quickly. They use techniques involving special independent groups and matching of connections to either find the group or decide one doesn't exist. This helps in problems related to exploring networks over time.
What this means in practice
- •For network analysts: Check connectivity and identify critical subgroups in changing networks fast using the new detection and construction algorithm for small blocking sets.
- •For graph algorithm engineers: Use the matching contraction and strong-connectivity test technique to build efficient tools for network structure analysis and optimization.
Authors
Quanlong Niu, Riheng Jia
Abstract
The small blocking set detection and construction problem asks whether a given connected simple graph contains a nonempty independent set whose cardinality equals the size of its neighborhood and is strictly less than half the number of vertices, and, if so, how to construct such a set. Previous work characterized restless explorability in vertex-permuted temporal graphs using small blocking sets, but left the computational complexity of detecting their existence as an open problem. We give a polynomial-time algorithm for detection and construction. Specifically, we first compute a maximum-cardinality critical independent set and use its difference and cardinality to handle the cases that admit an immediate solution. In the remaining boundary case, where the critical difference is zero and the selected independent set contains exactly half the vertices, we establish a projection theorem using a perfect matching and neighborhood counting: the graph contains a small blocking set if and only if the selected independent set contains a nonempty proper tight subset. We then use matching contraction to translate the tight-subset condition into the absence of arcs leaving a vertex subset in an auxiliary digraph. This yields a strong-connectivity test for the existence of a small blocking set and, when one exists, a construction based on a sink strongly connected component. The result resolves the open complexity question for small blocking set detection and provides an explicit construction algorithm.