Algorithms and Time Complexity of the Request-Service Problem

Given a number of users each of which provides a set of services with a cost for each service and has a set of requests to be satisfied, the goal of the request-service problem is to find a feasible solution that satisfies all requests of each user with minimum cost. In addition, a feasible solution must satisfy an additional constraint. Specifically, if user A provides a service to user B, B should provide a service back to A either directly or indirectly through other users. In this paper, we studied the complexity of this problem. We show that there exists a polynomial time algorithm that can compute a feasible solution with minimum cost if such a solution exists. However, if a feasible solution does not exist, the problem of maximizing the number of satisfied users (i.e., all requests of the users are satisfied) is NP-hard.