A typical goal of research in combinatorial optimization is to come up with fast algorithms that find optimal solutions to a computational problem. The process that takes a real-world problem and extracts a clean mathematical abstraction of it often throws out a lot of “side information” which is deemed irrelevant. However, the discarded information could be of real significance to the end-user of the algorithm’s output. All solutions of the same cost are not necessarily of equal impact in the real-world; some solutions may be much more desirable than others, even at the expense of additional increase in cost. If the impact, positive or negative, is mostly felt by some specific (minority) subgroups of the population, the population at large will be largely unaware of it. In this work we ask the question of finding solutions to combinatorial optimization problems that are “unbiased” with respect to a collection of specified subgroups of the total population. We consider a simple model of bias, and study it via two basic optimization problems on graphs: Vertex Cover and Feedback Vertex Set, which are both NP-hard. Here, the input is a graph and the solution is a subset of the vertex set. The vertices represent members of a population, and each vertex has been assigned a subset of colors, where each color indicates membership of a specific subgroup. The goal is to find a small-sized solution to the optimization problem in which no color appears more than a specified—per-color—number of times. The colors can be used to model various relevant—economic, political, demographic, or other—classes to which the entities belong, and the variants that we study can then be used to look for small solutions which enforce per-class upper bounds on the number of removed entities. These upper-bounds enforce the constraint that no subclass of the population is over-represented in the solution. We show the new variants of Vertex Cover and Feedback Vertex Set, obtained by adding these additional constraints, are Fixed-Parameter Tractable, when parameterized by various combinations of the solution size, the number of colors, and the treewidth of the graph. Our results shows that it is possible to devise fast algorithms to solve these problem in many practical settings.