In this paper, we study the Robust Minimal Controllability and Observability Problem (rMCOP). The scenario that motivated this question is related to the design of a drone formation to execute some task, where the decision of which nodes to equip with a more expensive communication system represents a critical economic choice. Given a linear time-invariant system for each of the vehicles, this problem consists of identifying a minimal subset of state variables to be actuated and measured, ensuring that the overall formation model is both controllable and observable while tolerating a prescribed level of inputs/outputs that can fail. Based on the tools in the available literature, a naive approach would consist of enumerating separately all possible minimal solutions for the controllability and observability parts. Then, iterating over all combinations to find the maximum intersection of sensors/actuators in the independent solutions, yielding a combinatorial problem. The presented solution couples the design of both controllability and observability parts through a polynomial reformulation as a minimum set multi-covering problem under some mild assumptions. In this format, the algorithm has the following interesting attributes: (i) only requires the solution of a single covering problem; 9ii) using polynomial approximations algorithms, one can obtain close-to-optimal solutions to the rMCOP.