2026-08-03T04:36:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20070 2024-05-31T13:11:12Z ddc:004 open_access

Parameterized Complexity of Submodular Minimization Under Uncertainty Kakimura, Naonori Schlotter, Ildikó Submodular minimization optimization under uncertainty parameterized complexity cut function 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_1,… ,f_k over a set family 2^V, 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_i in the sense that some minimizer of f_i 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: - Robust Submodular Minimizer can be solved in polynomial time when k ≤ 2, but is NP-hard if k is a constant with k ≥ 3. - Robust Submodular Minimizer can be solved in polynomial time when d = 0, but is NP-hard if d is a constant with d ≥ 1. - Robust Submodular Minimizer is fixed-parameter tractable when parameterized by (k,d). We also show that if some submodular function f_i 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Naonori Kakimura and Ildikó Schlotter 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.30 urn:nbn:de:0030-drops-200702 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode