31 Search Results for "Kozma, László"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.25
Permutation Patterns in Streams

Authors: Benjamin Aram Berendsohn

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Permutation patterns and pattern avoidance are central, well-studied concepts in combinatorics and computer science. Given two permutations τ and π, the pattern matching problem (PPM) asks whether τ contains π. This problem arises in various contexts in computer science and statistics and has been studied extensively in exact-, parameterized-, approximate-, property-testing- and other formulations. In this paper, we study pattern matching in a streaming setting, when the input τ is revealed sequentially, one element at a time. There is extensive work on the space complexity of various statistics in streams of integers. The novelty of our setting is that the input stream is a permutation, which allows inferring some information about future inputs. Our algorithms crucially take advantage of this fact, while existing lower bound techniques become difficult to apply. We show that the complexity of the problem changes dramatically depending on the pattern π. The space requirement is: - Θ(klog{n}) for the monotone patterns π = 12…k, or π = k…21, - 𝒪(√{nlog{n}}) for π ∈ {312,132}, - 𝒪(√n log n) for π ∈ {231,213}, - Θ̃_π(n) for all other π. If τ is an arbitrary sequence of integers (not necessary a permutation), we show that the complexity is Θ̃_π(n) in all except the first (monotone) cases.
Cite as

Benjamin Aram Berendsohn. Permutation Patterns in Streams. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berendsohn:LIPIcs.ICALP.2026.25,
  author =	{Berendsohn, Benjamin Aram},
  title =	{{Permutation Patterns in Streams}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.25},
  URN =		{urn:nbn:de:0030-drops-264144},
  doi =		{10.4230/LIPIcs.ICALP.2026.25},
  annote =	{Keywords: permutations, pattern matching, streaming}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.5
Efficient Grammar Compression via RLZ-Based RePair

Authors: Rahul Varki, Travis Gagie, and Christina Boucher

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Among grammar-based compression techniques, RePair is a notable offline encoding scheme known for its simplicity and powerful combinatorial properties, producing compact grammars by repeatedly replacing the most frequent adjacent pairs of symbols, known as bigrams. However, RePair’s memory usage scales poorly with input size, as it loads the entire text into memory. In contrast, Relative Lempel-Ziv (RLZ) parsing offers a scalable and lightweight online encoding scheme that losslessly represents a text in terms of phrases that refer to a reference string, but it often fails to expose deeper structural patterns. We introduce an algorithm that produces a RePair grammar from the RLZ parse of the input, leveraging the strengths of both methods. Our method, RLZ-RePair, performs bigram replacements systematically, preserving the integrity of the RLZ phrases throughout the RePair iterations. When the reference is well chosen, our method achieves the same grammar as standard RePair while significantly reducing both memory usage and the number of bigram replacements. In particular, we show that RLZ-RePair can reduce memory usage by more than 80% while incurring only a modest runtime increase compared to RePair. To our knowledge, RLZ-RePair is one of the first scalable methods that constructs exact RePair grammars, resulting in a grammar-based compressor that is both practical for large datasets and faithful to the theoretical elegance of RePair.
Cite as

Rahul Varki, Travis Gagie, and Christina Boucher. Efficient Grammar Compression via RLZ-Based RePair. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{varki_et_al:LIPIcs.CPM.2026.5,
  author =	{Varki, Rahul and Gagie, Travis and Boucher, Christina},
  title =	{{Efficient Grammar Compression via RLZ-Based RePair}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.5},
  URN =		{urn:nbn:de:0030-drops-259310},
  doi =		{10.4230/LIPIcs.CPM.2026.5},
  annote =	{Keywords: RePair, RLZ, Grammar Compression}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.14
Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

Authors: Jaehoon Chung

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study a variant of a polygon partition problem, introduced by Chung, Iwama, Liao, and Ahn [ISAAC'25]. Given orthogonal unit vectors 𝐮,𝐯 ∈ ℝ² and a polygon P with n vertices, we partition P into connected pieces by cuts parallel to 𝐯 such that each resulting subpolygon has width at most one in direction 𝐮. We consider the value version, which asks for the minimum number of strips, and the reporting version, which outputs a compact encoding of the cuts in an optimal strip partition. We give efficient algorithms and lower bounds for both versions on three classes of polygons of increasing generality: convex, simple, and self-overlapping. For convex polygons, we solve the value version in O(log n) time and the reporting version in O(h log (1 + n/h)) time, where h is the width of P in direction 𝐮. We prove matching lower bounds in the decision-tree model, showing that the reporting algorithm is input-sensitive optimal with respect to h. For simple polygons, we present O(n log n)-time, O(n)-space algorithms for both versions and prove an Ω(n) lower bound. For self-overlapping polygons, we extend the approach for simple polygons to obtain O(n log n)-time, O(n)-space algorithms for both versions, and we prove a matching Ω(n log n) lower bound in the algebraic computation-tree model via a reduction from the δ-closeness problem. Our approach relies on a lattice-theoretic formulation of the problem. We represent strip partitions as antichains of intervals in the Clarke-Cormack-Burkowski lattice, originally developed for minimal-interval semantics in information retrieval. Within this lattice framework, we design a dynamic programming algorithm that uses the lattice operations of meet and join. To the best of our knowledge, this is the first geometric application of the Clarke-Cormack-Burkowski lattice.
Cite as

Jaehoon Chung. Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chung:LIPIcs.SWAT.2026.14,
  author =	{Chung, Jaehoon},
  title =	{{Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.14},
  URN =		{urn:nbn:de:0030-drops-260506},
  doi =		{10.4230/LIPIcs.SWAT.2026.14},
  annote =	{Keywords: Polygon partitioning, Strip partition, Lattice, Self-overlapping curves}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.4
Improved Bounds for Online TSP on the Half-Line

Authors: Júlia Baligács, Yann Disser, and Linda Thelen

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a 2-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of 2.04. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below 2. We introduce a second algorithm that beats the barrier of 2 by carefully modulating its speed, and prove a tight bound of 1.75 on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from 1.627 to 1.646.
Cite as

Júlia Baligács, Yann Disser, and Linda Thelen. Improved Bounds for Online TSP on the Half-Line. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.SWAT.2026.4,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Thelen, Linda},
  title =	{{Improved Bounds for Online TSP on the Half-Line}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.4},
  URN =		{urn:nbn:de:0030-drops-260402},
  doi =		{10.4230/LIPIcs.SWAT.2026.4},
  annote =	{Keywords: online algorithms, competitive analysis, server problems, online TSP}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.52
Online Packing of Orthogonal Polygons

Authors: Tim Gerlach, Benjamin Hennies, and Linda Kleist

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in Ω(n/(log n)), where n denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least n. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness 0), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than n. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in Ω(n/(log n)) for strip packing, and there exist online algorithms with competitive ratios in O(1) for perimeter packing, or in O(√n) for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).
Cite as

Tim Gerlach, Benjamin Hennies, and Linda Kleist. Online Packing of Orthogonal Polygons. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.SoCG.2026.52,
  author =	{Gerlach, Tim and Hennies, Benjamin and Kleist, Linda},
  title =	{{Online Packing of Orthogonal Polygons}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.52},
  URN =		{urn:nbn:de:0030-drops-258589},
  doi =		{10.4230/LIPIcs.SoCG.2026.52},
  annote =	{Keywords: Packing, orthogonal polygon, algorithm, offline, online, competitive ratio, bin packing, strip packing, perimeter packing, critical density, 6-gon, 8-gon, L-shape, Z-shape, skeleton}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.58
A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP

Authors: Andreas Kalavas, Charalampos Platanos, and Thanos Tolias

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In Online Sorting, an array of n initially empty cells is given. At each time step t, an element x_t ∈ [0,1] arrives and must be irrevocably placed in an empty cell without knowledge of future arrivals. We aim to minimize the sum of absolute differences between pairs of elements placed in consecutive array cells, seeking an online placement strategy that results in a final array close to a sorted one. An interesting multidimensional generalization, referred to as the Online Traveling Salesperson Problem, arises when the request sequence consists of points in the d-dimensional unit cube and the objective is to minimize the sum of Euclidean distances between points in consecutive cells. Motivated by the recent work of (Abrahamsen, Bercea, Beretta, Klausen and Kozma; ESA 2024), we consider the stochastic version of Online Sorting (resp. Online TSP), where each element (resp. point) x_t is an i.i.d. sample from the uniform distribution on [0, 1] (resp. [0,1]^d). By carefully decomposing the request sequence into a hierarchy of balls-into-bins instances, where the balls to bins ratio is large enough so that bin occupancy is sharply concentrated around its mean and small enough so that we can efficiently deal with the elements placed in the same bin, we obtain an online algorithm that approximates the optimal cost within a factor of O(log² n) with high probability. Our result comprises an exponential improvement over the previously best known competitive ratio of Õ(n^{1/4}) for Stochastic Online Sorting due to (Abrahamsen et al.; ESA 2024) and O(√n) for (adversarial) Online TSP due to (Bertram, ESA 2025).
Cite as

