Parameterized Complexity of Submodular Minimization under Uncertainty

This paper studies the computational complexity of a robust variant of a two-stage submodular minimization problem that we call Robust Submodular Minimizer. In this problem, we are given k submodular functions f₁,,fₖ over a set family 2V, which represent k possible scenarios in the future when we will need to find an optimal solution for one of these scenarios, i.e., a minimizer for one of the functions. The present task is to find a set X ⊆ V that is close to some optimal solution for each fᵢ in the sense that some minimizer of fᵢ can be obtained from X by adding/removing at most d elements for a given integer d. The main contribution of this paper is to provide a complete computational map of this problem with respect to parameters k and d, which reveals a tight complexity threshold for both parameters: (1) Robust Submodular Minimizer can be solved in polynomial time when k ≤ 2, but is NP-hard if k is a constant with k ≥ 3. (2) Robust Submodular Minimizer can be solved in polynomial time when $d=0$, but is NP-hard if d is a constant with d ≥ 1. (3) Robust Submodular Minimizer is fixed-parameter tractable when parameterized by $(k,d)$. We also show that if some submodular function fᵢ has a polynomial number of minimizers, then the problem becomes fixed-parameter tractable when parameterized by d. We remark that all our hardness results hold even if each submodular function is given by a cut function of a directed graph.