49 Search Results for "Zaroliagis, Christos D."

Volume

OASIcs, Volume 85

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

ATMOS 2020, September 7-8, 2020, Pisa, Italy (Virtual Conference)

Editors: Dennis Huisman and Christos D. Zaroliagis

Document
DOI: 10.4230/LIPIcs.IPEC.2025.16
Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance (I,k) can be reduced in polynomial time to an integer linear program (ILP) with poly(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size poly(k) that can be verified in time poly(k). By combining known data structures with new ideas, we design such protocols for several problems, such as r-Way Cut, Vertex Multiway Cut, Steiner Tree, and Minimum Common String Partition, thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems.
Cite as

Michał Włodarczyk. Designing Compact ILPs via Fast Witness Verification. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.IPEC.2025.16,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Designing Compact ILPs via Fast Witness Verification}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.16},
  URN =		{urn:nbn:de:0030-drops-251481},
  doi =		{10.4230/LIPIcs.IPEC.2025.16},
  annote =	{Keywords: integer programming, kernelization, nondeterminism, multiway cut}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.12
Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments

Authors: Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Planar Separator Theorem, which states that any planar graph 𝒢 has a separator consisting of O(√n) nodes whose removal partitions 𝒢 into components of size at most 2n/3, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of disks, which generalize planar graphs, do not admit such separators. It has recently been shown that disk graphs do admit so-called clique-based separators that consist of O(√n) cliques. This result has been generalized to intersection graphs of various other types of disk-like objects. Unfortunately, segment intersection graphs do not admit small clique-based separators, because they can contain arbitrarily large bicliques. This is true even in the simple case of axis-aligned segments. In this paper we therefore introduce biclique-based separators (and, in particular, star-based separators), which are separators consisting of a small number of bicliques (or stars). We prove that any c-oriented set of n segments in the plane, where c is a constant, admits a star-based separator consisting of O(√n) stars. In fact, our result is more general, as it applies to any set of n pseudo-segments that is partitioned into c subsets such that the pseudo-segments in the same subset are pairwise disjoint. We extend our result to intersection graphs of c-oriented polygons. These results immediately lead to an almost-exact distance oracle for such intersection graphs, which has O(n√n) storage and O(√n) query time, and that can report the hop-distance between any two query nodes in the intersection graph with an additive error of at most 2. This is the first distance oracle for such types of intersection graphs that has subquadratic storage and sublinear query time and that only has an additive error.
Cite as

Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme. Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.12,
  author =	{de Berg, Mark and Jansen, Bart M. P. and Lamme, Jeroen S. K.},
  title =	{{Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.12},
  URN =		{urn:nbn:de:0030-drops-249207},
  doi =		{10.4230/LIPIcs.ISAAC.2025.12},
  annote =	{Keywords: Computational geometry, intersection graphs, biclique-based separators, distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.5
External-Memory Priority Queues with Optimal Insertions

Authors: Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, and Rolf Svenning

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present an external-memory priority queue structure supporting Insert and DeleteMin with amortized 𝒪(1) and 𝒪(lg N) comparisons, respectively, and amortized 𝒪(1/B) and 𝒪(1/B log_{M/B} N/B) I/Os, respectively. Here, M is the size of the internal memory, B is the block size of I/Os between internal and external memory, and N is the number of elements in the priority queue just before an operation is performed. Previous external-memory priority queues required amortized 𝒪(lg N) comparisons and 𝒪(1/B log_{M/B} N/B) I/Os for both Insert and DeleteMin. The construction requires the minimal assumption M ≥ 2B.
Cite as

Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, and Rolf Svenning. External-Memory Priority Queues with Optimal Insertions. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2025.5,
  author =	{Brodal, Gerth St{\o}lting and Goodrich, Michael T. and Iacono, John and Lo, Jared and Meyer, Ulrich and Pagan, Victor and Sitchinava, Nodari and Svenning, Rolf},
  title =	{{External-Memory Priority Queues with Optimal Insertions}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.5},
  URN =		{urn:nbn:de:0030-drops-244734},
  doi =		{10.4230/LIPIcs.ESA.2025.5},
  annote =	{Keywords: priority queues, external memory, cache aware, amortized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.22
Constructing Long Paths in Graph Streams

Authors: Christian Konrad and Chhaya Trehan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the graph stream model of computation, an algorithm processes the edges of an n-vertex input graph in one or more sequential passes while using a memory that is sublinear in the input size. The streaming model poses significant challenges for algorithmically constructing long paths. Many known algorithms that are tasked with extending an existing path as a subroutine require an entire pass over the input to add a single additional edge. This raises a fundamental question: Are multiple passes inherently necessary to construct paths of non-trivial lengths, or can a single pass suffice? To address this question, we systematically study the Longest Path problem in the one-pass streaming model. In this problem, given a desired approximation factor α, the objective is to compute a path of length at least lp(G)/α, where lp(G) is the length of a longest path in the input graph G. We study the problem in the insertion-only and the insertion-deletion streaming models, and we give algorithms as well as space lower bounds for both undirected and directed graphs. Our results are: 1) We show that for undirected graphs, in both the insertion-only and the insertion-deletion models, there are semi-streaming algorithms, i.e., algorithms that use space O(n poly log n), that compute a path of length at least d/3 with high probability, where d is the average degree of the input graph. These algorithms can also yield an α-approximation to Longest Path using space Õ(n²/α). 2) Next, we show that such a result cannot be achieved for directed graphs, even in the insertion-only model. We show that computing a (n^{1-o(1)})-approximation to Longest Path in directed graphs in the insertion-only model requires space Ω(n²). This result is in line with recent results that demonstrate that processing directed graphs is often significantly harder than undirected graphs in the streaming model. 3) We further complement our results with two additional lower bounds. First, we show that semi-streaming space is insufficient for small constant factor approximations to Longest Path for undirected graphs in the insertion-only model. Last, in undirected graphs in the insertion-deletion model, we show that computing an α-approximation requires space Ω(n²/α³).
Cite as

Christian Konrad and Chhaya Trehan. Constructing Long Paths in Graph Streams. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ESA.2025.22,
  author =	{Konrad, Christian and Trehan, Chhaya},
  title =	{{Constructing Long Paths in Graph Streams}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.22},
  URN =		{urn:nbn:de:0030-drops-244902},
  doi =		{10.4230/LIPIcs.ESA.2025.22},
  annote =	{Keywords: Longest Path Problem, Streaming Algorithms, One-way Two-party Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.59
Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets

Authors: Konstantinos Karathanasis, Spyros Kontogiannis, and Christos Zaroliagis

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A key task in multi-objective optimization is to compute the Pareto frontier (a.k.a. Pareto subset) P of a given d-dimensional objective space F; that is, a maximal subset P ⊆ F such that every element in P is non-dominated (i.e., it is better in at least one criterion, against any other point) within F. This process, called dominance-filtering, often involves handling objective spaces derived from either the union or the Minkowski sum of two given partial objective spaces which are Pareto sets themselves, and constitutes a major bottleneck in several multi-objective optimization techniques. In this work, we introduce three new data structures, ND^{+}-trees, QND^{+}-trees and TND^{+}-trees, which are designed for efficiently indexing non-dominated objective vectors and performing dominance-checks. We also devise three new algorithms that efficiently filter out dominated objective vectors from the union or the Minkowski sum of two Pareto sets. An extensive experimental evaluation on both synthetically generated and real-world data sets reveals that our new algorithms outperform state-of-art techniques for dominance-filtering of unions and Minkowski sums of Pareto sets, and scale well w.r.t. the number of d ≥ 3 criteria and the sets' sizes.
Cite as

Konstantinos Karathanasis, Spyros Kontogiannis, and Christos Zaroliagis. Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{karathanasis_et_al:LIPIcs.ESA.2025.59,
  author =	{Karathanasis, Konstantinos and Kontogiannis, Spyros and Zaroliagis, Christos},
  title =	{{Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.59},
  URN =		{urn:nbn:de:0030-drops-245277},
  doi =		{10.4230/LIPIcs.ESA.2025.59},
  annote =	{Keywords: Multi-Objective Optimization, Multi-Dimensional Data Structures, Pareto Sets, Algorithm Engineering}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.33
Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

Authors: Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We show how to preprocess a weighted undirected n-vertex planar graph in Õ(n^{4/3}) time, such that the distance between any pair of vertices can then be reported in Õ(1) time. This improves the previous Õ(n^{3/2}) preprocessing time [JACM'23]. Our main technical contribution is a near optimal construction of additively weighted Voronoi diagrams in undirected planar graphs. Namely, given a planar graph G and a face f, we show that one can preprocess G in Õ(n) time such that given any weight assignment to the vertices of f one can construct the additively weighted Voronoi diagram of f in near optimal Õ(|f|) time. This improves the Õ(√{n|f|}) construction time of [JACM'23].
Cite as

Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann. Faster Construction of a Planar Distance Oracle with Õ(1) Query Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.ICALP.2025.33,
  author =	{Boneh, Itai and Golan, Shay and Mozes, Shay and Prigan, Daniel and Weimann, Oren},
  title =	{{Faster Construction of a Planar Distance Oracle with \~{O}(1) Query Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.33},
  URN =		{urn:nbn:de:0030-drops-234106},
  doi =		{10.4230/LIPIcs.ICALP.2025.33},
  annote =	{Keywords: Distance Oracle, Planar Graph, Construction Time}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.100
Robust-Sorting and Applications to Ulam-Median

Authors: Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal when the outcome of each comparison is error-free. However, many real-world sorting applications operate in scenarios where the outcome of each comparison can be noisy. In this work, we explore settings where a bounded number of comparisons are potentially corrupted by erroneous agents, resulting in arbitrary, adversarial outcomes. We model the sorting problem as a query-limited tournament graph where edges involving erroneous nodes may yield arbitrary results. Our primary contribution is a randomized algorithm inspired by quick-sort that, in expectation, produces an ordering close to the true total order while only querying Õ(n) edges. We achieve a distance from the target order π within (3 + ε)|B|, where B is the set of erroneous nodes, balancing the competing objectives of minimizing both query complexity and misalignment with π. Our algorithm needs to carefully balance two aspects - identify a pivot that partitions the vertex set evenly and ensure that this partition is "truthful" and yet query as few "triangles" in the graph G as possible. Since the nodes in B can potentially hide in an intricate manner, our algorithm requires several technical steps that ensure that progress is made in each recursive step. Additionally, we demonstrate significant implications for the Ulam-k-Median problem. This is a classical clustering problem where the metric is defined on the set of permutations on a set of d elements. Chakraborty, Das, and Krauthgamer gave a (2-ε) FPT approximation algorithm for this problem, where the running time is super-linear in both n and d. We give the first (2-ε) FPT linear time approximation algorithm for this problem. Our main technical result gives a strengthening of the results in Chakraborty et al. by showing that a good 1-median solution can be obtained from a constant-size random sample of the input. We use our robust sorting framework to find a good solution from such a random sample. We feel that the notion of robust sorting should have applications in several such settings.
Cite as

Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-Sorting and Applications to Ulam-Median. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jaiswal_et_al:LIPIcs.ICALP.2025.100,
  author =	{Jaiswal, Ragesh and Kumar, Amit and Yadav, Jatin},
  title =	{{Robust-Sorting and Applications to Ulam-Median}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{100:1--100:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.100},
  URN =		{urn:nbn:de:0030-drops-234774},
  doi =		{10.4230/LIPIcs.ICALP.2025.100},
  annote =	{Keywords: Sorting, clustering, query complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.27
Computing Oriented Spanners and Their Dilation

Authors: Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph G = (P, E), where for every pair of distinct points p and q in P, the shortest oriented closed walk in G that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph G is the minimum t for which G is an oriented t-spanner. For arbitrary point sets of size n in ℝ^d, where d ≥ 2 is a constant, the only known oriented spanner construction is an oriented 2-spanner with binom(n,2) edges. Moreover, there exists a set P of four points in the plane, for which the oriented dilation is larger than 1.46, for any oriented graph on P. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝ^d, where d is a constant, we construct an oriented (2+ε)-spanner with 𝒪(n) edges in 𝒪(n log n) time and 𝒪(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in 𝒪(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the oriented graph is already given, computing its oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝ^d, where d is a constant.
Cite as

Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong. Computing Oriented Spanners and Their Dilation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.27,
  author =	{Buchin, Kevin and Kalb, Antonia and Maheshwari, Anil and Odak, Saeed and Rehs, Carolin and Smid, Michiel and Wong, Sampson},
  title =	{{Computing Oriented Spanners and Their Dilation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.27},
  URN =		{urn:nbn:de:0030-drops-231792},
  doi =		{10.4230/LIPIcs.SoCG.2025.27},
  annote =	{Keywords: spanner, oriented graph, dilation, orientation, well-separated pair decomposition, minimum-perimeter triangle}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.38
An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Authors: Colleen Delaney, Clément Maria, and Eric Samperton

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Quantum topology provides various frameworks for defining and computing invariants of manifolds inspired by quantum theory. One such framework of substantial interest in both mathematics and physics is the Turaev-Viro-Barrett-Westbury state sum construction, which uses the data of a spherical fusion category to define topological invariants of triangulated 3-manifolds via tensor network contractions. In this work we analyze the computational complexity of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. While these categories are the simplest source of state sum invariants beyond finite abelian groups (whose invariants can be computed in polynomial time) their computational complexities are yet to be fully understood. We first establish that the invariants arising from even the smallest Tambara-Yamagami categories are #P-hard to compute, so that one expects the same to be true of the whole family. Our main result is then the existence of a fixed parameter tractable algorithm to compute these 3-manifold invariants, where the parameter is the first Betti number of the 3-manifold with ℤ/2ℤ coefficients. Contrary to other domains of computational topology, such as graphs on surfaces, very few hard problems in 3-manifold topology are known to admit FPT algorithms with a topological parameter. However, such algorithms are of particular interest as their complexity depends only polynomially on the combinatorial representation of the input, regardless of size or combinatorial width. Additionally, in the case of Betti numbers, the parameter itself is computable in polynomial time. Thus while one generally expects quantum invariants to be hard to compute classically, our results suggest that the hardness of computing state sum invariants from Tambara-Yamagami categories arises from classical 3-manifold topology rather than the quantum nature of the algebraic input.
Cite as

Colleen Delaney, Clément Maria, and Eric Samperton. An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{delaney_et_al:LIPIcs.SoCG.2025.38,
  author =	{Delaney, Colleen and Maria, Cl\'{e}ment and Samperton, Eric},
  title =	{{An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.38},
  URN =		{urn:nbn:de:0030-drops-231901},
  doi =		{10.4230/LIPIcs.SoCG.2025.38},
  annote =	{Keywords: 3-manifold, quantum invariant, fixed parameter tractable algorithm, topological parameter, Gauss sums, topological quantum field theory}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.7
Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs

Authors: David C. Kutner and Anouk Sommer

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
In train networks, carefully-chosen delays may be beneficial for certain passengers, who would otherwise miss some connection. Given a simple (directed or undirected) temporal graph and a set of passengers (each specifying a starting vertex, an ending vertex, and a desired arrival time), we ask whether it is possible to delay some of the edges of the temporal graph to realize all the passengers' demands. We call this problem DelayBetter (DB), and study it along with two variants: in δ-DelayBetter, each delay must be of at most δ; in (δ-)Path DB, passengers also fully specify the vertices they should visit on their journey. On the positive side, we give a polynomial-time algorithm for Path DB and δ-Path DB, and obtain as a corollary a polynomial-time algorithm for DB and δ-DB on trees. We also provide an fpt algorithm for both problems parameterized by the size of the graph’s Feedback Edge Set together with the number of passengers. On the negative side, we show NP-completeness of (1-)DB on bounded-degree temporal graphs even when the lifetime is 2, and of (10-)DB on bounded-degree planar temporal graphs of lifetime 19. Our results complement previous work studying reachability problems in temporal graphs with delaying operations. This is to our knowledge the first such problem in which the aim is to facilitate travel between specific points (as opposed to facilitating or impeding a broadcast from one or many sources).
Cite as

David C. Kutner and Anouk Sommer. Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kutner_et_al:LIPIcs.SAND.2025.7,
  author =	{Kutner, David C. and Sommer, Anouk},
  title =	{{Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.7},
  URN =		{urn:nbn:de:0030-drops-230604},
  doi =		{10.4230/LIPIcs.SAND.2025.7},
  annote =	{Keywords: Temporal Graphs, Computational Complexity, Delay Management, Train Networks}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.28
Can You Link Up With Treewidth?

Authors: Radu Curticapean, Simon Döring, Daniel Neuen, and Jiaheng Wang

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

Abstract
A central result by Marx [ToC '10] constructs k-vertex graphs H of maximum degree 3 such that n^o(k/log k) time algorithms for detecting colorful H-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is widely used to obtain almost-tight conditional lower bounds for parameterized problems under ETH. Our first contribution is a new and fully self-contained proof of this result that further simplifies a recent work by Karthik et al. [SOSA 2024]. In our proof, we introduce a novel graph parameter of independent interest, the linkage capacity γ(H), and show that detecting colorful H-subgraphs in time n^o(γ(H)) refutes ETH. Then, we use a simple construction of communication networks credited to Beneš to obtain k-vertex graphs of maximum degree 3 and linkage capacity Ω(k/log k), avoiding arguments involving expander graphs, which were required in previous papers. We also show that every graph H of treewidth t has linkage capacity Ω(t/log t), thus recovering a stronger result shown by Marx [ToC '10] with a simplified proof. Additionally, we obtain new tight lower bounds on the complexity of subgraph detection for certain types of patterns by analyzing their linkage capacity: We prove that almost all k-vertex graphs of polynomial average degree Ω(k^β) for β > 0 have linkage capacity Θ(k), which implies tight lower bounds for finding such patterns H. As an application of these results, we also obtain tight lower bounds for counting small induced subgraphs having a fixed property Φ, improving bounds from, e.g., [Roth et al., FOCS 2020].
Cite as

Radu Curticapean, Simon Döring, Daniel Neuen, and Jiaheng Wang. Can You Link Up With Treewidth?. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{curticapean_et_al:LIPIcs.STACS.2025.28,
  author =	{Curticapean, Radu and D\"{o}ring, Simon and Neuen, Daniel and Wang, Jiaheng},
  title =	{{Can You Link Up With Treewidth?}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{28:1--28:24},
  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.28},
  URN =		{urn:nbn:de:0030-drops-228534},
  doi =		{10.4230/LIPIcs.STACS.2025.28},
  annote =	{Keywords: subgraph isomorphism, constraint satisfaction problems, linkage capacity, exponential-time hypothesis, parameterized complexity, counting complexity}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2020
OASIcs, Volume 85, ATMOS 2020, Complete Volume

Authors: Dennis Huisman and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
OASIcs, Volume 85, ATMOS 2020, Complete Volume
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1-272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{huisman_et_al:OASIcs.ATMOS.2020,
  title =	{{OASIcs, Volume 85, ATMOS 2020, Complete Volume}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{1--272},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020},
  URN =		{urn:nbn:de:0030-drops-131356},
  doi =		{10.4230/OASIcs.ATMOS.2020},
  annote =	{Keywords: OASIcs, Volume 85, ATMOS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dennis Huisman and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huisman_et_al:OASIcs.ATMOS.2020.0,
  author =	{Huisman, Dennis and Zaroliagis, Christos D.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.0},
  URN =		{urn:nbn:de:0030-drops-131363},
  doi =		{10.4230/OASIcs.ATMOS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
  • Refine by Type
  • 48 Document/PDF
  • 11 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 12 2025
  • 20 2020
  • 17 2016

  • Refine by Author
  • 3 Huisman, Dennis
  • 3 Wagner, Dorothea
  • 3 Zaroliagis, Christos D.
  • 2 Dürr, Christoph
  • 2 Golan, Shay
  • Show More...

  • Refine by Series/Journal
  • 29 LIPIcs
  • 19 OASIcs

  • Refine by Classification
  • 13 Applied computing → Transportation
  • 5 Mathematics of computing → Graph algorithms
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Mathematics of computing → Graph theory
  • 4 Theory of computation → Shortest paths
  • Show More...

  • Refine by Keyword
  • 2 Algorithm Engineering
  • 2 Algorithms
  • 2 Computational geometry
  • 2 Modeling
  • 2 Network Flow
  • 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