  Bottom-up role-mining is the determination of a set of roles given as input a
set of users and the permissions those users possess. It is well-established in
the research literature, and in practice, as an important problem in
information security. A natural objective that has been explored in prior work
is for the set of roles to be of minimum size. We address this problem for
practical inputs while reconciling foundations, specifically, that the problem
is \cnph. We first observe that an approach from prior work that exploits a
sufficient condition for an efficient algorithm, while a useful first step,
does not scale to more recently proposed benchmark inputs. We propose a new
technique: the enumeration of maximal bicliques. We point out that the number
of maximal bicliques provides a natural measure of the hardness of an input. We
leverage the enumeration of maximal bicliques in two different ways. Our first
approach addresses more than half the benchmark inputs to yield exact results.
The other approach is needed for hard instances; in it, we identify and adopt
as roles those that correspond to large maximal bicliques. We have implemented
all our algorithms and carried out an extensive empirical assessment, which
suggests that our approaches are promising. Our code is available publicly as
open-source.
