DROPS

Volume

LIPIcs, Volume 57

24th Annual European Symposium on Algorithms (ESA 2016)

ESA 2016, August 22-24, 2016, Aarhus, Denmark

Editors: Piotr Sankowski and Christos Zaroliagis

Document

DOI: 10.4230/LIPIcs.SEA.2026.26

Engineering Algorithms for Dynamic Greedy Set Cover

Authors: Amitai Uzrad

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.

Cite as

Amitai Uzrad. Engineering Algorithms for Dynamic Greedy Set Cover. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uzrad:LIPIcs.SEA.2026.26,
  author =	{Uzrad, Amitai},
  title =	{{Engineering Algorithms for Dynamic Greedy Set Cover}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26},
  URN =		{urn:nbn:de:0030-drops-260308},
  doi =		{10.4230/LIPIcs.SEA.2026.26},
  annote =	{Keywords: Dynamic graphs, set cover, recourse}
}

Document

DOI: 10.4230/LIPIcs.CPM.2026.20

Longest Common Extension of a Dynamic String in Parallel Constant Time

Authors: Daniel Alexander Albert

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

Abstract

A longest common extension (LCE) query on a string computes the length of the longest common suffix or prefix at two given positions. A dynamic LCE algorithm maintains a data structure that allows efficient LCE queries on a string that can change via character insertions and deletions. A dynamic parallel constant-time algorithm is presented that can maintain LCE queries on a common CRCW PRAM with 𝒪(n^ε) work, for any ε > 0. The algorithm maintains a string synchronizing sets hierarchy, which it uses to answer substring equality queries, which it in turn uses to answer LCE queries. To achieve constant runtime, the algorithm allows parts of its information to become outdated by up to log n log^* n updates. It answers queries by combining this slightly outdated information with a list of the recent changes. Two applications of this dynamic LCE algorithm are shown. Firstly, a dynamic parallel constant-time algorithm can maintain membership in a Dyck language D_k, k > 0 with 𝒪(n^ε) work for any ε > 0. Secondly, a dynamic parallel constant-time algorithm can maintain squares with 𝒪(n^ε) work for any ε > 0.

Cite as

Daniel Alexander Albert. Longest Common Extension of a Dynamic String in Parallel Constant Time. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{albert:LIPIcs.CPM.2026.20,
  author =	{Albert, Daniel Alexander},
  title =	{{Longest Common Extension of a Dynamic String in Parallel Constant Time}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{20:1--20:21},
  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.20},
  URN =		{urn:nbn:de:0030-drops-259467},
  doi =		{10.4230/LIPIcs.CPM.2026.20},
  annote =	{Keywords: Dynamic Strings, Work, Parallel Constant Time, Longest Common Extension, Longest Common Prefix}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.22

Search-Space Reduction for Boolean MinCSPs via Essential Constraints

Authors: Bart M. P. Jansen and Ruben F. A. Verhaegh

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

Abstract

For a fixed set ℱ of Boolean constraint types, a MinCSP(ℱ)-instance consists of a formula F that applies m constraints from ℱ to a set of n Boolean variables. The goal is to remove a minimum subset of constraint applications from F to make the remaining formula satisfiable. Previous work characterized how the choice of ℱ affects its polynomial-time solvability and approximability. We extend a recently introduced preprocessing framework for graph problems to the problem above. Rephrased in the context of CSPs, this framework defines a constraint application from a given formula F as c-essential if it is contained in all c-approximate solutions to F. Being able to efficiently detect these essential parts of a solution reduces the search space of any follow-up FPT algorithms parameterized by the solution size and yields an immediate asymptotic improvement to the runtime of such algorithms. In this work, we present a dichotomy theorem that distinguishes constraint sets ℱ for which c_ℱ-essential constraint applications can be detected efficiently for some c_{ℱ} ∈ 𝒪(1), from those for which this task is intractable under established complexity-theoretic conjectures. Our results show that for any set ℱ of bijunctive constraints, there is a polynomial-time algorithm that detects 𝒪(1)-essential constraint applications. This contrasts the fact that constant-factor approximating a bijunctive MinCSP(ℱ)-problem is intractable under the Unique Games Conjecture.

Cite as

Bart M. P. Jansen and Ruben F. A. Verhaegh. Search-Space Reduction for Boolean MinCSPs via Essential Constraints. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SWAT.2026.22,
  author =	{Jansen, Bart M. P. and Verhaegh, Ruben F. A.},
  title =	{{Search-Space Reduction for Boolean MinCSPs via Essential Constraints}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-260586},
  doi =		{10.4230/LIPIcs.SWAT.2026.22},
  annote =	{Keywords: fixed-parameter tractability, constraint satisfaction problems}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.24

Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support

Authors: Reilly Browne and Hsien-Chih Chang

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

Abstract

Given an unweighted graph G, the minimum r-dominating set problem asks for a subset of vertices S of the smallest cardinality, such that every vertex in G is within radius r to some vertex in S. While the r-dominating set problem on planar graph admits PTAS from Baker’s shifting/layering technique when r is a constant, the problem becomes significantly harder when r can depend on n. In fact, under Exponential-Time Hypothesis, Fox-Epstein ηl [SODA 2019] observed that no efficient PTAS can exist for the unbounded r-dominating set problem on planar graphs. One may consider even harder weighted-variant known as the vertex-weighted metric r-dominating set, where edges are associated with lengths, and every vertex is associated with a positive-valued weight, and the goal is to compute an r-dominating set with minimum total weight. As a result, people resorted to bicriteria algorithms by allowing the returned solution to use radius-(1+ε)r balls instead, in addition to the total weight being a 1+ε approximation to the optimal value. We establish the first single-criteria polynomial-time O(1)-approximation algorithm for the vertex-weighted metric r-dominating set problem on planar graphs when r is part of the input, and can be arbitrarily large compared to n. Our new (single-criteria) O(1)-approximation algorithm uses the quasi-uniformity sampling technique of Chan et al. [SODA 2012] by bounding the shallow cell complexity of the (unbounded) radius-r ball system to be linear in n. To this end we have two technical innovations: 1) The discrete ball system on planar graphs are neither pseudodisks nor have well-defined boundaries for standard union-complexity arguments. We construct a support graph for arbitrary distance ball systems as contractions of Voronoi cells; the sparseness comes as a byproduct. 2) We present an assignment of each depth-(≥3) cell to a unique 3-tuple of ball centers. This allows us to use standard Clarkson-Shor techniques to reduce the counting to cells of depth exactly 3, which we prove to be size O(n) by a novel geometric argument based on our support being a Voronoi contraction.

