Parameterized complexity of submodular minimization under uncertainty

Kakimura, Naonori and Schlotter, Ildikó Anna (2026) Parameterized complexity of submodular minimization under uncertainty. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 160. No. -103796. ISSN 0022-0000

Preview

Text 1-s2.0-S0022000026000425-main.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview

Abstract

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 f1,..., fk 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 fi in the sense that some minimizer of fi can be obtained from X by adding/removing at most d elements for a given integer d ∈ N. 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. We also show that if some submodular function fi has a polynomial number of minimizers, then the problem becomes fixedparameter tractable when parameterized by d. On the other hand, the problem remains W[1]-hard parameterized by k even if each function fi has at most |V| minimizers. We remark that all our hardness results hold even if each submodular function is given by a cut function of a directed graph.

Actions (login required)

Edit Item