DROPS

Volume

LIPIcs, Volume 370

20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

SWAT 2026, Copenhagen, Denmark, June 17-19, 2026

Editors: Pierre Fraigniaud

Volume

LIPIcs, Volume 226

11th International Conference on Fun with Algorithms (FUN 2022)

FUN 2022, May 30 to June 3, 2022, Island of Favignana, Sicily, Italy

Editors: Pierre Fraigniaud and Yushi Uno

Document

DOI: 10.4230/LIPIcs.SWAT.2026.39

Faster Approximate Linear Matroid Intersection

Authors: Tatsuya Terao

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

Abstract

We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two r × n matrices M₁ and M₂, and the objective is to find a largest set of columns that are linearly independent in both M₁ and M₂. We design a (1 - ε)-approximation algorithm with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}), where nnz(M_i) denotes the number of nonzero entries in M_i for i = 1, 2, r_{*} denotes the maximum size of a common independent set, and ω < 2.372 denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS'06 & SICOMP'09] and Cheung-Kwok-Lau [STOC'12 & JACM'13], which runs in Õ(nnz(M₁) + nnz(M₂) + n r_{*}^{ω - 1}) time. We also develop a fast (1 - ε)-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a (1 - ε)-approximation algorithm for weighted linear matroid intersection with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}). Our algorithm improves upon the (1 - ε)-approximation algorithm by Huang-Kakimura-Kamiyama [SODA'16 & Math. Program.'19], which runs in Õ_{ε}(nnz(M₁) + nnz(M₂) + nr_{*}^{ω - 1}) time. To obtain these results, we combine Quanrud’s adaptive sparsification framework [ICALP'24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest.

Cite as

Tatsuya Terao. Faster Approximate Linear Matroid Intersection. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{terao:LIPIcs.SWAT.2026.39,
  author =	{Terao, Tatsuya},
  title =	{{Faster Approximate Linear Matroid Intersection}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{39:1--39:19},
  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.39},
  URN =		{urn:nbn:de:0030-drops-260756},
  doi =		{10.4230/LIPIcs.SWAT.2026.39},
  annote =	{Keywords: Linear matroid intersection, fast approximation algorithm}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.40

Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Authors: Anastasiia Tkachenko and Haitao Wang

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

Abstract

For a set 𝒟 of disks in the plane, its disk graph G(𝒟) is the graph with vertex set 𝒟, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set 𝒟 of n weighted disks, computing a maximum independent set of G(𝒟) is NP-hard. In this paper, we present an O(n³log n)-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of 𝒟. This setting has been studied previously for disks of equal radius, for which an O(n^{37/11})-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an O(n³log² n)-time algorithm for the dispersion problem on a set of n disks in convex position: given an integer k, compute a subset of k disks that maximizes the minimum pairwise distance among all disks in the subset.

Cite as

Anastasiia Tkachenko and Haitao Wang. Maximum Independent Sets in Disk Graphs with Disks in Convex Position. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tkachenko_et_al:LIPIcs.SWAT.2026.40,
  author =	{Tkachenko, Anastasiia and Wang, Haitao},
  title =	{{Maximum Independent Sets in Disk Graphs with Disks in Convex Position}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{40:1--40:18},
  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.40},
  URN =		{urn:nbn:de:0030-drops-260766},
  doi =		{10.4230/LIPIcs.SWAT.2026.40},
  annote =	{Keywords: disk graphs, independent sets, convex position, dispersion}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.38

New Algorithms for Girth and Cycle Detection

Authors: Liam Roditty and Plia Trabelsi

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

Abstract

Let G = (V,E) be an unweighted undirected graph with n vertices and m edges. Let g be the girth of G, that is, the length of a shortest cycle in G. We present a randomized algorithm with a running time of Õ(𝓁 ⋅ n^{1 + 1/(𝓁-ε)}) that returns a cycle of length at most 2𝓁 ⌈g/2⌉ - 2 ⌊ε⌈g/2⌉⌋, where 𝓁 ≥ 2 is an integer and ε ∈ [0,1], for every graph with g = polylog(n). Our algorithm generalizes an algorithm of Kadria et al. [SODA'22] that computes a cycle of length at most 4 ⌈g/2⌉ - 2 ⌊ε⌈g/2⌉⌋ in Õ(n^{1 + 1/(2 - ε)}) time. Kadria et al. presented also an algorithm that finds a cycle of length at most 2𝓁 ⌈g/2⌉ in Õ(n^{1 + 1/(𝓁)}) time, where 𝓁 must be an integer. Our algorithm generalizes this algorithm, as well, by replacing the integer parameter 𝓁 in the running time exponent with a real-valued parameter 𝓁 - ε, thereby offering greater flexibility in parameter selection and enabling a broader spectrum of combinations between running times and cycle lengths. We also show that for sparse graphs a better tradeoff is possible, by presenting an Õ(𝓁⋅ m^{1+ 1/(𝓁-ε)}) time randomized algorithm that returns a cycle of length at most 2𝓁(⌊(g-1)/2⌋) - 2(⌊ε⌊(g-1)/2⌋⌋+1), where 𝓁 ≥ 3 is an integer and ε ∈ [0,1), for every graph with g = polylog(n). To obtain our algorithms we develop several techniques and introduce a formal definition of hybrid cycle detection algorithms. Both may prove useful in broader contexts, including other cycle detection and approximation problems. Among our techniques is a new cycle searching technique, in which we search for a cycle from a given vertex and possibly all its neighbors in linear time. Using this technique together with more ideas we develop two hybrid algorithms. The first allows us to obtain an Õ(m^{2-2/(⌈g/2⌉+1))-time, (+1)-approximation of g. The second is used to obtain our Õ(𝓁⋅ n^{1+ 1/(𝓁-ε)})-time and Õ(𝓁⋅ m^{1+ 1/(𝓁-ε)})-time approximation algorithms.

Cite as

Liam Roditty and Plia Trabelsi. New Algorithms for Girth and Cycle Detection. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{roditty_et_al:LIPIcs.SWAT.2026.38,
  author =	{Roditty, Liam and Trabelsi, Plia},
  title =	{{New Algorithms for Girth and Cycle Detection}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{38:1--38: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.38},
  URN =		{urn:nbn:de:0030-drops-260742},
  doi =		{10.4230/LIPIcs.SWAT.2026.38},
  annote =	{Keywords: Graph algorithms, All pairs shortest path, Girth, Cycle approximation}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.8

Submodular Max-Min Allocation Under Identical Valuations

Authors: Kimon Boehmer

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

Abstract

In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4-approximation, improving the previously best factor of 10/27 ≈ 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in k given matroids, we derive a 𝒪(k)-estimation algorithm for max-min allocation subject to k matroid constraints under identical valuations.

Cite as

Kimon Boehmer. Submodular Max-Min Allocation Under Identical Valuations. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{boehmer:LIPIcs.SWAT.2026.8,
  author =	{Boehmer, Kimon},
  title =	{{Submodular Max-Min Allocation Under Identical Valuations}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{8:1--8: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.8},
  URN =		{urn:nbn:de:0030-drops-260446},
  doi =		{10.4230/LIPIcs.SWAT.2026.8},
  annote =	{Keywords: Submodularity, Approximation algorithms, Allocation, Configuration LP}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.9

QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes

Authors: Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski

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

Abstract

We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (MWIS) in graphs with a bounded number of pairwise vertex-disjoint and non-adjacent long induced cycles. More formally, for every fixed s and t, we show a QPTAS for MWIS in graphs that exclude sC_t as an induced minor. Combining this with known results, we obtain a QPTAS for the problem of finding a largest induced subgraph of bounded treewidth with given hereditary property definable in Counting Monadic Second Order Logic, in the same classes of graphs. This is a step towards a conjecture of Gartland and Lokshtanov which asserts that for any planar graph H, graphs that exclude H as an induced minor admit a polynomial-time algorithm for the latter problem. This conjecture is notoriously open and even its weaker variants are confirmed only for very restricted graphs H.

Cite as

Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski. QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.SWAT.2026.9,
  author =	{Bonnet, \'{E}douard and Czy\.{z}ewska, Jadwiga and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{9:1--9:14},
  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.9},
  URN =		{urn:nbn:de:0030-drops-260454},
  doi =		{10.4230/LIPIcs.SWAT.2026.9},
  annote =	{Keywords: independent set, long holes, QPTAS, induced subgraphs}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.15

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming

Authors: Avinandan Das

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

Abstract

This paper investigates the semi-streaming complexity of k-partial coloring, a generalization of proper graph coloring. For k ≥ 1, a k-partial coloring requires that each vertex v in an n-node graph is assigned a color such that at least min{k, deg(v)} of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, k-partial (k+1)-coloring and k-partial k-coloring generalize (Δ+1)-proper coloring and Δ-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA 2019] and Assadi, Kumar, and Mittal [TheoretiCS 2023] show that both (Δ+1)-proper coloring and Δ-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold: while k-partial (k+1)-coloring admits a one-pass randomized semi-streaming algorithm, the k-partial k-coloring remains semi-streaming intractable, effectively demonstrating a "dichotomy of one color" in the streaming model.

Cite as

Avinandan Das. One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{das:LIPIcs.SWAT.2026.15,
  author =	{Das, Avinandan},
  title =	{{One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{15:1--15:16},
  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.15},
  URN =		{urn:nbn:de:0030-drops-260515},
  doi =		{10.4230/LIPIcs.SWAT.2026.15},
  annote =	{Keywords: Graph Coloring, Semi-streaming algorithms, Lower bounds}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.16

Online Hitting Set for Axis-Aligned Squares

Authors: Minati De, Satyam Singh, and Csaba D. Tóth

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

Abstract

Given a set P of n points in the plane and a sequence of axis-aligned squares that arrive in an online fashion, the online hitting set problem consists of maintaining, by adding new points from P if necessary, a hitting set H ⊆ P, which contains at least one point in every input square that has already arrived. We present an O(log n)-competitive deterministic algorithm for this problem. The competitive ratio is the best possible, apart from constant factors. In fact, this is the first O(log n)-competitive algorithm for the online hitting set problem that works for geometric objects of arbitrary sizes (i.e., unbounded scaling factors) in the plane. We further generalize this result to positive homothets of a polygon with k ≥ 3 vertices in the plane and provide an O(k²log n)-competitive algorithm.

Cite as

Minati De, Satyam Singh, and Csaba D. Tóth. Online Hitting Set for Axis-Aligned Squares. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.SWAT.2026.16,
  author =	{De, Minati and Singh, Satyam and T\'{o}th, Csaba D.},
  title =	{{Online Hitting Set for Axis-Aligned Squares}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-260528},
  doi =		{10.4230/LIPIcs.SWAT.2026.16},
  annote =	{Keywords: axis-aligned squares, hitting set, homothets of a polygon, online algorithm}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.17

Incremental Strongly Connected Components with Predictions

Authors: Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, and Nathan Vosburg

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

Abstract

Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the n vertices of a graph are known a priori and the m directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.

Cite as

Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, and Nathan Vosburg. Incremental Strongly Connected Components with Predictions. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.SWAT.2026.17,
  author =	{Deng, Ronald and McCauley, Samuel and Niaparast, Aidin and Niaparast, Helia and Ptak, Bennett and Quintanilla, Shirel and Singh, Shikha and Vosburg, Nathan},
  title =	{{Incremental Strongly Connected Components with Predictions}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{17:1--17:16},
  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.17},
  URN =		{urn:nbn:de:0030-drops-260530},
  doi =		{10.4230/LIPIcs.SWAT.2026.17},
  annote =	{Keywords: algorithms with predictions, learning augmented algorithms, incremental graph algorithms, strongly connected components, data structures}
}

@InProceedings{deng_et_al:LIPIcs.SWAT.2026.17,
  author =	{Deng, Ronald and McCauley, Samuel and Niaparast, Aidin and Niaparast, Helia and Ptak, Bennett and Quintanilla, Shirel and Singh, Shikha and Vosburg, Nathan},
  title =	{{Incremental Strongly Connected Components with Predictions}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{17:1--17:16},
  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.17},
  URN =		{urn:nbn:de:0030-drops-260530},
  doi =		{10.4230/LIPIcs.SWAT.2026.17},
  annote =	{Keywords: algorithms with predictions, learning augmented algorithms, incremental graph algorithms, strongly connected components, data structures}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.13

Faster Algorithms for Shortest Unique or Absent Substrings

Authors: Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis, Hilde Verbeek, and Wiktor Zuba

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

Abstract

We revisit two well-known algorithmic problems on strings: computing a shortest unique substring (SUS) and a shortest absent substring (SAS) in a string S of length n. Both problems admit folklore 𝒪(n)-time solutions using the suffix tree of S. However, for small alphabets, this complexity is not necessarily optimal in the word RAM model, where a string of length n over alphabet [0,σ) can be stored in 𝒪(n log σ/log n) space and read in 𝒪(n log σ/log n) time. We present an 𝒪(n log σ/√{log n})-time algorithm for computing a SUS in S. This algorithm decomposes the problem according to the length and the period of the sought substring and uses several tools and techniques, such as synchronizing sets, the analysis of runs, and wavelet trees, to reduce the computation of a SUS to a simple geometric problem. Further, we adapt this algorithm and combine it with an efficient construction of de Bruijn sequences in order to obtain an 𝒪(n log σ/√{log n})-time algorithm for computing a SAS in S.

Cite as

Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis, Hilde Verbeek, and Wiktor Zuba. Faster Algorithms for Shortest Unique or Absent Substrings. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.SWAT.2026.13,
  author =	{Charalampopoulos, Panagiotis and Mohamed, Manal and Pissis, Solon P. and Verbeek, Hilde and Zuba, Wiktor},
  title =	{{Faster Algorithms for Shortest Unique or Absent Substrings}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{13:1--13:19},
  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.13},
  URN =		{urn:nbn:de:0030-drops-260493},
  doi =		{10.4230/LIPIcs.SWAT.2026.13},
  annote =	{Keywords: string algorithms, unique substrings, absent substrings, absent words}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.10

Robotic Arm Rotation: Standing up Is Harder Than You Think

Authors: Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig

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

Abstract

We study motion-planning problems for planar robotic arms that rotate around fixed centers while avoiding collisions. In the SM-RAMP model, each unit-length arm may rotate at most once; the question is whether all arms can be rotated to the vertical position. We resolve an open problem of Bousquet et al. [Bousquet et al., 2026] by proving that SM-RAMP is NP-complete, even in the horizontal-to-vertical setting. Our hardness proof uses a structural analysis of rotation-propagation chains and introduces a combinatorial abstraction of independent interest, the Lighthouse Propagation problem, which we show is itself NP-complete. We then consider the multi-move variant MM-RAMP, where each arm may rotate multiple times among a fixed set of allowed angles (or orientations). We prove that MM-RAMP is PSPACE-complete even when each arm has only a few allowed angles, in sharp contrast with the single-move case. Finally, we give two fixed-parameter tractable algorithms: for MAX-SM-RAMP parameterized by the number k of arms to be made vertical, and for 2A-MM-RAMP (restricted to horizontal and vertical) parameterized by the number 𝓁 of allowed rotations.

Cite as

Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig. Robotic Arm Rotation: Standing up Is Harder Than You Think. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.SWAT.2026.10,
  author =	{Bousquet, Nicolas and Connor, Frank and El Sabeh, Remy and Langevin, Louis-Roy and Mouawad, Amer E. and Nishimura, Naomi and Totschnig, Agnes},
  title =	{{Robotic Arm Rotation: Standing up Is Harder Than You Think}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-260467},
  doi =		{10.4230/LIPIcs.SWAT.2026.10},
  annote =	{Keywords: search, optimization, robotics, robotic arms, parameterized complexity, computational geometry, combinatorial reconfiguration}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.12

Strategy Repair in Reachability Games via a Graph Quotientation

Authors: Tiziana Calamoneri, Pierre Gaillard, Giacomo Paesani, and Giuseppe Perelli

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

Abstract

Reachability Games over graphs (RGs) are a powerful modelling tool for synthesis and planning. The solutions to RGs are strategies that are used in program design. Sometimes, due to model deviation at execution time, specification updates, or simply a bug, the strategy provided as a solution to an RG no longer works. Strategy Repair aims to solve this problem by adjusting strategies with a minimum number of modifications. Such a minimisation requirement is motivated by the costs that one may incur when implementing the new strategy. To minimise implementation costs, one wants to reuse as much of the provided strategy as possible. In the literature, Strategy Repair has been investigated from both theoretical and practical perspectives. First, it has been shown to be NP-complete. Second, two algorithmic approaches have been proposed to tackle the problem in practice, one provides an optimal solution, the other an approximated solution. Both approaches underutilise the graph-theoretical properties of games, which could significantly improve their performance and accuracy (in the case of approximation algorithms). This paper provides a graph-theoretic characterisation of Strategy Repair that provably improves every algorithmic approach to solving the problem. It does so by introducing a new notion of quotient graph that allows us to identify and merge those vertices that are equivalent from the perspective of every solution to the problem. This way, solving Strategy Repair can be done in a reduced instance, which we call the quotient game. The approach not only reduces the problem’s input size, but also improves the effectiveness of MustFix, an optimisation condition previously introduced for the problem. Besides the theoretical characterisation, we test our approach empirically by running experiments to demonstrate improvements over the quotient graph approach.

Cite as

Tiziana Calamoneri, Pierre Gaillard, Giacomo Paesani, and Giuseppe Perelli. Strategy Repair in Reachability Games via a Graph Quotientation. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{calamoneri_et_al:LIPIcs.SWAT.2026.12,
  author =	{Calamoneri, Tiziana and Gaillard, Pierre and Paesani, Giacomo and Perelli, Giuseppe},
  title =	{{Strategy Repair in Reachability Games via a Graph Quotientation}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{12:1--12:16},
  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.12},
  URN =		{urn:nbn:de:0030-drops-260481},
  doi =		{10.4230/LIPIcs.SWAT.2026.12},
  annote =	{Keywords: Reachability Games, Strategy Repair, Strategic Reasoning, Automated Reasoning}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.7

On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons

Authors: Mark de Berg, Prosenjit Bose, and Leonidas Theocharous

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

Abstract

Many algorithmic problems can be solved (almost) as efficiently in metric spaces of bounded doubling dimension as in Euclidean space. Unfortunately, the metric space defined by points in a simple polygon equipped with the geodesic distance does not necessarily have bounded doubling dimension. We therefore study the doubling dimension of fat polygons, for two well-known fatness definitions. We prove that locally-fat simple polygons do not always have bounded doubling dimension, while any (α,β)-covered polygon does have bounded doubling dimension (even if it has holes). We also study the perimeter of geodesically convex sets in (α,β)-covered polygons (possibly with holes), and show that this perimeter is at most a constant times the Euclidean diameter of the set. Using these two results, we obtain new results for several problems on (α,β)-covered polygons, including an algorithm that computes the closest pair of a set of m points in an (α,β)-covered polygon with n vertices that runs in O(n + mlog n) expected time.

Cite as

Mark de Berg, Prosenjit Bose, and Leonidas Theocharous. On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SWAT.2026.7,
  author =	{de Berg, Mark and Bose, Prosenjit and Theocharous, Leonidas},
  title =	{{On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{7:1--7:16},
  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.7},
  URN =		{urn:nbn:de:0030-drops-260439},
  doi =		{10.4230/LIPIcs.SWAT.2026.7},
  annote =	{Keywords: Fat polygons, doubling dimension}
}

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}
}

166 Search Results for "Fraigniaud, Pierre"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message