Search Results

Documents authored by Schlotter, Ildikó

Document
DOI: 10.4230/LIPIcs.SWAT.2024.30
Parameterized Complexity of Submodular Minimization Under Uncertainty

Authors: Naonori Kakimura and Ildikó Schlotter

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

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 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.
Cite as

Naonori Kakimura and Ildikó Schlotter. Parameterized Complexity of Submodular Minimization Under Uncertainty. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kakimura_et_al:LIPIcs.SWAT.2024.30,
  author =	{Kakimura, Naonori and Schlotter, Ildik\'{o}},
  title =	{{Parameterized Complexity of Submodular Minimization Under Uncertainty}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.30},
  URN =		{urn:nbn:de:0030-drops-200702},
  doi =		{10.4230/LIPIcs.SWAT.2024.30},
  annote =	{Keywords: Submodular minimization, optimization under uncertainty, parameterized complexity, cut function}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.57
Shortest Two Disjoint Paths in Conservative Graphs

Authors: Ildikó Schlotter

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = (V,E) with edge weights w:E → ℝ, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G.
Cite as

Ildikó Schlotter. Shortest Two Disjoint Paths in Conservative Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schlotter:LIPIcs.STACS.2024.57,
  author =	{Schlotter, Ildik\'{o}},
  title =	{{Shortest Two Disjoint Paths in Conservative Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.57},
  URN =		{urn:nbn:de:0030-drops-197678},
  doi =		{10.4230/LIPIcs.STACS.2024.57},
  annote =	{Keywords: Shortest paths, disjoint paths, conservative weights, graph algorithm}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact