22 Search Results for "Soto, José A."

Document
DOI: 10.4230/LIPIcs.CPM.2026.29
The TAG Array of a Multiple Sequence Alignment

Authors: Jannik Olbrich and Enno Ohlebusch

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

Abstract
Modern genomic analyses increasingly rely on pangenomes, that is, representations of the genome of entire populations. The simplest representation of a pangenome is a set of individual genome sequences. Compared to e.g. sequence graphs, this has the advantage that efficient exact search via indexes based on the Burrows-Wheeler Transform (BWT) is possible, that no chimeric sequences are created, and that the results are not influenced by heuristics. However, such an index may report a match in thousands of positions even if these all correspond to the same locus, making downstream analysis unnecessarily more expensive. For sufficiently similar sequences (e.g. human chromosomes), a multiple sequence alignment (MSA) can be computed. Since an MSA tends to group similar strings in the same columns, it is likely that a string occurring thousands of times in the pangenome can be described by very few columns in the MSA. We describe a method to tag entries in the BWT with the corresponding column in the MSA and develop an index that can map matches in the BWT to columns in the MSA in time proportional to the output. As a by-product, we can project a match to a designated reference genome, a capability that current pangenome aligners lack.
Cite as

Jannik Olbrich and Enno Ohlebusch. The TAG Array of a Multiple Sequence Alignment. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{olbrich_et_al:LIPIcs.CPM.2026.29,
  author =	{Olbrich, Jannik and Ohlebusch, Enno},
  title =	{{The TAG Array of a Multiple Sequence Alignment}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{29:1--29:14},
  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.29},
  URN =		{urn:nbn:de:0030-drops-259555},
  doi =		{10.4230/LIPIcs.CPM.2026.29},
  annote =	{Keywords: Burrows-Wheeler Transform, pattern matching, index data structure, pangenomics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.32
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Authors: Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter

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

Abstract
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values of these parameters can be determined by performing costly queries. The goal is to design an adaptive query strategy that minimizes the query cost incurred in computing an optimal solution. Solving such problems generally requires that we be able to solve the associated verification problem: given the answers to all queries in advance, find a minimum-cost set of queries that certifies an optimal solution to the combinatorial optimization problem. We present a polynomial-time algorithm for verifying a minimum-weight basis of a matroid, where each weight lies in a given uncertainty area. These areas may be finite sets, real intervals, or unions of open and closed intervals, strictly generalizing previous work by Erlebach and Hoffman which only handled the special case of open intervals. Our algorithm introduces new techniques to address the resulting challenges. Verification problems are of particular importance in the area of explorable uncertainty, as the structural insights and techniques used to solve the verification problem often heavily influence work on the corresponding online problem and its stochastic variant. In our case, we use structural results from the verification problem to give a best-possible algorithm for a promise variant of the corresponding adaptive online problem. Finally, we show that our algorithms can be applied to two learning-augmented variants of the minimum-weight basis problem under explorable uncertainty.
Cite as

Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter. Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{diwan_et_al:LIPIcs.STACS.2026.32,
  author =	{Diwan, Haya and Hellerstein, Lisa and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{32:1--32:20},
  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.32},
  URN =		{urn:nbn:de:0030-drops-255216},
  doi =		{10.4230/LIPIcs.STACS.2026.32},
  annote =	{Keywords: Matroid verification, minimum-weight basis, query strategy, uncertainty matroid, explorable uncertainty}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.94
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Authors: Yingxi Li, Ellen Vitercik, and Mingwei Yang

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

Abstract
In the online metric matching problem, n servers and n requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in [0, 1]^d with the Euclidean metric, when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an O(1)-competitive algorithm for d ≠ 2 that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an o(log n) competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the Ω(log n) barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric space of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees.
Cite as

Yingxi Li, Ellen Vitercik, and Mingwei Yang. Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2026.94,
  author =	{Li, Yingxi and Vitercik, Ellen and Yang, Mingwei},
  title =	{{Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{94:1--94:23},
  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.94},
  URN =		{urn:nbn:de:0030-drops-253815},
  doi =		{10.4230/LIPIcs.ITCS.2026.94},
  annote =	{Keywords: Online algorithm, Metric matching, Competitive analysis, Smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.10
Computing in a Faulty Congested Clique

Authors: Keren Censor-Hillel and Pedro Soto

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of O(nlog{n})-bit input per node can be solved in roughly n rounds, where n is the size of the network. This nearly matches the linear upper bound on the complexity of the non-faulty Congested Clique model for such problems, by learning the entire input, and it holds in the faulty model even with a linear number of faults. Our main contribution is that we establish that one can do much better by looking more closely at the computation. Given a deterministic algorithm 𝒜 for the non-faulty Congested Clique model, we show how to transform it into an algorithm 𝒜' for the faulty model, with an overhead that could be as small as some logarithmic-in-n factor, by considering refined complexity measures of 𝒜. As an exemplifying application of our approach, we show that the O(n^{1/3})-round complexity of semi-ring matrix multiplication [Censor{-}Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela, PODC 2015] remains the same up to polylog factors in the faulty model, even if the adversary can fail 99% of the nodes (or any other constant fraction).
Cite as

Keren Censor-Hillel and Pedro Soto. Computing in a Faulty Congested Clique. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2025.10,
  author =	{Censor-Hillel, Keren and Soto, Pedro},
  title =	{{Computing in a Faulty Congested Clique}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.10},
  URN =		{urn:nbn:de:0030-drops-251833},
  doi =		{10.4230/LIPIcs.OPODIS.2025.10},
  annote =	{Keywords: distributed computing, graph algorithms, computing with faults}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.10
A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design

Authors: Caleb Eardley, Dalton Gomez, Ryan Dupuis, Michael Papadopoulos, and Sean Yaw

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
The Multi-Capacity Fixed-Charge Network Flow (MC-FCNF) problem, a generalization of the Fixed-Charge Network Flow problem, aims to assign capacities to edges in a flow network such that a target amount of flow can be hosted at minimum cost. The cost model for both problems dictates that the fixed cost of an edge is incurred for any non-zero amount of flow hosted by that edge. This problem naturally arises in many areas including infrastructure design, transportation, telecommunications, and supply chain management. The MC-FCNF problem is NP-Hard, so solving large instances using exact techniques is impractical. This paper presents a genetic algorithm designed to quickly find high-quality flow solutions to the MC-FCNF problem. The genetic algorithm uses a novel solution representation scheme that eliminates the need to repair invalid flow solutions, which is an issue common to many other genetic algorithms for the MC-FCNF problem. The genetic algorithm’s utility is demonstrated with an evaluation using real-world CO₂ capture, transportation, and storage infrastructure design data. The evaluation results highlight the genetic algorithm’s potential for solving large-scale network design problems.
Cite as

Caleb Eardley, Dalton Gomez, Ryan Dupuis, Michael Papadopoulos, and Sean Yaw. A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eardley_et_al:OASIcs.ATMOS.2025.10,
  author =	{Eardley, Caleb and Gomez, Dalton and Dupuis, Ryan and Papadopoulos, Michael and Yaw, Sean},
  title =	{{A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{10:1--10:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10},
  URN =		{urn:nbn:de:0030-drops-247661},
  doi =		{10.4230/OASIcs.ATMOS.2025.10},
  annote =	{Keywords: Fixed-Charge Network Flow, Genetic Algorithm, Matheuristic, Infrastructure Design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.6
On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms

Authors: Jens Schlöter

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

Abstract
In the knapsack problem under explorable uncertainty, we are given a knapsack instance with uncertain item profits. Instead of having access to the precise profits, we are only given uncertainty intervals that are guaranteed to contain the corresponding profits. The actual item profit can be obtained via a query. The goal of the problem is to adaptively query item profits until the revealed information suffices to compute an optimal (or approximate) solution to the underlying knapsack instance. Since queries are costly, the objective is to minimize the number of queries. In the offline variant of this problem, we assume knowledge of the precise profits and the task is to compute a query set of minimum cardinality that a third party without access to the profits could use to identify an optimal (or approximate) knapsack solution. We show that this offline variant is complete for the second-level of the polynomial hierarchy, i.e., Σ₂^p-complete, and cannot be approximated within a non-trivial factor unless Σ₂^p = Δ₂^p. Motivated by these strong hardness results, we consider a "resource-augmented" variant of the problem where the requirements on the query set computed by an algorithm are less strict than the requirements on the optimal solution we compare against. More precisely, a query set computed by the algorithm must reveal sufficient information to identify an approximate knapsack solution, while the optimal query set we compare against has to reveal sufficient information to identify an optimal solution. We show that this resource-augmented setting allows interesting non-trivial algorithmic results.
Cite as

Jens Schlöter. On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schloter:LIPIcs.ESA.2025.6,
  author =	{Schl\"{o}ter, Jens},
  title =	{{On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{6:1--6:15},
  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.6},
  URN =		{urn:nbn:de:0030-drops-244740},
  doi =		{10.4230/LIPIcs.ESA.2025.6},
  annote =	{Keywords: Explorable uncertainty, knapsack, queries, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.52
Beating Competitive Ratio 4 for Graphic Matroid Secretary

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski

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

Abstract
One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.
Cite as

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating Competitive Ratio 4 for Graphic Matroid Secretary. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ESA.2025.52,
  author =	{Banihashem, Kiarash and Hajiaghayi, MohammadTaghi and Kowalski, Dariusz R. and Krysta, Piotr and Mittal, Danny and Olkowski, Jan},
  title =	{{Beating Competitive Ratio 4 for Graphic Matroid Secretary}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{52:1--52:16},
  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.52},
  URN =		{urn:nbn:de:0030-drops-245205},
  doi =		{10.4230/LIPIcs.ESA.2025.52},
  annote =	{Keywords: online algorithms, graphic matroids, secretary problem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.67
Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

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

Abstract
We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.
Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67: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.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}
Document
DOI: 10.4230/OASIcs.Programming.2025.6
Exploration and Complexity Management in Graph-Based Programming Environments

Authors: Max Boksem and L. Thomas van Binsbergen

Published in: OASIcs, Volume 134, Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)

Abstract
Programmers often rely on different environments depending on the nature of their tasks. For large-scale software projects, IDEs help manage complexity through structured abstractions like files, modules, and classes, and provide tools for code visualization and navigation. In contrast, exploratory programming tasks - such as data analysis, rapid prototyping, and design space exploration - are better served by interactive environments like REPLs and Notebooks, which support incremental development and immediate feedback. However, these tools tend to prioritize either complexity management or exploration, limiting their effectiveness across contexts. This paper investigates a hybrid graph-based programming environment that bridges these two modes by building on Incremental Graph Code (IGC), a graph-based system for structuring, visualizing, and interacting with source code. We explore how IGC can support both complexity management and exploratory programming through three key features: projectional views for aggregating and navigating interrelated code and documentation, graph-type nodes for encapsulating subgraphs to manage structural complexity, and an exploratory programming view for managing branching executions and promoting experimentation. Together, these features suggest that graph-based environments like IGC can offer a unified platform for both systematic software engineering and dynamic, exploratory development.
Cite as

Max Boksem and L. Thomas van Binsbergen. Exploration and Complexity Management in Graph-Based Programming Environments. In Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025). Open Access Series in Informatics (OASIcs), Volume 134, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boksem_et_al:OASIcs.Programming.2025.6,
  author =	{Boksem, Max and van Binsbergen, L. Thomas},
  title =	{{Exploration and Complexity Management in Graph-Based Programming Environments}},
  booktitle =	{Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)},
  pages =	{6:1--6:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-382-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{134},
  editor =	{Edwards, Jonathan and Perera, Roly and Petricek, Tomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Programming.2025.6},
  URN =		{urn:nbn:de:0030-drops-242906},
  doi =		{10.4230/OASIcs.Programming.2025.6},
  annote =	{Keywords: Graph-based Programming Environments, Exploratory Programming, Complexity Management, Incremental Graph Code (IGC), Projectional Views}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.27
Triangles Improve 0.878 Approximation for Maxcut

Authors: Fredie George, Anand Louis, and Rameesh Paul

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Maxcut is a fundamental problem in graph algorithms, extensively studied for its theoretical and practical significance. The goal is to partition the vertex set of a graph G = (V, E) into disjoint subsets S and V⧵S so as to maximize the number of edges crossing the cut (S,V⧵S). The seminal work of Goemans and Williamson [Goemans and Williamson, 1995] introduced a semidefinite programming (SDP) based algorithm achieving a α_{GW} ≈ 0.87856-approximation for general graphs, guaranteed to be optimal under the Unique Games Conjecture [Khot, 2002; Khot et al., 2007]. We revisit the Goemans–Williamson SDP and prove that the standard Maxcut SDP achieves a (α_{GW} + Ω(1))-approximation whenever the input graph contains Ω(|E|) edge-disjoint triangles. Our analysis builds on classical rounding techniques studied in [Goemans and Williamson, 1995; Zwick, 1999] and introduces a refined understanding of the SDP solution structure in regimes where the previous guarantees are tight. Our result identifies a simple combinatorial property that may be satisfied by many natural graph classes. As applications, we show that unit ball graphs and graphs satisfying a spectral transitivity condition (as studied in [Gupta et al., 2016; Basu et al., 2024]) meet our structural criterion, and therefore we get better than α_{GW} approximation guarantees for them. Our algorithm runs in nearly linear time 𝒪̃(|E|), offering a more practical alternative to the PTAS of [Jansen et al., 2005] for unit ball graphs, which has exponential dependence on the approximation parameter.
Cite as

Fredie George, Anand Louis, and Rameesh Paul. Triangles Improve 0.878 Approximation for Maxcut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 27:1-27:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{george_et_al:LIPIcs.APPROX/RANDOM.2025.27,
  author =	{George, Fredie and Louis, Anand and Paul, Rameesh},
  title =	{{Triangles Improve 0.878 Approximation for Maxcut}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{27:1--27:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.27},
  URN =		{urn:nbn:de:0030-drops-243931},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.27},
  annote =	{Keywords: Approximation Algorithms, Maxcut, Semidefinite Programming, Edge-disjoint Triangles, Unit Ball Graphs, Spectral Triadic Graphs}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.5
On Planar Straight-Line Dominance Drawings

Authors: Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, and Giacomo Ortali

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

Abstract
We study the following question, which has been considered since the 90’s: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, and st-planar graphs in which no face has the left boundary that is a single edge.
Cite as

Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, and Giacomo Ortali. On Planar Straight-Line Dominance Drawings. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.WADS.2025.5,
  author =	{Angelini, Patrizio and Bekos, Michael A. and Di Battista, Giuseppe and Frati, Fabrizio and Grilli, Luca and Ortali, Giacomo},
  title =	{{On Planar Straight-Line Dominance Drawings}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.5},
  URN =		{urn:nbn:de:0030-drops-242361},
  doi =		{10.4230/LIPIcs.WADS.2025.5},
  annote =	{Keywords: st-graphs, dominance drawings, planar straight-line drawings, upward planarity}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.16
An Improved Guillotine Cut for Squares

Authors: Parinya Chalermsook, Axel Kugelmann, Ly Orgo, Sumedha Uniyal, and Minoo Zarsav

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

Abstract
Given a set of n non-overlapping geometric objects, can we separate a constant fraction of them using straight-line cuts that extend from edge to edge? In 1996, Urrutia posed this question for compact convex objects. Pach and Tardos later refuted it for general line segments by constructing a family where any separable subfamily has size at most O (n^{log₃ 2}). However, for axis-parallel rectangles, they provided positive evidence, showing that an Ω(1/log n)-fraction can be separated. This problem naturally arises in geometric approximation algorithms. In particular, when restricting cuts to only orthogonal straight lines, known as a guillotine cut sequence, any bound on the separability ratio directly translates into a clean and simple dynamic programming for computing a maximum independent set of geometric objects. This paper focuses on the case when the objects are squares. For squares of arbitrary sizes, an Ω(1)-fraction can be separated (Abed et al., APPROX 2015), recently improved to 1/40 (and 1/160 ≈ 0.62% for the weighted case) (Khan and Pittu, APPROX 2020). We further improve this bound, showing that a 9/256 ≈ 3.51% can be separated for the weighted case. This result significantly narrows the possible range for squares to [3.51%, 50%]. The key to our improvement is a refined analysis of the existing framework.
Cite as

Parinya Chalermsook, Axel Kugelmann, Ly Orgo, Sumedha Uniyal, and Minoo Zarsav. An Improved Guillotine Cut for Squares. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.WADS.2025.16,
  author =	{Chalermsook, Parinya and Kugelmann, Axel and Orgo, Ly and Uniyal, Sumedha and Zarsav, Minoo},
  title =	{{An Improved Guillotine Cut for Squares}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.16},
  URN =		{urn:nbn:de:0030-drops-242472},
  doi =		{10.4230/LIPIcs.WADS.2025.16},
  annote =	{Keywords: Guillotine cuts, Geometric Approximation Algorithms, Rectangles, Squares}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.48
Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform

Authors: Gabriele Fici and Estéban Gabory

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

Abstract
We define generalized de Bruijn words as those words having a Burrows-Wheeler transform that is a concatenation of permutations of the alphabet. We show that generalized de Bruijn words are in 1-to-1 correspondence with Hamiltonian cycles in the generalized de Bruijn graphs, introduced in the early '80s in the context of network design. When the size of the alphabet is a prime p, we define invertible necklaces as those whose BWT-matrix is non-singular. We show that invertible necklaces of length n correspond to normal bases of the finite field 𝔽_{pⁿ}, and that they form an Abelian group isomorphic to the Reutenauer group RG_pⁿ. Using known results in abstract algebra, we can make a bridge between generalized de Bruijn words and invertible necklaces. In particular, we highlight a correspondence between binary de Bruijn words of order d+1, binary necklaces of length 2^{d} having an odd number of 1’s, invertible BWT matrices of size 2^{d}× 2^{d}, and normal bases of the finite field 𝔽_{2^{2^{d}}}.
Cite as

Gabriele Fici and Estéban Gabory. Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.MFCS.2025.48,
  author =	{Fici, Gabriele and Gabory, Est\'{e}ban},
  title =	{{Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-241555},
  doi =		{10.4230/LIPIcs.MFCS.2025.48},
  annote =	{Keywords: Burrows-Wheeler Transform, Generalized de Bruijn Word, Generalized de Bruijn Graph, Circulant Matrix, Invertible Necklace, Sandpile Group, Reutenauer Group}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.52
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy

Authors: Christoph Grüne and Lasse Wulf

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

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

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

Copy BibTex To Clipboard

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

Authors: Diego Arroyuelo and Gonzalo Navarro

Published in: OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025)

Abstract
Graph databases represent data as a labeled directed graph, where the labels refer to properties that connect the entities represented by their source and target vertices. Queries feature, most prominently, sets of edges where source, target, and/or label can be variables; each instantiation of the variables where all the edges occur in the graph is a solution to the query. Worst-case-optimal algorithms to solve those queries have been devised, but they pose significant space requirements. This overhead has hindered the adoption of worst-case-optimal algorithms in real systems. We show that a representation of the graph based on the extended BWT (eBWT), where each edge is seen as an independent string of length 3 (source, label, target) supports worst-case-optimal algorithms while using almost no extra space on top of the raw data. We then show how the idea is generalized to the relational model, where the strings can be longer than 3 and several eBWTs are needed to obtain worst-case optimality. The aim to minimize the amount of space in that case leads to consider novel eBWT variants, where columns other than the last can be chosen. Finally, we show how the same graph representation can be used to solve other typical queries, like finding graph paths that match regular expressions.
Cite as

Diego Arroyuelo and Gonzalo Navarro. BWT Indexes for Optimal Joins in Graph Databases. In The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 131, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arroyuelo_et_al:OASIcs.Manzini.14,
  author =	{Arroyuelo, Diego and Navarro, Gonzalo},
  title =	{{BWT Indexes for Optimal Joins in Graph Databases}},
  booktitle =	{The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday},
  pages =	{14:1--14:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-390-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{131},
  editor =	{Ferragina, Paolo and Gagie, Travis and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.14},
  URN =		{urn:nbn:de:0030-drops-239222},
  doi =		{10.4230/OASIcs.Manzini.14},
  annote =	{Keywords: Graph databases, Ring index, extended BWT, compact data structures}
}
  • Refine by Type
  • 22 Document/PDF
  • 19 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 14 2025
  • 1 2024
  • 1 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 3 Soto, José A.
  • 2 Chalermsook, Parinya
  • 2 Fici, Gabriele
  • 2 Schlöter, Jens
  • 1 Abed, Fidaa
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs
  • 3 OASIcs
  • 1 TGDK

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Online algorithms
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 Burrows-Wheeler Transform
  • 2 Guillotine cuts
  • 2 Rectangles
  • 2 Squares
  • 2 queries
  • 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