Relationship-Based Access Control (ReBAC) expresses authorization in terms of various direct and indirect relationships amongst entities, most commonly between users. The need for ReBAC policy mining arises when an existing access control system is reformulated in ReBAC. This paper considers the feasibility of ReBAC policy mining in context of user to user authorization, such as arises in various social and business contexts. In accordance with the policy mining literature, we assume that complete data is provided regarding user to user authorizations for a given user set, along with complete relationship data amongst these users comprising a labeled relationship graph. A ReBAC policy language is also specified. ReBAC policy mining seeks to formulate a ReBAC policy with the given policy language and relationship graph, which is exactly equivalent to the given authorizations. ReBAC policy mining feasibility problem asks whether such a policy exists and if so to provide the policy. We investigate this problem in context of different ReBAC policy languages which differ in the relationships, inverse relationships and non-relationships that can be used to build the policy. We develop a feasibility detection algorithm and analyze its complexity. We show that our policy languages are progressively more expressive as we introduce additional capability. In case of infeasibility, various solution approaches are discussed.