Andreas Kalavas, Charalampos Platanos, and Thanos Tolias. A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.STACS.2026.58,
  author =	{Kalavas, Andreas and Platanos, Charalampos and Tolias, Thanos},
  title =	{{A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.58},
  URN =		{urn:nbn:de:0030-drops-255473},
  doi =		{10.4230/LIPIcs.STACS.2026.58},
  annote =	{Keywords: sorting, online algorithm, balls-into-bins, TSP}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.52
Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.
Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}
Document
DOI: 10.4230/DagRep.15.5.1
Adaptive and Scalable Data Structures (Dagstuhl Seminar 25191)

Authors: Michael A. Bender, John Iacono, László Kozma, Eva Rotenberg, and Justin Dallant

Published in: Dagstuhl Reports, Volume 15, Issue 5 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25191 "Adaptive and Scalable Data Structures". Data structures govern the organization and manipulation of data in computing systems across a broad range of applications. The efficiency and scalability of data structures has profound implications, motivating continued research on the entire spectrum from theoretical to practical. As the size and complexity of data sets increases and as the underlying computing infrastructure changes, data structures need to be continually redesigned with scalability in mind. Classical data structures also need reevaluation to better fit the requirements of modern applications. Adaptivity offers a way to design data structures that automatically take advantage of features of the underlying hardware, specific structure and biases in their usage, or side-information, and the limits of data structure adaptivity pose deep research questions. The goal of this seminar was to reflect on these complementary aspects of data structure research and to identify promising research questions. The program provides a snapshot of the current state of research and establishes possible future directions for the field.
Cite as

