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

edit

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   and a parameter  , and the goal is to determine whether   has a nonblocker with   or more vertices.[1]

This problem has an easy kernelization that reduces it to an equivalent problem with at most   vertices. First, remove all isolated vertices from  , 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   or more vertices, the problem can be solved immediately. Otherwise, the remaining graph is a kernel with at most   vertices.[1]

Dehne et al. improved this to a kernel of size at most  . 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  , which can be handled separately) this instance must either be smaller than the kernel size bound or contain a  -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  . Even faster algorithms are possible for certain special classes of graphs.[1]

See also

edit

References

edit
  1. ^ a b c d e f 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, vol. 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, vol. 38, Providence, R.I.: American Mathematical Society, Theorem 13.1.5, p. 207, MR 0150753