Parameterized Complexity of Submodular Minimization under Uncertainty
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929439375360000 |
|---|---|
| author | Kakimura, Naonori Schlotter, Ildikó |
| author_facet | Kakimura, Naonori Schlotter, Ildikó |
| contents | 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,\dots,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 \subseteq V$ that is close to \emph{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 \in \mathbb{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: (1) Robust Submodular Minimizer can be solved in polynomial time when $k \leq 2$, but is NP-hard if $k$ is a constant with $k \geq 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 \geq 1$. (3) 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$. On the other hand, the problem remains $\mathsf{W}[1]$-hard parameterized by $k$ even if each function $f_i$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07516 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of Submodular Minimization under Uncertainty Kakimura, Naonori Schlotter, Ildikó Data Structures and Algorithms Discrete Mathematics 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,\dots,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 \subseteq V$ that is close to \emph{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 \in \mathbb{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: (1) Robust Submodular Minimizer can be solved in polynomial time when $k \leq 2$, but is NP-hard if $k$ is a constant with $k \geq 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 \geq 1$. (3) 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$. On the other hand, the problem remains $\mathsf{W}[1]$-hard parameterized by $k$ even if each function $f_i$ 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. |
| title | Parameterized Complexity of Submodular Minimization under Uncertainty |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2404.07516 |