9 Search Results for "Wallheimer, Nathan"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.107
New Greedy Spanners and Applications

Authors: Elizaveta Popova and Elad Tzalik

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

Abstract
We present a simple greedy procedure to compute an (α,β)-spanner for a graph G. We then show that this procedure is useful for building fault-tolerant spanners, as well as spanners for weighted graphs. Our first main result is an algorithm that, given a multigraph G, outputs an f edge fault-tolerant (k,k-1)-spanner H of size O(fn^{1+1/k}) which is tight. To our knowledge, this is the first tight result concerning the price of fault tolerance in spanners which are not multiplicative, in any model of faults. Our second main result is a new construction of a spanner for weighted graphs. We show that any weighted graph G has a subgraph H with O(n^{1+1/k}) edges such that any path P of hop-length 𝓁 in G has a replacement path P' in H of weighted length ≤ w(P)+(2k-2)w^(1/2)(P) where w(P) is the total edge weight of P, and w^(1/2) denotes the sum of the largest ⌈𝓁/2⌉ edge weights along P. Moreover, we show such approximation is optimal for shortest paths of hop-length 2. To our knowledge, this is the first construction of a "spanner" for weighted graphs that strictly improves upon the stretch of multiplicative (2k-1)-spanners for all non-adjacent vertex pairs, while maintaining the same size bound. Our technique is based on using clustering and ball-growing, which are methods commonly used in designing spanner algorithms, to analyze simple greedy algorithms. This allows us to combine the flexibility of clustering approaches with the unique properties of the greedy algorithm to get improved bounds. In particular, our methods give a very short proof that the parallel greedy spanner adds O(kn^{1+1/k}) edges, improving upon known bounds.
Cite as

