Title: The Minimal Feature Removal Problem in Neural Networks. Abstract: We present the \emph{minimal feature removal problem} for neural networks, a combinatorial problem which has interesting potential applications for improving interpretability and robustness of neural network predictions. For a given input to a trained neural network, our aim is to compute a smallest set of input features so that the model prediction changes when these features are disregarded by setting them to a given uninformative baseline value. While computing such minimal subsets of features is computationally intractable in general for fully-connected neural networks, we show that the problem becomes solvable in polynomial time by a greedy algorithm under mild assumptions on the network's activation functions.  We then show that our tractability result extends seamlessly to more advanced neural network architectures such as  convolutional and graph neural networks. Our experiments on standard datasets show favourable performance of our greedy algorithm in practice.