  We discuss the problem of finding critical sets in graphs, a concept which
has appeared in a number of guises in the combinatorics and graph theory
literature. The case of the Sudoku graph receives particular attention, because
critical sets correspond to minimal fair puzzles. We define four parameters
associated with the sizes of extremal critical sets and (a) prove several
general results about these parameters' properties, including their
computational intractability, (b) compute their values exactly for some classes
of graphs, (c) obtain bounds for generalized Sudoku graphs, and (d) offer a
number of open questions regarding critical sets and the aforementioned
parameters.
