7 Search Results for "Duraj, Lech"

Document
DOI: 10.4230/LIPIcs.ESA.2025.39
Going Beyond Surfaces in Diameter Approximation

Authors: Michał Włodarczyk

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

Abstract
Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+ε)-approximation algorithms with running time poly(1/ε, log n)⋅ n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+ε)-approximation algorithms with the following running times: - 𝒪_h((1/ε)^𝒪(h) ⋅ nlog² n)-time algorithm for graphs excluding an apex graph of size h as a minor, - 𝒪_d((1/ε)^𝒪(d) ⋅ nlog² n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+ε)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time 𝒪_h((1/ε)⁸⋅ nlog nlog W) and query time 𝒪_h((1/ε)²⋅log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.
Cite as

Michał Włodarczyk. Going Beyond Surfaces in Diameter Approximation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.ESA.2025.39,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Going Beyond Surfaces in Diameter Approximation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-245076},
  doi =		{10.4230/LIPIcs.ESA.2025.39},
  annote =	{Keywords: diameter, approximation, distance oracles, graph minors, treewidth}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.109
Faster Diameter Computation in Graphs of Bounded Euler Genus

Authors: Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, and Giannos Stamoulis

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

Abstract
We show that for any fixed integer k ⩾ 0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time 𝒪_k(n^{2-1/25}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪_k(n^{2-1/356} log^{6k} n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K_h-minor-free graphs, but the running time bound is 𝒪_h(n^{2-c_h}) for some constant c_h > 0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter k. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus.
Cite as

Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, and Giannos Stamoulis. Faster Diameter Computation in Graphs of Bounded Euler Genus. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 109:1-109:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kluk_et_al:LIPIcs.ICALP.2025.109,
  author =	{Kluk, Kacper and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and Stamoulis, Giannos},
  title =	{{Faster Diameter Computation in Graphs of Bounded Euler Genus}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{109:1--109:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.109},
  URN =		{urn:nbn:de:0030-drops-234869},
  doi =		{10.4230/LIPIcs.ICALP.2025.109},
  annote =	{Keywords: Diameter, eccentricity, subquadratic algorithms, surface-embeddable graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.51
Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs

Authors: Lech Duraj, Filip Konieczny, and Krzysztof Potępa

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We develop a framework for algorithms finding the diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) subquadratic time complexity. The class of bounded distance VC-dimension graphs is wide, including, e.g. all minor-free graphs. We build on the work of Ducoffe et al. [SODA'20, SIGCOMP'22], improving their technique. With our approach the algorithms become simpler and faster, working in 𝒪{(k ⋅ n^{1-1/d} ⋅ m ⋅ polylog(n))} time complexity for the graph on n vertices and m edges, where k is the diameter and d is the distance VC-dimension of the graph. Furthermore, it allows us to use the improved technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we partially answer a question posed by Bringmann et al. [SoCG'22], finding an 𝒪{(n^{7/4} ⋅ polylog(n))} parameterized diameter algorithm for unit square intersection graph of size n, as well as a more general algorithm for convex polygon intersection graphs.
Cite as

Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.ESA.2024.51,
  author =	{Duraj, Lech and Konieczny, Filip and Pot\k{e}pa, Krzysztof},
  title =	{{Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.51},
  URN =		{urn:nbn:de:0030-drops-211229},
  doi =		{10.4230/LIPIcs.ESA.2024.51},
  annote =	{Keywords: Graph Diameter, Geometric Intersection Graphs, Vapnik-Chervonenkis Dimension}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.76
Faster Deterministic Modular Subset Sum

Authors: Krzysztof Potępa

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We consider the Modular Subset Sum problem: given a multiset X of integers from ℤ_m and a target integer t, decide if there exists a subset of X with a sum equal to t (mod m). Recent independent works by Cardinal and Iacono (SOSA'21), and Axiotis et al. (SOSA'21) provided simple and near-linear algorithms for this problem. Cardinal and Iacono gave a randomized algorithm that runs in 𝒪(m log m) time, while Axiotis et al. gave a deterministic algorithm that runs in 𝒪(m polylog m) time. Both results work by reduction to a text problem, which is solved using a dynamic strings data structure. In this work, we develop a simple data structure, designed specifically to handle the text problem that arises in the algorithms for Modular Subset Sum. Our data structure, which we call the shift-tree, is a simple variant of a segment tree. We provide both a hashing-based and a deterministic variant of the shift-trees. We then apply our data structure to the Modular Subset Sum problem and obtain two algorithms. The first algorithm is Monte-Carlo randomized and matches the 𝒪(m log m) runtime of the Las-Vegas algorithm by Cardinal and Iacono. The second algorithm is fully deterministic and runs in 𝒪(m log m ⋅ α(m)) time, where α is the inverse Ackermann function.
Cite as

Krzysztof Potępa. Faster Deterministic Modular Subset Sum. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{potepa:LIPIcs.ESA.2021.76,
  author =	{Pot\k{e}pa, Krzysztof},
  title =	{{Faster Deterministic Modular Subset Sum}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.76},
  URN =		{urn:nbn:de:0030-drops-146574},
  doi =		{10.4230/LIPIcs.ESA.2021.76},
  annote =	{Keywords: Modular Subset Sum, String Problem, Segment Tree, Data Structure}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.41
A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem

Authors: Lech Duraj

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated Longest Common Subsequence (LCS) problem. For LCIS, as well as for LCS, there is an ?(n²)-time algorithm and a SETH-based conditional lower bound of ?(n^{2-ε}). For LCS, there is also the Masek-Paterson ?(n²/log n)-time algorithm, which does not seem to adapt to LCIS in any obvious way. Hence, a natural question arises: does any (slightly) sub-quadratic algorithm exist for the Longest Common Increasing Subsequence problem? We answer this question positively, presenting a ?(n²/log^a n)-time algorithm for a = 1/6-o(1). The algorithm is not based on memorizing small chunks of data (often used for logarithmic speedups, including the "Four Russians Trick" in LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences.
Cite as

Lech Duraj. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{duraj:LIPIcs.STACS.2020.41,
  author =	{Duraj, Lech},
  title =	{{A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{41:1--41:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.41},
  URN =		{urn:nbn:de:0030-drops-119020},
  doi =		{10.4230/LIPIcs.STACS.2020.41},
  annote =	{Keywords: longest common increasing subsequence, log-shaving, matching pairs}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.46
A Note on Two-Colorability of Nonuniform Hypergraphs

Authors: Lech Duraj, Grzegorz Gutowski, and Jakub Kozik

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
For a hypergraph H, let q(H) denote the expected number of monochromatic edges when the color of each vertex in H is sampled uniformly at random from the set of size 2. Let s_{min}(H) denote the minimum size of an edge in H. Erdös asked in 1963 whether there exists an unbounded function g(k) such that any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant g(k) is two colorable. Beck in 1978 answered this question in the affirmative for a function g(k) = Theta(log^* k). We improve this result by showing that, for an absolute constant delta>0, a version of random greedy coloring procedure is likely to find a proper two coloring for any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant delta * log k.
Cite as

Lech Duraj, Grzegorz Gutowski, and Jakub Kozik. A Note on Two-Colorability of Nonuniform Hypergraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.ICALP.2018.46,
  author =	{Duraj, Lech and Gutowski, Grzegorz and Kozik, Jakub},
  title =	{{A Note on Two-Colorability of Nonuniform Hypergraphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.46},
  URN =		{urn:nbn:de:0030-drops-90505},
  doi =		{10.4230/LIPIcs.ICALP.2018.46},
  annote =	{Keywords: Property B, Nonuniform Hypergraphs, Hypergraph Coloring, Random Greedy Coloring}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.15
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

Authors: Lech Duraj, Marvin Künnemann, and Adam Polak

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called k-LCIS: Given k integer sequences X_1,...,X_k of length at most n, the task is to determine the length of the longest common subsequence of X_1,...,X_k that is also strictly increasing. Especially for the case of k=2 (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case. Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound to rule out O((nL)^{1-epsilon}) time algorithms for LCIS, where L denotes the solution size, and to rule out O(n^{k-epsilon}) time algorithms for k-LCIS. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.
Cite as

Lech Duraj, Marvin Künnemann, and Adam Polak. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.IPEC.2017.15,
  author =	{Duraj, Lech and K\"{u}nnemann, Marvin and Polak, Adam},
  title =	{{Tight Conditional Lower Bounds for Longest Common Increasing Subsequence}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.15},
  URN =		{urn:nbn:de:0030-drops-85706},
  doi =		{10.4230/LIPIcs.IPEC.2017.15},
  annote =	{Keywords: fine-grained complexity, combinatorial pattern matching, sequence alignments, parameterized complexity, SETH}
}
  • Refine by Type
  • 7 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 1 2021
  • 1 2020
  • 2 2018

  • Refine by Author
  • 4 Duraj, Lech
  • 2 Potępa, Krzysztof
  • 1 Gutowski, Grzegorz
  • 1 Kluk, Kacper
  • 1 Konieczny, Filip
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Mathematics of computing → Hypergraphs
  • Show More...

  • Refine by Keyword
  • 1 Data Structure
  • 1 Diameter
  • 1 Geometric Intersection Graphs
  • 1 Graph Diameter
  • 1 Hypergraph Coloring
  • 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