Future communication systems are complex infrastructures with virtualized software services that are updated regularly as requirements evolve. This paper addresses the adaptation of microservices under dependency and efficiency constraints. We formalize the evolution of microservices as a combination of two subproblems, the Microservice Dependency Problem and the Evolution Planning Problem, both of which are difficult to solve optimally. We then propose a method based on the Binate Covering Problem (BCP) with branch-and-bound, and introduce a novel algorithm that finds the deployment steps towards a desired new configuration. Our proposed method, DEP-DS, is then compared with two heuristics on three sample datasets from historical radio access network update records run on Kubernetes. We further show that BCP with greedy search is faster but finds fewer solutions to the evolution plan. Overall, DEP-DS is able to find solutions to all samples, generates deployment plans within an average time of 1–2 s, and the plans are similar to other heuristics in terms of CPU usage.