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 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]
The white vertex sets are maximal nonblockers
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 G and a parameter k, and the goal is to determine whether G has a nonblocker with k or more vertices.[1]
This problem has an easy kernelization that reduces it to an equivalent problem with at most } 2k vertices. First, remove all isolated vertices from 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 2k or more vertices, the problem can be solved immediately. Otherwise, the remaining graph is a kernel with at most 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 k {\displaystyle k} k, which can be handled separately) this instance must either be smaller than the kernel size bound or contain a k {\displaystyle k} 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
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
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
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
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
