Graph theory objects | Computational problems in graph theory
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. The computational problem of finding the largest nonblocker in a graph was formulated by , who observed that it belongs to MaxSNP.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. In graphs with no isolated vertices, every maximal nonblocker (one to which no more vertices can be added) is itself a dominating set. (Wikipedia).
