Kakimura, Naonori and Schlotter, Ildikó Anna (2024) Parameterized Complexity of Submodular Minimization Under Uncertainty. In: 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs) (294). Leibniz-Zentrum für Informatik, Wadern, 30:1-30:17. ISBN 9783959773188
|
Text
LIPIcs.SWAT.2024.30.pdf - Published Version Available under License Creative Commons Attribution. Download (901kB) | 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 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 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: 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 fi 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.
Item Type: | Book Section |
---|---|
Uncontrolled Keywords: | Submodular minimization, optimization under uncertainty, parameterized complexity, cut function |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 03 Jun 2024 06:37 |
Last Modified: | 10 Sep 2024 07:09 |
URI: | https://real.mtak.hu/id/eprint/196369 |
Actions (login required)
![]() |
Edit Item |