Michael A. Bender, John Iacono, László Kozma, Eva Rotenberg, and Justin Dallant. Adaptive and Scalable Data Structures (Dagstuhl Seminar 25191). In Dagstuhl Reports, Volume 15, Issue 5, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{bender_et_al:DagRep.15.5.1,
  author =	{Bender, Michael A. and Iacono, John and Kozma, L\'{a}szl\'{o} and Rotenberg, Eva and Dallant, Justin},
  title =	{{Adaptive and Scalable Data Structures (Dagstuhl Seminar 25191)}},
  pages =	{1--20},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{5},
  editor =	{Bender, Michael A. and Iacono, John and Kozma, L\'{a}szl\'{o} and Rotenberg, Eva and Dallant, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.5.1},
  URN =		{urn:nbn:de:0030-drops-252802},
  doi =		{10.4230/DagRep.15.5.1},
  annote =	{Keywords: Data structures, Algorithms, Big data, Computational models}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.30
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers

Authors: Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler

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

Abstract
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.
Cite as

Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler. A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.IPEC.2025.30,
  author =	{Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert},
  title =	{{A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{30:1--30:19},
  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.30},
  URN =		{urn:nbn:de:0030-drops-251623},
  doi =		{10.4230/LIPIcs.IPEC.2025.30},
  annote =	{Keywords: Hamiltonian path, Hamiltonian cycle, partial order, graph width parameter, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

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

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  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.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.80
Online Metric TSP

Authors: Christian Bertram

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

Abstract
In the online metric traveling salesperson problem, n points of a metric space arrive one by one and have to be placed (immediately and irrevocably) into empty cells of a size-n array. The goal is to minimize the sum of distances between consecutive points in the array. This problem was introduced by Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA'24] as a generalization of the online sorting problem, which was introduced by Aamand, Abrahamsen, Beretta, and Kleist [SODA'23] as a tool in their study of online geometric packing problems. Online metric TSP has been studied for a range of fixed metric spaces. For 1-dimensional Euclidean space, the problem is equivalent to online sorting, where an optimal competitive ratio of Θ(√n) is known. For d-dimensional Euclidean space, the best-known upper bound is O(2^d √{dn log n}), leaving a gap to the Ω(√n) lower bound. Finally, for the uniform metric, where all distances are 0 or 1, the optimal competitive ratio is known to be Θ(log n). We study the problem for a general metric space, presenting an algorithm with competitive ratio O(√n). In particular, we close the gap for d-dimensional Euclidean space, completely removing the dependence on dimension. One might hope to simultaneously guarantee competitive ratio O(√n) in general and O(log n) for the uniform metric, but we show that this is impossible.
Cite as

Christian Bertram. Online Metric TSP. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 80:1-80:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bertram:LIPIcs.ESA.2025.80,
  author =	{Bertram, Christian},
  title =	{{Online Metric TSP}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{80:1--80:9},
  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.80},
  URN =		{urn:nbn:de:0030-drops-245485},
  doi =		{10.4230/LIPIcs.ESA.2025.80},
  annote =	{Keywords: online algorithm, metric space, TSP}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.110
Faster Exponential Algorithms for Cut Problems via Geometric Data Structures

Authors: László Kozma and Junqi Tan

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

Abstract
For many hard computational problems, simple algorithms that run in time 2ⁿ ⋅ n^O(1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this paper we obtain algorithms with running time O(1.9999977ⁿ) on input graphs with n vertices, for the following well-studied problems: - d-Cut: find a proper cut in which no vertex has more than d neighbors on the other side of the cut; - Internal Partition: find a proper cut in which every vertex has at least as many neighbors on its side of the cut as on the other side; and - (α,β)-Domination: given intervals α,β ⊆ [0,n], find a subset S of the vertices, so that for every vertex v ∈ S the number of neighbors of v in S is from α and for every vertex v ∉ S, the number of neighbors of v in S is from β. Our algorithms are exceedingly simple, combining the split and list technique (Horowitz and Sahni, 1974; Williams, 2005) with a tool from computational geometry: orthogonal range searching in the moderate dimensional regime (Chan, 2017). Our technique is applicable to the decision, optimization and counting versions of these problems and easily extends to various generalizations with more fine-grained, vertex-specific constraints, as well as to directed, balanced, and other variants. Algorithms with running times of the form cⁿ, for c < 2, were known for the first problem only for constant d, and for the third problem for certain special cases of α and β; for the second problem we are not aware of such results.
Cite as

László Kozma and Junqi Tan. Faster Exponential Algorithms for Cut Problems via Geometric Data Structures. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 110:1-110:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.ESA.2025.110,
  author =	{Kozma, L\'{a}szl\'{o} and Tan, Junqi},
  title =	{{Faster Exponential Algorithms for Cut Problems via Geometric Data Structures}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{110:1--110:12},
  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.110},
  URN =		{urn:nbn:de:0030-drops-245796},
  doi =		{10.4230/LIPIcs.ESA.2025.110},
  annote =	{Keywords: graph algorithms, cuts, exponential time, data structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.42
(Multivariate) k-SUM as Barrier to Succinct Computation

Authors: Geri Gokaj, Marvin Künnemann, Sabine Storandt, and Carina Truschel

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

Abstract
How does the time complexity of a problem change when the input is given succinctly rather than explicitly? We study this question for several geometric problems defined on a set X of N points in ℤ^d. As succinct representation, we choose a sumset (or Minkowski sum) representation: Instead of receiving X explicitly, we are given sets A,B of n points that define X as A+B = {a+b∣ a ∈ A,b ∈ B}. We investigate the fine-grained complexity of this succinct version for several Õ(N)-time computable geometric primitives. Remarkably, we can tie their complexity tightly to the complexity of corresponding k-SUM problems. Specifically, we introduce as All-ints 3-SUM(n,n,k) the following multivariate, multi-output variant of 3-SUM: given sets A,B of size n and set C of size k, determine for all c ∈ C whether there are a ∈ A and b ∈ B with a+b = c. We obtain the following results: 1) Succinct closest L_∞-pair requires time N^{1-o(1)} under the 3-SUM hypothesis, while succinct furthest L_∞-pair can be solved in time Õ(n). 2) Succinct bichromatic closest L_∞-Pair requires time N^{1-o(1)} iff the 4-SUM hypothesis holds. 3) The following problems are fine-grained equivalent to All-ints 3-SUM(n,n,k): succinct skyline computation in 2D with output size k and succinct batched orthogonal range search with k given ranges. This establishes conditionally tight Õ(min{nk, N})-time algorithms for these problems. We obtain further connections with All-ints 3-SUM(n,n,k) for succinctly computing independent sets in unit interval graphs. Thus, (Multivariate) k-SUM problems precisely capture the barrier for enabling sumset-succinct computation for various geometric primitives.
Cite as

Geri Gokaj, Marvin Künnemann, Sabine Storandt, and Carina Truschel. (Multivariate) k-SUM as Barrier to Succinct Computation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gokaj_et_al:LIPIcs.ESA.2025.42,
  author =	{Gokaj, Geri and K\"{u}nnemann, Marvin and Storandt, Sabine and Truschel, Carina},
  title =	{{(Multivariate) k-SUM as Barrier to Succinct Computation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{42:1--42: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.42},
  URN =		{urn:nbn:de:0030-drops-245101},
  doi =		{10.4230/LIPIcs.ESA.2025.42},
  annote =	{Keywords: Fine-grained complexity theory, sumsets, additive combinatorics, succinct inputs, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.87
Lazy B-Trees

Authors: Casper Moldrup Rysgaard and Sebastian Wild

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

Abstract
Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient priority queues and binary search trees - automatically, depending on actual use; no adjustments are necessary to the data structure to realize the cost savings. In this paper, we design lazy B-trees, a variant of lazy search trees suitable for external memory that generalizes the speedup of B-trees over binary search trees wrt. input/output operations to the same smooth interpolation regime. A key technical difficulty to overcome is the lack of a (fully satisfactory) external variant of biased search trees, on which lazy search trees crucially rely. We give a construction for a subset of performance guarantees sufficient to realize external-memory lazy search trees, which we deem of independent interest. As one special case, lazy B-trees can be used as an external-memory priority queue, in which case they are competitive with some tailor-made heaps; indeed, they offer faster decrease-key and insert operations than known data structures.
Cite as

Casper Moldrup Rysgaard and Sebastian Wild. Lazy B-Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 87:1-87:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rysgaard_et_al:LIPIcs.MFCS.2025.87,
  author =	{Rysgaard, Casper Moldrup and Wild, Sebastian},
  title =	{{Lazy B-Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{87:1--87:19},
  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.87},
  URN =		{urn:nbn:de:0030-drops-241949},
  doi =		{10.4230/LIPIcs.MFCS.2025.87},
  annote =	{Keywords: B-tree, lazy search trees, lazy updates, external memory, deferred data structures, database cracking}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.24
Counting Permutation Patterns with Multidimensional Trees

Authors: Gal Beniamini and Nir Lavee

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

Abstract
We consider the well-studied pattern-counting problem: given a permutation π ∈ 𝕊_n and an integer k > 1, count the number of order-isomorphic occurrences of every pattern τ ∈ 𝕊_k in π. Our first result is an 𝒪̃(n²)-time algorithm for k = 6 and k = 7. The proof relies heavily on a new family of graphs that we introduce, called pattern-trees. Every such tree corresponds to an integer linear combination of permutations in 𝕊_k, and is associated with linear extensions of partially ordered sets. We design an evaluation algorithm for these combinations, and apply it to a family of linearly-independent trees. For k = 8, we show a barrier: the subspace spanned by trees in the previous family has dimension exactly |𝕊₈| - 1, one less than required. Our second result is an 𝒪̃(n^{7/4})-time algorithm for k = 5. This algorithm extends the framework of pattern-trees by speeding-up their evaluation in certain cases. A key component of the proof is the introduction of pair-rectangle-trees, a data structure for dominance counting.
Cite as

Gal Beniamini and Nir Lavee. Counting Permutation Patterns with Multidimensional Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beniamini_et_al:LIPIcs.ICALP.2025.24,
  author =	{Beniamini, Gal and Lavee, Nir},
  title =	{{Counting Permutation Patterns with Multidimensional Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{24:1--24:18},
  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.24},
  URN =		{urn:nbn:de:0030-drops-234018},
  doi =		{10.4230/LIPIcs.ICALP.2025.24},
  annote =	{Keywords: Pattern counting, patterns, permutations}
}
  • Refine by Type
  • 31 Document/PDF
  • 16 Document/HTML

  • Refine by Publication Year
  • 7 2026
  • 10 2025
  • 2 2024
  • 2 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 15 Kozma, László
  • 5 Berendsohn, Benjamin Aram
  • 4 Kaplan, Haim
  • 3 Dallant, Justin
  • 3 Zwick, Uri
  • Show More...

  • Refine by Series/Journal
  • 28 LIPIcs
  • 1 OASIcs
  • 2 DagRep

  • Refine by Classification
  • 11 Theory of computation → Data structures design and analysis
  • 8 Theory of computation → Design and analysis of algorithms
  • 5 Theory of computation → Computational geometry
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Mathematics of computing → Permutations and combinations
  • Show More...

  • Refine by Keyword
  • 3 TSP
  • 3 data structure
  • 3 exponential time
  • 3 online algorithm
  • 3 parameterized complexity
  • 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