Source-linked AI summary
Detection and Construction of Small Blocking Sets via Critical Independent Sets and Matching Decomposition
Quanlong Niu, Riheng Jia
TL;DR
Small blocking set detection was left as an open complexity question despite its connection to restless exploration in vertex-permuted temporal graphs. The paper gives a polynomial-time detection and construction algorithm, reducing the balanced boundary case to a strong-connectivity test. A sink strongly connected component supplies a small blocking set when the auxiliary digraph is not strongly connected.
Problem
Prior work left open the complexity of detecting a small blocking set, which characterizes restless exploration in vertex-permuted temporal graphs for sufficiently long lifetimes.
Source: §1 · p. 3Method
The algorithm classifies a maximum-cardinality critical independent set and reduces the balanced case to a tight-subset test represented by an auxiliary digraph.
Source: §1 · p. 3, §4.2 · p. 7Results
The graph contains a small blocking set exactly when the auxiliary digraph is not strongly connected, and a sink strongly connected component yields one.
Source: §5.1 · pp. 10–11Takeaways & Limitations
The result resolves the open detection-complexity question with a polynomial-time algorithm that also constructs a small blocking set when one exists.
Source: §1 · p. 3The empty-set branch relies on a maximum-cardinality critical independent set; an arbitrary critical independent set may be empty even when a nonempty blocking set exists.
Source: §3.2 · p. 6
Abstract
from arXiv · showhide
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.
1. Introduction
Prior work connected small blocking sets to restless exploration in vertex-permuted temporal graphs, but left detection complexity open. This paper gives a polynomial-time detection and construction algorithm.
1. Introduction
- Temporal exploration research studies how changing topology and restrictions on waiting affect exploration, including period-dependent complexity results for restless exploration.For infinite periodic temporal graphs, the problem is polynomial-time solvable at period two and NP-hard at every fixed period of at least three.Source: §1 · p. 2
- For sufficiently long lifetimes, a vertex-permuted temporal graph based on a connected graph admits restless exploration exactly when its base graph has no blocking set smaller than half its vertices.The prior work left the complexity of detecting such a set open; direct subset enumeration can require exponentially many candidates.Source: §1 · pp. 2–3
- A polynomial-time algorithm detects and constructs small blocking sets, using critical-independent-set classification and a matching-based test in the boundary case.The boundary test uses strong connectivity in an auxiliary digraph; a sink strongly connected component yields a set when one exists.Source: §1 · p. 3
2. Problem formulation
The paper frames small blocking set detection as finding an independent set with a specified cardinality relationship to its neighborhood, or determining that none exists. It uses critical independent sets to approach the detection and construction problem.
2. Problem formulation
- For lifetime L ≥ n(n−1), restless exploration from every starting vertex in every vertex-permuted temporal graph based on G is equivalent to G having no small blocking set.If G contains one, a permutation sequence and starting vertex can be constructed for which the temporal graph admits no restless exploration.Source: §2 · p. 4
- The target is a nonempty independent set whose neighborhood has a specified cardinality relationship to it, with a strict size bound as part of the small-blocking-set condition.The supplied formulation introduces the neighborhood N(S), but does not include the full displayed condition.Source: §2 · p. 4
- The approach starts from a maximum-cardinality critical independent set computed in polynomial time, then classifies cases by its difference and cardinality.The cited algorithm for computing that set is due to Larson [11].Source: §2 · p. 5
3. Classification using critical independent sets
A maximum-cardinality critical independent set is classified by its difference and size. Positive difference yields a small blocking set, while zero difference leaves an immediate answer except when the set has exactly half the vertices.
3. Classification using critical independent sets
- The algorithm computes a maximum-cardinality critical independent set and separates the cases δ > 0 and δ = 0.This classification is the framework for the positive-difference and zero-difference branches.Source: §3 · p. 5
3.1. Positive critical difference
- For δ > 0, deleting vertices from I yields a blocking set S with |S| ≤ |N(I)|, and the bounds make S small.The proof uses |I| + |N(I)| ≤ n and |I| > |N(I)| to establish the strict half-size bound.Source: §3.1 · pp. 5–6
3.2. Zero critical difference
- For δ = 0, an empty I certifies no nonempty blocking set, a nonempty I smaller than n/2 is itself small, and only |I| = n/2 remains.The nonempty smaller set has |I| = |N(I)| because its difference is zero.Source: §3.2 · p. 6
- The maximum-cardinality requirement supports the empty-set branch; an arbitrary critical independent set may be empty even when a nonempty blocking set exists.Thus the empty output of a subroutine computing an arbitrary critical independent set would not justify concluding that no blocking set exists.Source: §3.2 · p. 6
4. Boundary structure and the projection theorem
In the boundary case, a perfect matching supports a projection theorem: a small blocking set exists exactly when the selected independent set contains a nonempty proper tight subset. Thus, detection in this case can be restricted to subsets of that independent set.
4.1. Boundary structure
- In the boundary case, the bipartite graph between I and its complement J has a perfect matching.The zero critical difference gives |N(X)| ≥ |X| for every X ⊆ I; since |I| = |J|, Hall’s condition yields a perfect matching.Source: §4.1 · p. 7
4.2. Projection of small blocking sets
- A small blocking set exists if and only if the selected independent set contains a nonempty proper subset T with |T| = |N(T)|.Such a subset is called tight; the theorem reduces the graph-level question to finding one within I.Source: §4.2 · p. 7
- If a small blocking set intersects I, its intersection with I is a nonempty proper tight subset.Taking T = S ∩ I gives |N(T)| = |T|, and T ⊊ I.Source: §4.2 · p. 8
- If a small blocking set lies in J, the matching argument yields a nonempty proper tight subset T = I \ C.The argument identifies N(T) with J \ S, then uses |I| = |J| to establish |N(T)| = |T| and the strict size bound.Source: §4.2 · pp. 8–9
- The projection theorem means that in this boundary case it suffices to detect and construct a small blocking set within I.Any nonempty proper tight subset of I is itself a small blocking set.Source: §4.2 · p. 9
5. Algorithm design and analysis
The algorithm handles immediate cases using a maximum-cardinality critical independent set, then reduces the balanced boundary case to a strong-connectivity test. A sink strongly connected component constructs a small blocking set, and the full algorithm runs in O(m^2) time.
5.1. Constructing a small blocking set within a maximum-cardinality critical independent set
- In the balanced boundary case, matching contraction turns tight subsets of I into vertex subsets of DM with no outgoing arcs, so G has a small blocking set iff DM is not strongly connected.The test is independent of the chosen perfect matching.Source: §5.1 · pp. 9–11
- Any sink strongly connected component C yields a small blocking set TC = {xi : i ∈C}.Its vertices are a nonempty proper subset of I, which is independent and has an equal-sized neighborhood.Source: §5.1 · pp. 10–11
5.2. Algorithmic framework
- The algorithm classifies cases by the critical difference δ and |I|, returning an immediate set when possible and using matching and SCCs when δ = 0 and |I| = n/2.If DM is strongly connected in the boundary case, it returns NO; otherwise it selects a sink SCC.Source: §5.2 · pp. 11–12
5.3. Correctness
- Theorem 5 establishes that every branch correctly decides whether a small blocking set exists and constructs one whenever it does.For the boundary case, the decision follows from the equivalence between a small blocking set and DM not being strongly connected.Source: §5.3 · p. 12
5.4. Running time
- The overall running time is O(m^2) for connected graphs.The maximum-cardinality critical independent set computation takes O(m^2); the other stages are no slower.Source: §5.4 · pp. 12–13
6. Conclusions and future work
The paper presents an O(m^2)-time algorithm for detecting and constructing small blocking sets. It also identifies graph repair and permutation-specific restless exploration as directions for future work.
6. Conclusions and future work
- The algorithm combines critical-independent-set classification with a matching-based strong-connectivity test and runs in O(m^2) time.In the balanced boundary case, a sink SCC supplies a small blocking set.Source: §6 · p. 13
- One future direction is finding the minimum number of edges to add to eliminate all small blocking sets and ensure universal restless explorability for sufficiently long lifetimes.The paper frames this as base-graph repair.Source: §6 · p. 13
- Another direction is deciding feasibility and constructing schedules for a given permutation sequence, including when the base graph lacks the universal-explorability condition.Source: §6 · p. 13