graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a nonblocker is a subset of vertices in an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

, all of which are adjacent to vertices outside of the subset. Equivalently, a nonblocker is the

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...

of a

dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set ...

. The computational problem of finding the largest nonblocker in a graph was formulated by , who observed that it belongs to

MaxSNP In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class Max ...

. Although computing a dominating set is not

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

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.

Kernelization

One way to construct a fixed-parameter tractable algorithm for the nonblocker problem is to use

kernelization In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solvi ...

, 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. 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 In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

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. Dehne et al. improved this to a kernel of size at most

\tfrack+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

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

k

-vertex blocker. 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 In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

algorithm to the kernel. Applying faster (but still exponential) time bounds leads to a time bound for the nonblocker problem of the form

O(2.5154^k+n)

. Even faster algorithms are possible for certain special classes of graphs.

References

{{reflist, 30em, refs= {{citation , last1 = Dehne , first1 = Frank , last2 = Fellows , first2 = Michael , last3 = Fernau , first3 = Henning , last4 = Prieto , first4 = Elena , author4-link = Elena Prieto-Rodriguez , last5 = Rosamond , first5 = Frances , contribution = Nonblocker: Parameterized algorithmics for minimum dominating set , contribution-url = http://www.informatik.uni-trier.de/~fernau/papers/Dehetal06.pdf , doi = 10.1007/11611257_21 , pages = 237–245 , publisher = Springer , series = Lecture Notes in Computer Science , title = SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 21-27, 2006, Proceedings , volume = 3831 , year = 2006 {{citation , last = Ore , first = Øystein , authorlink = Øystein Ore , location = Providence, R.I. , mr = 0150753 , at = Theorem 13.1.5, p. 207 , publisher = American Mathematical Society , series = American Mathematical Society Colloquium Publications , title = Theory of graphs , url = https://books.google.com/books?id=Pf-VAwAAQBAJ&pg=PA207 , volume = 38 , year = 1962 {{citation , last1 = Papadimitriou , first1 = Christos H. , author1-link = Christos Papadimitriou , last2 = Yannakakis , first2 = Mihalis , author2-link = Mihalis Yannakakis , doi = 10.1016/0022-0000(91)90023-X , issue = 3 , journal =

Journal of Computer and System Sciences The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been publishe ...

, mr = 1135471 , pages = 425–440 , title = Optimization, approximation, and complexity classes , volume = 43 , year = 1991, doi-access = free Graph theory objects Computational problems in graph theory

Kernelization

See also

References