Methods, systems, and computer-readable media for analysis of role reachability using policy complements are disclosed. An access control analyzer determines two nodes in a graph that potentially have a common edge. The nodes correspond to roles in a provider network, and the roles are associated with first and second access control policies that grant or deny access to resources. The access control analyzer performs a role reachability analysis that determines whether the first role can assume the second role for a particular state of one or more key-value tags. The role reachability analysis determines a third access control policy authorizing a negation of a role assumption request for the second role. The role reachability analysis performs analysis of the third access control policy with respect to a role assumption policy for the second role for the particular state of the one or more key-value tags.