Nonblocker

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.

[3] 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.

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.

[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.

, which can be handled separately) this instance must either be smaller than the kernel size bound or contain a

[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.