Cite as

Reilly Browne and Hsien-Chih Chang. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{browne_et_al:LIPIcs.SoCG.2026.24,
  author =	{Browne, Reilly and Chang, Hsien-Chih},
  title =	{{Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-258300},
  doi =		{10.4230/LIPIcs.SoCG.2026.24},
  annote =	{Keywords: Minimum dominating set, planar graphs, shallow cell complexity}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.13

Dynamic Light Spanners in Doubling Metrics

Authors: Sujoy Bhore, Jonathan Conroy, and Arnold Filtser

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

Abstract

A t-spanner of a point set X in a metric space (𝒳, δ) is a graph G with vertex set P such that, for any pair of points u,v ∈ X, the distance between u and v in G is at most t times δ(u,v). We study the problem of maintaining a spanner for a dynamic point set X - that is, when X undergoes a sequence of insertions and deletions - in a metric space of constant doubling dimension. For any constant ε > 0, we maintain a (1+ε)-spanner of P whose total weight remains within a constant factor of the weight of the minimum spanning tree of X. Each update (insertion or deletion) can be performed in poly(log Φ) time, where Φ denotes the aspect ratio of X. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space.

Cite as

Sujoy Bhore, Jonathan Conroy, and Arnold Filtser. Dynamic Light Spanners in Doubling Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.13,
  author =	{Bhore, Sujoy and Conroy, Jonathan and Filtser, Arnold},
  title =	{{Dynamic Light Spanners in Doubling Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{13:1--13:16},
  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.13},
  URN =		{urn:nbn:de:0030-drops-258193},
  doi =		{10.4230/LIPIcs.SoCG.2026.13},
  annote =	{Keywords: Dynamic data structures, spanners, light-weight, Euclidean metrics, doubling metrics}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.25

Computational Complexity of Swish Is Solved

Authors: Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, and Yutaro Yamaguchi

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Swish is a card game in which players are given cards having symbols (hoops and balls), and find a valid superposition of cards, called a "swish." Dailly, Lafourcade, and Marcadet (FUN 2024) studied a generalized version of Swish and showed that the problem is solvable in polynomial time with one symbol per card, while it is NP-complete with three or more symbols per card. In this paper, we resolve the previously open case of two symbols per card, which corresponds to the original game. We show that Swish is NP-complete for this case. Specifically, we prove the NP-hardness when the allowed transformations of cards are restricted to a single (horizontal or vertical) flip or 180-degree rotation, and extend the results to the original setting allowing all three transformations. In contrast, when neither transformation is allowed, we present a polynomial-time algorithm. Combining known and our results, we establish a complete characterization of the computational complexity of Swish with respect to both the number of symbols per card and the allowed transformations.

Cite as

Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, and Yutaro Yamaguchi. Computational Complexity of Swish Is Solved. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{horiyama_et_al:LIPIcs.FUN.2026.25,
  author =	{Horiyama, Takashi and Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Suzuki, Akira and Uehara, Ryuhei and Yamaguchi, Yutaro},
  title =	{{Computational Complexity of Swish Is Solved}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.25},
  URN =		{urn:nbn:de:0030-drops-257448},
  doi =		{10.4230/LIPIcs.FUN.2026.25},
  annote =	{Keywords: Swish, Computational complexity, Matching, Parity-constrained cycles}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.39

Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions

Authors: Keerti Choudhary, Amit Kumar, and Lakshay Saggi

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

Abstract

We study the 2-Disjoint Shortest Paths (2-DSP) problem: given a directed weighted graph and two terminal pairs (s₁,t₁) and (s₂,t₂), decide whether there exist vertex-disjoint shortest paths between each pair. Building on recent advances in disjoint shortest paths for DAGs and undirected graphs (Akmal et al. 2024), we present an O(mn log n)-time algorithm for this problem in weighted directed graphs that do not contain negative or zero weight cycles. This algorithm presents a significant improvement over the previously known O(m⁵n)-time bound (Berczi et al. 2017). Our approach exploits the algebraic structure of polynomials that enumerate shortest paths between terminal pairs. A key insight is that these polynomials admit a recursive decomposition, enabling efficient evaluation via dynamic programming over fields of characteristic two. Furthermore, we demonstrate how to report the corresponding paths in O(mn² log n)-time. In addition, we extend our techniques to a more general setting: given two terminal pairs (s₁, t₁) and (s₂, t₂) in a directed graph, find the minimum possible number of vertex intersections between any shortest path from s₁ to t₁ and s₂ to t₂. We call this the Minimum 2-Disjoint Shortest Paths (Min-2-DSP) problem. We provide in this paper the first efficient algorithm for this problem, including an O(m² n³)-time algorithm for directed graphs with positive edge weights, and an O(m+n)-time algorithm for DAGs and undirected graphs. Moreover, if the number of intersecting vertices is at least one, we show that it is possible to report the paths in the same O(m+n)-time. This is somewhat surprising, as there is no known o(mn) time algorithm for explicitly reporting the paths if they are vertex-disjoint, and is left as an open problem in (Akmal et al. 2024).

Cite as

Keerti Choudhary, Amit Kumar, and Lakshay Saggi. Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.ITCS.2026.39,
  author =	{Choudhary, Keerti and Kumar, Amit and Saggi, Lakshay},
  title =	{{Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-253267},
  doi =		{10.4230/LIPIcs.ITCS.2026.39},
  annote =	{Keywords: Disjoint paths, Disjoint shortest paths, Algebraic graph algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.5

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs

Authors: Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi

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

Abstract

This paper addresses the problem of designing fault-tolerant data structures for the (s,t)-max-flow and (s,t)-min-cut problems in unweighted directed graphs. Given a directed graph G = (V, E) with a designated source s, sink t, and an (s,t)-max-flow of value λ, we present constructions for max-flow and min-cut sensitivity oracles, and introduce the concept of a fault-tolerant flow family, which may be of independent interest. Our main contributions are as follows. 1) Fault-Tolerant Flow Family: We construct a family ℬ of 2λ+1 (s,t)-flows such that for every edge e, ℬ contains an (s,t)-max-flow of G-e. This covering property is tight up to constants for single failures and provably cannot extend to comparably small families for k ≥ 2, where we show an Ω(n) lower bound on the family size, independent of λ. 2) Max-Flow Sensitivity Oracle: Using the fault-tolerant flow family, we construct a single as well as dual-edge sensitivity oracle for (s,t)-max-flow that requires only O(λ n) space. Given any set F of up to two failing edges, the oracle reports the updated max-flow value in G-F in O(n) time. Additionally, for the single-failure case, the oracle can determine in constant time whether the flow through an edge x changes when another edge e fails. 3) Min-Cut Sensitivity Oracle for Dual Failures: Recently, Baswana et al. (ICALP’22) designed an O(n²)-sized oracle for answering (s,t)-min-cut size queries under dual edge failures in constant time, along with a matching lower bound. We extend this by focusing on graphs with small min-cut values λ, and present a more compact oracle of size O(λ n) that answers such min-cut size queries in constant time and reports the corresponding (s,t)-min-cut partition in O(n) time. We also show that the space complexity of our oracle is asymptotically optimal in this setting. 4) Min-Cut Sensitivity Oracle for Multiple Failures: We extend our results to the general case of k edge failures. For any graph with (s,t)-min-cut of size λ, we construct a k-fault-tolerant min-cut oracle with space complexity O_{λ,k}(n log n) that answers min-cut size queries in O_{λ,k}(log n) time. This also leads to improved fault-tolerant (s,t)-reachability oracles, achieving O(n log n) space and O(log n) query time for up to k = O(1) edge failures.

Cite as

Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi. Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahi_et_al:LIPIcs.ITCS.2026.5,
  author =	{Ahi, Mridul and Choudhary, Keerti and Pande, Shlok and Pushpraj and Saggi, Lakshay},
  title =	{{Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{5:1--5:24},
  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.5},
  URN =		{urn:nbn:de:0030-drops-252920},
  doi =		{10.4230/LIPIcs.ITCS.2026.5},
  annote =	{Keywords: Fault tolerance, Data structures, Minimum cuts, Maximum flows}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.102

Smoothed Analysis of Dynamic Graph Algorithms

Authors: Uri Meir and Ami Paz

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

Abstract

Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger, Krinninger, Nanongkai and Saranurak, STOC 2015; Larsen and Yu, FOCS 2023). As worst-case analysis (adversarial inputs) may lead to the necessity of high running times, a natural question arises: in which cases are high running times really necessary, and in which cases these inputs merely manifest unique pathological cases? Early attempts to tackle this question were made by Nikoletseas, Reif, Spirakis and Yung (ICALP 1995) and by Alberts and Henzinger (Algorithmica 1998), who considered models with very little adversarial control over the inputs, and showed fast algorithms exist for them. The question was then overlooked for decades, until Henzinger, Lincoln and Saha (SODA 2022) recently addressed uniformly random inputs, and presented algorithms and impossibility results for several subgraph counting problems. To tackle the above question more thoroughly, we employ smoothed analysis, a celebrated framework introduced by Spielman and Teng (J. ACM, 2004). An input is proposed by an adversary but then a noisy version of it is processed by the algorithm instead. This model of inputs is parameterized by the amount of adversarial control, and fully interpolates between worst-case inputs and a uniformly random input. Doing so, we extend impossibility results for some problems to the smoothed model with only a minor quantitative loss. That is, we show that partially-adversarial inputs suffice to impose high running times for certain problems. In contrast, we show that other problems become easy even with the slightest amount of noise. In addition, we study the interplay between the adversary and the noise, leading to three natural models of smoothed inputs, for which we show a hierarchy of increasing difficulty stretching between the average-case and the worst-case complexities.

Cite as

Uri Meir and Ami Paz. Smoothed Analysis of Dynamic Graph Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.ITCS.2026.102,
  author =	{Meir, Uri and Paz, Ami},
  title =	{{Smoothed Analysis of Dynamic Graph Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{102:1--102: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.102},
  URN =		{urn:nbn:de:0030-drops-253896},
  doi =		{10.4230/LIPIcs.ITCS.2026.102},
  annote =	{Keywords: Dynamic graph algorithms, Smoothed analysis, Shortest paths}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2025.16

Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

Document

DOI: 10.4230/LIPIcs.DISC.2025.40

On the Randomized Locality of Matching Problems in Regular Graphs

Authors: Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

The main goal in distributed symmetry-breaking is to understand the locality of problems: the radius of the neighborhood that a node must explore to determine its part of a global solution. In this work, we study the locality of matching problems in the family of regular graphs, which is one of the main benchmarks for establishing lower bounds on the locality of symmetry-breaking problems, as well as for obtaining classification results. Our main results are summarized as follows: 1) Approximate matching: We develop randomized algorithms to show that (1 + ε)-approximate matching in regular graphs is truly local, i.e., the locality depends only on ε and is independent of all other graph parameters. Furthermore, as long as the degree Δ is not very small (namely, as long as Δ ≥ poly(1/ε)), this dependence is only logarithmic in 1/ε. This stands in sharp contrast to maximal matching in regular graphs which requires some dependence on the number of nodes n or the degree Δ. 2) Maximal matching: Our techniques further allow us to establish a strong separation between the node-averaged complexity and worst-case complexity of maximal matching in regular graphs, by showing that the former is only O(1). Central to our main technical contribution is a novel martingale-based analysis for the ≈ 40-year-old algorithm by Luby. In particular, our analysis shows that applying one round of Luby’s algorithm on the line graph of a Δ-regular graph results in an almost Δ/2-regular graph.

Cite as

Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang. On the Randomized Locality of Matching Problems in Regular Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khoury_et_al:LIPIcs.DISC.2025.40,
  author =	{Khoury, Seri and Purohit, Manish and Schild, Aaron and Wang, Joshua R.},
  title =	{{On the Randomized Locality of Matching Problems in Regular Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.40},
  URN =		{urn:nbn:de:0030-drops-248570},
  doi =		{10.4230/LIPIcs.DISC.2025.40},
  annote =	{Keywords: regular graphs, maximum matching, augmenting paths, distributed algorithms, Luby’s algorithm, martingales}
}

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.74

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications

Authors: Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka

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

Abstract

Min-plus matrix multiplication is a fundamental tool for designing algorithms operating on distances in graphs and different problems solvable by dynamic programming. We know that, assuming the APSP hypothesis, no subcubic-time algorithm exists for the case of general matrices. However, in many applications the matrices admit certain structural properties that can be used to design faster algorithms. For example, when considering a planar graph, one often works with a Monge matrix A, meaning that the density matrix A^◻ has non-negative entries, that is, A^◻_{i,j} := A_{i+1,j} + A_{i,j+1} - A_{i,j} -A_{i+1,j+1} ≥ 0. The min-plus product of two n×n Monge matrices can be computed in 𝒪(n²) time using the famous SMAWK algorithm. In applications such as longest common subsequence, edit distance, and longest increasing subsequence, the matrices are even more structured, as observed by Tiskin [J. Discrete Algorithms, 2008]: they are (or can be converted to) simple unit-Monge matrices, meaning that the density matrix is a permutation matrix and, furthermore, the first column and the last row of the matrix consist of only zeroes. Such matrices admit an implicit representation of size 𝒪(n) and, as shown by Tiskin [SODA 2010 & Algorithmica, 2015], their min-plus product can be computed in 𝒪(nlog n) time. Russo [SPIRE 2010 & Theor. Comput. Sci., 2012] identified a general structural property of matrices that admit such efficient representation and min-plus multiplication algorithms: the core size δ, defined as the number of non-zero entries in the density matrices of the input and output matrices. He provided an adaptive implementation of the SMAWK algorithm that runs in 𝒪((n+δ)log³ n) or 𝒪((n+δ)log² n) time (depending on the representation of the input matrices). In this work, we further investigate the core size as the parameter that enables efficient min-plus matrix multiplication. On the combinatorial side, we provide a (linear) bound on the core size of the product matrix in terms of the core sizes of the input matrices. On the algorithmic side, we generalize Tiskin’s algorithm (but, arguably, with a more elementary analysis) to solve the core-sparse Monge matrix multiplication problem in 𝒪(n+δlog δ) ⊆ 𝒪(n + δ log n) time, matching the complexity for simple unit-Monge matrices. As witnessed by the recent work of Gorbachev and Kociumaka [STOC'25] for edit distance with integer weights, our generalization opens up the possibility of speed-ups for weighted sequence alignment problems. Furthermore, our multiplication algorithm is also capable of producing an efficient data structure for recovering the witness for any given entry of the output matrix. This allows us, for example, to preprocess an integer array of size n in Õ(n) time so that the longest increasing subsequence of any sub-array can be reconstructed in Õ(𝓁) time, where 𝓁 is the length of the reported subsequence. In comparison, Karthik C. S. and Rahul [arXiv, 2024] recently achieved 𝒪(𝓁+n^{1/2}polylog n)-time reporting after 𝒪(n^{3/2}polylog n)-time preprocessing.

Cite as

Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ESA.2025.74,
  author =	{Gawrychowski, Pawe{\l} and Gorbachev, Egor and Kociumaka, Tomasz},
  title =	{{Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{74:1--74:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.74},
  URN =		{urn:nbn:de:0030-drops-245427},
  doi =		{10.4230/LIPIcs.ESA.2025.74},
  annote =	{Keywords: Min-plus matrix multiplication, Monge matrix, longest increasing subsequence}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.22

Constructing Long Paths in Graph Streams

Authors: Christian Konrad and Chhaya Trehan

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

132 Search Results for "Sankowski, Piotr"

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

Abstract

Cite as

Thanks for your feedback!

Could not send message