In the maximal independent set listing problem, the input is an undirected graph, and the output is a list of all its maximal independent sets. The maximum independent set problem may be solved using as a subroutine an algorithm for the maximal independent set listing problem, because the maximum independent set must be included among all the maximal independent sets. In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.