Elizaveta Popova and Elad Tzalik. New Greedy Spanners and Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 107:1-107:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{popova_et_al:LIPIcs.ITCS.2026.107,
  author =	{Popova, Elizaveta and Tzalik, Elad},
  title =	{{New Greedy Spanners and Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{107:1--107:25},
  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.107},
  URN =		{urn:nbn:de:0030-drops-253945},
  doi =		{10.4230/LIPIcs.ITCS.2026.107},
  annote =	{Keywords: Graph Spanners, Greedy Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.1
Triangle Detection in H-Free Graphs

Authors: Amir Abboud, Ron Safier, and Nathan Wallheimer

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

Abstract
We initiate the study of combinatorial algorithms for Triangle Detection in H-free graphs. The goal is to decide if a graph that forbids a fixed pattern H as a subgraph contains a triangle, using only "combinatorial" methods that notably exclude fast matrix multiplication. Our work aims to classify which patterns admit a subcubic speedup, working towards a dichotomy theorem. On the lower bound side, we show that if H is not 3-colorable or contains more than one triangle, the complexity of the problem remains unchanged, and no combinatorial speedup is likely possible. On the upper bound side, we develop an embedding approach that results in a strongly subcubic, combinatorial algorithm for a rich class of "embeddable" patterns. Specifically, for an embeddable pattern of size k, our algorithm runs in Õ(n^{3-1/(2^{k-3)}}) time, where Õ(⋅) hides poly-logarithmic factors. This algorithm also extends to listing all the triangles within the same time bound. We supplement this main result with two generalizations: - A generalization to patterns that are embeddable up to a single obstacle that arises from a triangle in the pattern. This completes our classification for small patterns, yielding a dichotomy theorem for all patterns of size up to eight. - An H-sensitive algorithm for embeddable patterns, which runs faster when the number of copies of H is significantly smaller than the maximum possible Ω(n^{k}). Finally, we focus on the special case of odd cycles. We present specialized Triangle Detection algorithms that are very efficient: - A combinatorial algorithm for C_{2k+1}-free graphs that runs in Õ(m+n^{1+2/k}) time for every k ≥ 2, where m is the number of edges in the graph. - A combinatorial C₅-sensitive algorithm that runs in Õ(n² + n^{4/3} t^{1/3}) time, where t is the number of 5-cycles in the graph.
Cite as

Amir Abboud, Ron Safier, and Nathan Wallheimer. Triangle Detection in H-Free Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ITCS.2026.1,
  author =	{Abboud, Amir and Safier, Ron and Wallheimer, Nathan},
  title =	{{Triangle Detection in H-Free Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{1:1--1:19},
  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.1},
  URN =		{urn:nbn:de:0030-drops-252885},
  doi =		{10.4230/LIPIcs.ITCS.2026.1},
  annote =	{Keywords: fine-grained complexity, triangle detection, H-free graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.14
Testing Sumsets Is Hard

Authors: Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, and Or Zamir

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

Abstract
A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}.
Cite as

Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, and Or Zamir. Testing Sumsets Is Hard. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2025.14,
  author =	{Chen, Xi and Nadimpalli, Shivam and Randolph, Tim and Servedio, Rocco A. and Zamir, Or},
  title =	{{Testing Sumsets Is Hard}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-244822},
  doi =		{10.4230/LIPIcs.ESA.2025.14},
  annote =	{Keywords: Sumsets, additive combinatorics, property testing, Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.42
(Multivariate) k-SUM as Barrier to Succinct Computation

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

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

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

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

Copy BibTex To Clipboard

@InProceedings{gokaj_et_al:LIPIcs.ESA.2025.42,
  author =	{Gokaj, Geri and K\"{u}nnemann, Marvin and Storandt, Sabine and Truschel, Carina},
  title =	{{(Multivariate) k-SUM as Barrier to Succinct Computation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.42},
  URN =		{urn:nbn:de:0030-drops-245101},
  doi =		{10.4230/LIPIcs.ESA.2025.42},
  annote =	{Keywords: Fine-grained complexity theory, sumsets, additive combinatorics, succinct inputs, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.4
Worst-Case to Expander-Case Reductions: Derandomized and Generalized

Authors: Amir Abboud and Nathan Wallheimer

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

Abstract
A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving that the complexity remains unchanged if the input is assumed to be an expander. An interesting corollary of their self-reductions is that if some problem admits such reduction, then the popular algorithmic paradigm based on expander-decompositions is useless against it. In this paper, we improve their core gadget, which augments a graph to make it an expander while retaining its important structure. Our new core construction has the benefit of being simple to analyze and generalize while obtaining the following results: - A derandomization of the self-reductions, showing that the equivalence between worst-case and expander-case holds even for deterministic algorithms, and ruling out the use of expander-decompositions as a derandomization tool. - An extension of the results to other models of computation, such as the Fully Dynamic model and the Congested Clique model. In the former, we either improve or provide an alternative approach to some recent hardness results for dynamic expander graphs by Henzinger, Paz, and Sricharan [ESA 2022]. In addition, we continue this line of research by designing new self-reductions for more problems, such as Max-Cut and dynamic Densest Subgraph, and demonstrating that the core gadget can be utilized to lift lower bounds based on the OMv Conjecture to expanders.
Cite as

Amir Abboud and Nathan Wallheimer. Worst-Case to Expander-Case Reductions: Derandomized and Generalized. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ESA.2024.4,
  author =	{Abboud, Amir and Wallheimer, Nathan},
  title =	{{Worst-Case to Expander-Case Reductions: Derandomized and Generalized}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-210751},
  doi =		{10.4230/LIPIcs.ESA.2024.4},
  annote =	{Keywords: Fine-grained complexity, expander graphs, self-reductions, worst-case to expander-case, expander decomposition, dynamic algorithms, exact and parameterized complexity, max-cut, maximum matching, k-clique detection, densest subgraph}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.19
Spanning Adjacency Oracles in Sublinear Time

Authors: Greg Bodwin and Henry Fleischmann

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Suppose we are given an n-node, m-edge input graph G, and the goal is to compute a spanning subgraph H on O(n) edges. This can be achieved in linear O(m + n) time via breadth-first search. But can we hope for sublinear runtime in some range of parameters - for example, perhaps O(n^{1.9}) worst-case runtime, even when the input graph has n² edges? If the goal is to return H as an adjacency list, there are simple lower bounds showing that Ω(m + n) runtime is necessary. If the goal is to return H as an adjacency matrix, then we need Ω(n²) time just to write down the entries of the output matrix. However, we show that neither of these lower bounds still apply if instead the goal is to return H as an implicit adjacency matrix, which we call an adjacency oracle. An adjacency oracle is a data structure that gives a user the illusion that an adjacency matrix has been computed: it accepts edge queries (u, v), and it returns in near-constant time a bit indicating whether or not (u, v) ∈ E(H). Our main result is that, for any 0 < ε < 1, one can construct an adjacency oracle for a spanning subgraph on at most (1+ε)n edges, in Õ(n ε^{-1}) time (hence sublinear time on input graphs with m ≫ n edges), and that this construction time is near-optimal. Additional results include constructions of adjacency oracles for k-connectivity certificates and spanners, which are similarly sublinear on dense-enough input graphs. Our adjacency oracles are closely related to Local Computation Algorithms (LCAs) for graph sparsifiers; they can be viewed as LCAs with some computation moved to a preprocessing step, in order to speed up queries. Our oracles imply the first LCAs for computing sparse spanning subgraphs of general input graphs in Õ(n) query time, which works by constructing our adjacency oracle, querying it once, and then throwing the rest of the oracle away. This addresses an open problem of Rubinfeld [CSR '17].
Cite as

Greg Bodwin and Henry Fleischmann. Spanning Adjacency Oracles in Sublinear Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ITCS.2024.19,
  author =	{Bodwin, Greg and Fleischmann, Henry},
  title =	{{Spanning Adjacency Oracles in Sublinear Time}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.19},
  URN =		{urn:nbn:de:0030-drops-195475},
  doi =		{10.4230/LIPIcs.ITCS.2024.19},
  annote =	{Keywords: Graph algorithms, Sublinear algorithms, Data structures, Graph theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.88
Color Fault-Tolerant Spanners

Authors: Asaf Petruschka, Shay Sapir, and Elad Tzalik

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We initiate the study of spanners in arbitrarily vertex- or edge-colored graphs (with no "legality" restrictions), that are resilient to failures of entire color classes. When a color fails, all vertices/edges of that color crash. An f-color fault-tolerant (f-CFT) t-spanner of an n-vertex colored graph G is a subgraph H that preserves distances up to factor t, even in the presence of at most f color faults. This notion generalizes the well-studied f-vertex/edge fault-tolerant (f-V/EFT) spanners. The size (number of edges) of an f-V/EFT spanner crucially depends on the number f of vertex/edge faults to be tolerated. In the colored variants, even a single color fault can correspond to an unbounded number of vertex/edge faults. The key conceptual contribution of this work is in showing that the size required by an f-CFT spanner is in fact comparable to its uncolored counterpart, with no dependency on the size of color classes. We provide optimal bounds on the size required by f-CFT (2k-1)-spanners, as follows: - When vertices have colors, we show an upper bound of O(f^{1-1/k} n^{1+1/k}) edges. This precisely matches the (tight) bounds for (2k-1)-spanners resilient to f individual vertex faults [Bodwin et al., SODA 2018; Bodwin and Patel, PODC 2019]. - For colored edges, we show that O(f n^{1+1/k}) edges are always sufficient. Further, we prove this is tight, i.e., we provide an Ω(f n^{1+1/k}) (worst-case) lower bound. The state-of-the-art bounds known for the corresponding uncolored setting of edge faults are (roughly) Θ(f^{1/2} n^{1+1/k}) [Bodwin et al., SODA 2018; Bodwin, Dinitz and Robelle, SODA 2022]. - We also consider a mixed model where both vertices and edges are colored. In this case, we show tight Θ(f^{2-1/k} n^{1+1/k}) bounds. Thus, CFT spanners exhibit an interesting phenomenon: while (individual) edge faults are "easier" than vertex faults, edge-color faults are "harder" than vertex-color faults. Our upper bounds are based on a generalization of the blocking set technique of [Bodwin and Patel, PODC 2019] for analyzing the (exponential-time) greedy algorithm for FT spanners. We complement them by providing efficient constructions of CFT spanners with similar size guarantees, based on the algorithm of [Dinitz and Robelle, PODC 2020].
Cite as

Asaf Petruschka, Shay Sapir, and Elad Tzalik. Color Fault-Tolerant Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{petruschka_et_al:LIPIcs.ITCS.2024.88,
  author =	{Petruschka, Asaf and Sapir, Shay and Tzalik, Elad},
  title =	{{Color Fault-Tolerant Spanners}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{88:1--88:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.88},
  URN =		{urn:nbn:de:0030-drops-196160},
  doi =		{10.4230/LIPIcs.ITCS.2024.88},
  annote =	{Keywords: Fault tolerance, Graph spanners}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.1
Worst-Case to Expander-Case Reductions

Authors: Amir Abboud and Nathan Wallheimer

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful hammer has led the community to (1) believe that most problems are as easy on worst-case graphs as they are on expanders, and (2) suspect that expander decompositions are the key to breaking the remaining longstanding barriers in fine-grained complexity. We set out to investigate the extent to which these two things are true (and for which problems). Towards this end, we put forth the concept of worst-case to expander-case self-reductions. We design a collection of such reductions for fundamental graph problems, verifying belief (1) for them. The list includes k-Clique, 4-Cycle, Maximum Cardinality Matching, Vertex-Cover, and Minimum Dominating Set. Interestingly, for most (but not all) of these problems the proof is via a simple gadget reduction, not via expander decompositions, showing that this hammer is effectively useless against the problem and contradicting (2).
Cite as

Amir Abboud and Nathan Wallheimer. Worst-Case to Expander-Case Reductions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ITCS.2023.1,
  author =	{Abboud, Amir and Wallheimer, Nathan},
  title =	{{Worst-Case to Expander-Case Reductions}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.1},
  URN =		{urn:nbn:de:0030-drops-175044},
  doi =		{10.4230/LIPIcs.ITCS.2023.1},
  annote =	{Keywords: Fine-Grained Complexity, Expander Decomposition, Reductions, Exact and Parameterized Complexity, Expander Graphs, Triangle, Maximum Matching, Clique, 4-Cycle, Vertex Cover, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.27
Improved Compression of the Okamura-Seymour Metric

Authors: Shay Mozes, Nathan Wallheimer, and Oren Weimann

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Let G = (V,E) be an undirected unweighted planar graph. Let S = {s_1,…,s_k} be the vertices of some face in G and let T ⊆ V be an arbitrary set of vertices. The Okamura-Seymour metric compression problem asks to compactly encode the S-to-T distances. Consider a vector storing the distances from an arbitrary vertex v to all vertices S = {s_1,…,s_k} in their cyclic order. The pattern of v is obtained by taking the difference between every pair of consecutive values of this vector. In STOC'19, Li and Parter used a VC-dimension argument to show that in planar graphs, the number of distinct patterns, denoted p_#, is only O(k³). This resulted in a simple Õ(min{k⁴+|T|, k⋅|T|}) space compression of the Okamura-Seymour metric. We give an alternative proof of the p_# = O(k³) bound that exploits planarity beyond the VC-dimension argument. Namely, our proof relies on cut-cycle duality, as well as on the fact that distances among vertices of S are bounded by k. Our method implies the following: (1) An Õ(p_#+k+|T|) space compression of the Okamura-Seymour metric, thus improving the compression of Li and Parter to Õ(min{k³+|T|, k⋅|T|}). (2) An optimal Õ(k+|T|) space compression of the Okamura-Seymour metric, in the case where the vertices of T induce a connected component in G. (3) A tight bound of p_# = Θ(k²) for the family of Halin graphs, whereas the VC-dimension argument is limited to showing p_# = O(k³).
Cite as

Shay Mozes, Nathan Wallheimer, and Oren Weimann. Improved Compression of the Okamura-Seymour Metric. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mozes_et_al:LIPIcs.ISAAC.2022.27,
  author =	{Mozes, Shay and Wallheimer, Nathan and Weimann, Oren},
  title =	{{Improved Compression of the Okamura-Seymour Metric}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.27},
  URN =		{urn:nbn:de:0030-drops-173123},
  doi =		{10.4230/LIPIcs.ISAAC.2022.27},
  annote =	{Keywords: Shortest paths, planar graphs, metric compression, distance oracles}
}
  • Refine by Type
  • 9 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 2 2025
  • 3 2024
  • 1 2023
  • 1 2022

  • Refine by Author
  • 4 Wallheimer, Nathan
  • 3 Abboud, Amir
  • 2 Tzalik, Elad
  • 1 Bodwin, Greg
  • 1 Chen, Xi
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Sparsification and spanners
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 additive combinatorics
  • 1 4-Cycle
  • 1 Boolean functions
  • 1 Clique
  • 1 Data structures
  • 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