  A simple greedy algorithm to find a maximal independent set (MIS) in a graph
starts with the empty set and visits every vertex, adding it to the set if and
only if none of its neighbours are already in the set. In this paper, we
consider the generalisation of this MIS algorithm by letting it start with any
set of vertices and we prove the hardness of many decision problems related to
this generalisation. Our results are based on two main strategies. Firstly, we
view the MIS algorithm as a sequential update of a Boolean network, which we
refer to as the MIS network, according to a permutation of the vertex set. The
set of fixed points of the MIS network corresponds to the set of MIS of the
graph. Our generalisation then consists in starting from any configuration and
following a sequential update given by a word of vertices. Secondly, we
introduce the concept of a colony of a graph, that is a set of vertices that is
dominated by an independent set. Deciding whether a set of vertices is a colony
is NP-complete; decision problems related to the MIS algorithm will be reduced
from the Colony problem. We first show that deciding whether a configuration
can reach all maximal independent sets is coNP-complete. Second, we consider
so-called fixing words, that allow to reach a MIS for any initial
configuration, and fixing permutations, which we call permises; deciding
whether a permutation is fixing is coNP-complete. Third, we show that deciding
whether a graph has a permis is coNP-hard. Finally, we generalise the MIS
algorithm to digraphs. The algorithm then uses the so-called kernel network,
whose fixed points are the kernels of the digraph. Deciding whether the kernel
network of a given digraph is fixable is coNP-hard, even for digraphs that have
a kernel. Alternatively, we introduce two fixable Boolean networks whose sets
of fixed points contain all kernels.
