Lesson plan
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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.