6 Search Results for "Lendl, Stefan"

Document
DOI: 10.4230/LIPIcs.WADS.2025.36
On the Complexity of Minimising the Moving Distance for Dispersing Objects

Authors: Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, and Hirotaka Ono

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We study Geometric Graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We first show an O(n log n)-time algorithm that minimises the total moving distance to disperse unit intervals. This algorithm is applied to render a given unit interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. We next show that GGED becomes strongly NP-hard when rendering a weighted interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. Lastly, we prove that minimising the maximum moving distance for rendering a unit disk graph edgeless is strongly NP-hard over the L₁ and L₂ distances.
Cite as

Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, and Hirotaka Ono. On the Complexity of Minimising the Moving Distance for Dispersing Objects. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{honoratodroguett_et_al:LIPIcs.WADS.2025.36,
  author =	{Honorato-Droguett, Nicol\'{a}s and Kurita, Kazuhiro and Hanaka, Tesshu and Ono, Hirotaka},
  title =	{{On the Complexity of Minimising the Moving Distance for Dispersing Objects}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.36},
  URN =		{urn:nbn:de:0030-drops-242673},
  doi =		{10.4230/LIPIcs.WADS.2025.36},
  annote =	{Keywords: Intersection graphs, Optimisation, Graph modification}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.52
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy

Authors: Christoph Grüne and Lasse Wulf

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become Σ^p₃-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP = Σ^p₃ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, p-center, p-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, k-directed disjoint path (k ≥ 2), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes Σ^p₃-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is Σ^p₃-complete. This reveals the insight that all the above problems are Σ^p₃-complete "for the same reason". Our result extends a recent framework by Grüne and Wulf.
Cite as

Christoph Grüne and Lasse Wulf. On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grune_et_al:LIPIcs.MFCS.2025.52,
  author =	{Gr\"{u}ne, Christoph and Wulf, Lasse},
  title =	{{On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.52},
  URN =		{urn:nbn:de:0030-drops-241596},
  doi =		{10.4230/LIPIcs.MFCS.2025.52},
  annote =	{Keywords: Complexity, Robust Optimization, Recoverable Robust Optimization, Two-Stage Problems, Polynomial Hierarchy, Sigma 2, Sigma 3}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.44
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

Authors: Tim A. Hartmann and Dániel Marx

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these problems are well understood on bounded-treewidth graphs [Katsikarelis, Lampis, and Paschos, Discret. Appl. Math 2022][Borradaile and Le, IPEC 2016]: given a tree decomposition of width t, the two problems can be solved in time d^t⋅ n^O(1) and (2d+1)^t⋅ n^O(1), respectively. Furthermore, assuming the Strong Exponential-Time Hypothesis (SETH), the base constants are best possible in these running times: they cannot be improved to d-ε and 2d+1-ε, respectively, for any ε > 0. We investigate continuous versions of these problems in a setting introduced by Megiddo and Tamir [SICOMP 1983], where every edge is modeled by a unit-length interval of points. In the δ-Dispersion problem, the task is to find a maximum number of points (possibly inside edges) that are pairwise at distance at least δ from each other. Similarly, in the δ-Covering problem, the task is to find a minimum number of points (possibly inside edges) such that every point of the graph (including those inside edges) is at distance at most δ from the selected point set. We provide a comprehensive understanding of these two problems on bounded-treewidth graphs. 1) Let δ = a/b with a and b being coprime. If a ≤ 2, then δ-Dispersion is polynomial-time solvable. For a ≥ 3, given a tree decomposition of width t, the problem can be solved in time (2a)^t⋅ n^O(1), and, assuming SETH, there is no (2a-ε)^t⋅n^{O(1)} time algorithm for any ε > 0. 2) Let δ = a/b with a and b being coprime. If a = 1, then δ-Covering is polynomial-time solvable. For a ≥ 2, given a tree decomposition of width t, the problem can be solved in time ((2+2(bod 2)) a)^t⋅ n^O(1), and, assuming SETH, there is no ((2+2(bod 2))a -ε)^t⋅n^O(1) time algorithm for any ε > 0. 3) For every fixed irrational number δ > 0 satisfying some mild computability condition, both δ-Dispersion and δ-Covering can be solved in time n^O(t) on graphs of treewidth t. We show a very explicitly defined irrational number δ = (4∑_{j=1}^∞ 2^{-2^j})^{-1} ≈ 0.790085 such that δ-Dispersion and δ/2-Covering are W[1]-hard parameterized by the treewidth t of the input graph, and, assuming ETH, cannot be solved in time f(t)⋅n^o(t). As a key step in obtaining these results, we extend earlier results on distance-d versions of Independent Set and Dominating Set: We determine the exact complexity of these problems in the special case when the input graph arises from some graph G' by subdividing every edge exactly b times.
Cite as

Tim A. Hartmann and Dániel Marx. Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartmann_et_al:LIPIcs.STACS.2025.44,
  author =	{Hartmann, Tim A. and Marx, D\'{a}niel},
  title =	{{Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.44},
  URN =		{urn:nbn:de:0030-drops-228700},
  doi =		{10.4230/LIPIcs.STACS.2025.44},
  annote =	{Keywords: Independence, Domination, Irrationals, Treewidth, SETH}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.55
Dispersing Obnoxious Facilities on Graphs by Rounding Distances

Authors: Tim A. Hartmann and Stefan Lendl

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We continue the study of δ-dispersion, a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that every two facilities have distance at least δ from each other. Our main technical contribution is an efficient procedure to "round-up" distance δ. It transforms a δ-dispersed set S into a δ^⋆-dispersed set S^⋆ of same size where distance δ^⋆ is a potentially slightly larger rational a/b with a numerator a upper bounded by the longest (not-induced) path in the input graph. Based on this rounding procedure and connections to the distance-d independent set problem we derive a number of algorithmic results. When parameterized by treewidth, the problem is in XP. When parameterized by treedepth the problem is FPT and has a matching lower bound on its time complexity under ETH. Moreover, we can also settle the parameterized complexity with the solution size as parameter using our rounding technique: δ-Dispersion is FPT for every δ ≤ 2 and W[1]-hard for every δ > 2. Further, we show that δ-dispersion is NP-complete for every fixed irrational distance δ, which was left open in a previous work.
Cite as

Tim A. Hartmann and Stefan Lendl. Dispersing Obnoxious Facilities on Graphs by Rounding Distances. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hartmann_et_al:LIPIcs.MFCS.2022.55,
  author =	{Hartmann, Tim A. and Lendl, Stefan},
  title =	{{Dispersing Obnoxious Facilities on Graphs by Rounding Distances}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{55:1--55:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.55},
  URN =		{urn:nbn:de:0030-drops-168536},
  doi =		{10.4230/LIPIcs.MFCS.2022.55},
  annote =	{Keywords: facility location, parameterized complexity, packing}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.19
An Investigation of the Recoverable Robust Assignment Problem

Authors: Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We investigate the so-called recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ have at least k edges in common. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to parameter k, and also with respect to the complementary parameter k' = n/2-k. This hardness result holds even in the highly restricted special case where both cost functions c₁ and c₂ only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is Anti-Monge. Finally, we study the variant where matching M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², and we show that it is at least as hard as the infamous problem Exact Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing open problem.
Cite as

Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.IPEC.2021.19,
  author =	{Fischer, Dennis and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{An Investigation of the Recoverable Robust Assignment Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154025},
  doi =		{10.4230/LIPIcs.IPEC.2021.19},
  annote =	{Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.33
Dispersing Obnoxious Facilities on a Graph

Authors: Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance delta from each other. We investigate the complexity of this problem in terms of the rational parameter delta. The problem is polynomially solvable, if the numerator of delta is 1 or 2, while all other cases turn out to be NP-hard.
Cite as

Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Dispersing Obnoxious Facilities on a Graph. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 33:1-33:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grigoriev_et_al:LIPIcs.STACS.2019.33,
  author =	{Grigoriev, Alexander and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{Dispersing Obnoxious Facilities on a Graph}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{33:1--33:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.33},
  URN =		{urn:nbn:de:0030-drops-102729},
  doi =		{10.4230/LIPIcs.STACS.2019.33},
  annote =	{Keywords: algorithms, complexity, optimization, graph theory, facility location}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2022
  • 1 2021
  • 1 2019

  • Refine by Author
  • 4 Hartmann, Tim A.
  • 3 Lendl, Stefan
  • 2 Woeginger, Gerhard J.
  • 1 Fischer, Dennis
  • 1 Grigoriev, Alexander
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Discrete optimization
  • 3 Theory of computation → Problems, reductions and completeness
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing
  • Show More...

  • Refine by Keyword
  • 2 facility location
  • 1 Complexity
  • 1 Domination
  • 1 Graph modification
  • 1 Independence
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact