Nonblocker

In graph theory, a nonblocker is a subset of vertices in an undirected graph, all of which are adjacent to vertices outside of the subset. Equivalently, a nonblocker is the complement of a dominating set.[1]

The white vertex sets are maximal nonblockers

The computational problem of finding the largest nonblocker in a graph was formulated by Papadimitriou & Yannakakis (1991), who observed that it belongs to MaxSNP.[2] Although computing a dominating set is not fixed-parameter tractable under standard assumptions, the complementary problem of finding a nonblocker of a given size is fixed-parameter tractable.[1]

In graphs with no isolated vertices, every maximal nonblocker (one to which no more vertices can be added) is itself a dominating set.[3]

Kernelization

One way to construct a fixed-parameter tractable algorithm for the nonblocker problem is to use kernelization, an algorithmic design principle in which a polynomial-time algorithm is used to reduce a larger problem instance to an equivalent instance whose size is bounded by a function of the parameter. For the nonblocker problem, an input to the problem consists of a graph ${\displaystyle G}$ and a parameter ${\displaystyle k}$, and the goal is to determine whether ${\displaystyle G}$ has a nonblocker with ${\displaystyle k}$ or more vertices.[1]

This problem has an easy kernelization that reduces it to an equivalent problem with at most ${\displaystyle 2k}$ vertices. First, remove all isolated vertices from ${\displaystyle G}$, as they cannot be part of any nonblocker. Once this has been done, the remaining graph must have a nonblocker that includes at least half of its vertices; for instance, if one 2-colors any spanning tree of the graph, each color class is a nonblocker and one of the two color classes includes at least half the vertices. Therefore, if the graph with isolated vertices removed still has ${\displaystyle 2k}$ or more vertices, the problem can be solved immediately. Otherwise, the remaining graph is a kernel with at most ${\displaystyle 2k}$ vertices.[1]

Dehne et al. improved this to a kernel of size at most ${\displaystyle {\tfrac {5}{3}}k+3}$. Their method involves merging pairs of neighbors of degree-one vertices until all such vertices have a single neighbor, and removing all but one of the degree-one vertices, leaving an equivalent instance with only one degree-one vertex. Then, they show that (except for small values of ${\displaystyle k}$, which can be handled separately) this instance must either be smaller than the kernel size bound or contain a ${\displaystyle k}$-vertex blocker.[1]

Once a small kernel has been obtained, an instance of the nonblocker problem may be solved in fixed-parameter tractable time by applying a brute-force search algorithm to the kernel. Applying faster (but still exponential) time bounds leads to a time bound for the nonblocker problem of the form ${\displaystyle O(2.5154^{k}+n)}$. Even faster algorithms are possible for certain special classes of graphs.[1]

References

1. Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena; Rosamond, Frances (2006), "Nonblocker: Parameterized algorithmics for minimum dominating set" (PDF), SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 21-27, 2006, Proceedings, Lecture Notes in Computer Science, 3831, Springer, pp. 237–245, doi:10.1007/11611257_21
2. Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), "Optimization, approximation, and complexity classes", Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X, MR 1135471
3. Ore, Øystein (1962), Theory of graphs, American Mathematical Society Colloquium Publications, 38, Providence, R.I.: American Mathematical Society, Theorem 13.1.5, p. 207, MR 0150753