12 Search Results for "Yingchareonthawornchai, Sorrachai"

Document
DOI: 10.4230/LIPIcs.ESA.2025.107
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts

Authors: Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang

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

Abstract
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2022; Haeupler et al., 2024]. Along the way, we prove the multi-commodity maxflow-mincut theorems for length-constrained expansion in both directed and undirected vertex-capacitated graphs. Based on our decomposition, we build a length-constrained flow shortcut for undirected vertex-capacitated graphs, which roughly speaking is a set of edges and vertices added to the graph so that every multi-commodity flow demand can be routed with approximately the same vertex-congestion and length, but all flow paths only contain few edges. This generalizes the shortcut for undirected edge-capacitated graphs from [Bernhard Haeupler et al., 2024]. Length-constrained expander decomposition and flow shortcuts have been crucial in the recent algorithms in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2024; Haeupler et al., 2024]. Our work thus serves as a foundation to generalize these concepts to directed and vertex-capacitated graphs.
Cite as

Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 107:1-107:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ESA.2025.107,
  author =	{Haeupler, Bernhard and Long, Yaowei and Saranurak, Thatchaphol and Wang, Shengzhe},
  title =	{{Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{107:1--107: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.107},
  URN =		{urn:nbn:de:0030-drops-245765},
  doi =		{10.4230/LIPIcs.ESA.2025.107},
  annote =	{Keywords: Length-Constrained Expander, Expander Decomposition, Shortcut}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.36
Efficient Contractions of Dynamic Graphs - With Applications

Authors: Monika Henzinger, Evangelos Kosinas, Robin Münk, and Harald Räcke

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

Abstract
A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors. We discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs.
Cite as

Monika Henzinger, Evangelos Kosinas, Robin Münk, and Harald Räcke. Efficient Contractions of Dynamic Graphs - With Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2025.36,
  author =	{Henzinger, Monika and Kosinas, Evangelos and M\"{u}nk, Robin and R\"{a}cke, Harald},
  title =	{{Efficient Contractions of Dynamic Graphs - With Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{36:1--36:14},
  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.36},
  URN =		{urn:nbn:de:0030-drops-245047},
  doi =		{10.4230/LIPIcs.ESA.2025.36},
  annote =	{Keywords: Graph Algorithms, Cut Sparsifiers, Dynamic Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.83
Fault-Tolerant Matroid Bases

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, and Laure Morelle

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

Abstract
We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid ℳ and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of elements such that, even after the removal of any k elements, the remaining subset still spans the entire ground set. Since matroids generalize linear independence across structures such as vector spaces, graphs, and set systems, this problem unifies and extends several fault-tolerant concepts appearing in prior research. Our main contribution is a fixed-parameter tractable (FPT) algorithm for the k-fault-tolerant basis problem, parameterized by both k and the rank r of the matroid. This two-variable parameterization by k + r is shown to be tight in the following sense. On the one hand, the problem is already NP-hard for k = 1. On the other hand, it is Para-NP-hard for r ≥ 3 and polynomial-time solvable for r ≤ 2.
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, and Laure Morelle. Fault-Tolerant Matroid Bases. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ESA.2025.83,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Morelle, Laure},
  title =	{{Fault-Tolerant Matroid Bases}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{83:1--83:14},
  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.83},
  URN =		{urn:nbn:de:0030-drops-245511},
  doi =		{10.4230/LIPIcs.ESA.2025.83},
  annote =	{Keywords: Parameterized Complexity, matroids, robust bases}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.32
Quantum Property Testing in Sparse Directed Graphs

Authors: Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó

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

Abstract
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing k-star-freeness, and more generally k-source-subgraph-freeness, is almost maximally hard for large k. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the k-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 3-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
Cite as

Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó. Quantum Property Testing in Sparse Directed Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2025.32,
  author =	{Apers, Simon and Magniez, Fr\'{e}d\'{e}ric and Sen, Sayantan and Szab\'{o}, D\'{a}niel},
  title =	{{Quantum Property Testing in Sparse Directed Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{32:1--32:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.32},
  URN =		{urn:nbn:de:0030-drops-243987},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.32},
  annote =	{Keywords: property testing, quantum computing, bounded-degree directed graphs, dual polynomial method, collision finding}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2025.2
Higher Connectivity in Directed Graphs (Invited Talk)

Authors: Giuseppe F. Italiano

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

Abstract
The computation of edge-connected components in directed and undirected graphs is a well studied problem that is motivated by several applications (see, e.g., [Hiroshi Nagamochi and Toshihide Ibaraki, 2008]). Let G = (V,E) be a strongly connected directed graph with m edges and n vertices. An edge e ∈ E is a strong bridge if G ⧵ e is not strongly connected. More generally, a set of edges C ⊆ E is a cut if G ⧵ C is not strongly connected. If |C| = k then we refer to C as a k-sized cut of G. Hence, a strong bridge is a 1-sized cut of G. A digraph G is k-edge-connected if it has no (k-1)-cuts. We say that two vertices v and w are k-edge-connected, and we denote this relation by v ↔_{k} w, if there are k edge-disjoint directed paths from v to w and k edge-disjoint directed paths from w to v. (Note that a path from v to w and a path from w to v need not be edge-disjoint). By Menger’s theorem [Karl Menger, 1927], v ↔_{k} w if and only if the removal of any set of at most k-1 edges leaves v and w in the same strongly connected component. We define a k-edge-connected component of a digraph G = (V,E) as a maximal subset U ⊆ V such that u ↔_{k} v for all u, v ∈ U. The k-edge-connected components of G form a partition of V, since v ↔_{k} w is an equivalence relation [Loukas Georgiadis et al., 2016]. Connectivity-related problems are known to be much more difficult in directed graphs than in undirected graphs (see, e.g., [Harold N. Gabow, 2016; Monika Henzinger et al., 2020; Ken-Ichi Kawarabayashi and Mikkel Thorup, 2018]). Indeed, there is a fundamental difference in the structure of the cuts in the two scenarios. Specifically, it has been established more than 60 years ago [Gomory and Hu, 1961] that edge cuts in undirected graphs have a nice structure, as defined by the Gomory-Hu tree (or cut tree), which plays a special role in identifying, for any k, the k-edge-connected components of undirected graphs. Furthermore, many efficient algorithms for computing Gomory-Hu trees are available (see e.g., [Amir Abboud et al., 2021; Amir Abboud et al., 2022; Amir Abboud et al., 2023; Chen et al., 2022; Hariharan et al., 2007; Li et al., 2022]). On the contrary, in directed graphs edge cuts have a more complicated structure, and it was proved by Benczúr [Benczúr, 1995] that in this case cut trees do not even exist. It is thus not surprising that, while it is known how to compute the k-edge-connected components of undirected graphs in linear time for k ≤ 5 [Harold N. Gabow, 2000; Zvi Galil and Giuseppe F. Italiano, 1991; Loukas Georgiadis et al., 2021; John E. Hopcroft and Robert E. Tarjan, 1973; Kosinas, 2024; Wojciech Nadara et al., 2021; Hiroshi Nagamochi and Toshihide Ibaraki, 1992; Robert E. Tarjan, 1972; Yung H. Tsin, 2009], the situation is more challenging for directed graphs, where linear-time algorithms are only known for k ≤ 2 [Robert E. Tarjan, 1972; Loukas Georgiadis et al., 2020]. Also, as argued in [Loukas Georgiadis et al., 2023], there is a substantial increase in the inherent difficulty of the problem of computing k-edge-connected components in digraphs for k = 3 compared to k = 2. Indeed, for k = 2 any pair of vertices s,t that are not 2-edge-connected can be separated by only O(n) s-t min-cuts of size 1, for which we can define a total order [Giuseppe F. Italiano et al., 2012]. For k = 3, any pair of vertices s,t that are 2-edge-connected but not 3-edge-connected, can be separated by as many as O(n²) s-t min-cuts of size 2, which are also not totally ordered. This makes it difficult to explore the effect of removing each such cut of size 2 on the strong connectivity of the graph, similar to what was done for the case of k = 2 [Loukas Georgiadis et al., 2020]. Until recently, the best-known bound for computing the k-edge-connected components of a digraph, for constant k ≥ 3, was O(mn) by Nagamochi and Watanabe [Hiroshi Nagamochi and Toshimasa Watanabe, 1993]. Georgiadis et al. [Loukas Georgiadis et al., 2023] presented a randomized (Monte-Carlo) algorithm that computes the 3-edge-connected components of a digraph with m edges in Õ(m^{3/2}) time. Their algorithm involves a nontrivial extension of the framework of [Forster et al., 2020; Nanongkai et al., 2019] for deciding whether a digraph is (k+1)-edge-connected. It applies a local search procedure [Shiri Chechik et al., 2017; Forster et al., 2020] for identifying 2-in or 2-out sets, i.e., vertex sets S ⊆ V such that there are at most 2 edges from V ⧵ S to S or from S to V⧵ S. After finding such a set S, [Loukas Georgiadis et al., 2023] applies an efficient graph operation for replacing S with a gadget of small size that preserves the pairwise connectivity among the vertices of V ⧵ S. As in [Forster et al., 2020; Nanongkai et al., 2019], local search is initiated from sampled edges, but the overall scheme is more complicated to guarantee that enough 2-in sets or 2-out sets are identified that separate vertices that are not 3-edge-connected. Recently, Georgiadis, Italiano and Kosinas [Georgiadis et al., 2024] improved significantly the bound of [Loukas Georgiadis et al., 2023] by showing how to compute the 3-edge-connected components of a digraph in linear time with a deterministic algorithm. Their algorithm differs substantially from [Loukas Georgiadis et al., 2023], as it is based on a new characterization of 2-sized cuts in digraphs, which requires new techniques and a suitable combination of the notions of 2-connectivity-light graphs [Loukas Georgiadis et al., 2023] and of maximally edge-disjoint strongly divergent spanning trees [Loukas Georgiadis and Robert E. Tarjan, 2015; Robert E. Tarjan, 1976]. In particular, Georgiadis, Italiano and Kosinas [Georgiadis et al., 2024] showed how to modify the minset-poset technique of Gabow [Harold N. Gabow, 2016], in order to find the 3-edge-connected components of a digraph with m edges in O(m) time. In the invited talk, I will survey some of this recent work on higher connectivity on directed graphs.
Cite as

Giuseppe F. Italiano. Higher Connectivity in Directed Graphs (Invited Talk). In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 2:1-2:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{italiano:LIPIcs.MFCS.2025.2,
  author =	{Italiano, Giuseppe F.},
  title =	{{Higher Connectivity in Directed Graphs}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{2:1--2:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.2},
  URN =		{urn:nbn:de:0030-drops-241096},
  doi =		{10.4230/LIPIcs.MFCS.2025.2},
  annote =	{Keywords: Connectivity, Directed graphs, Graph algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.12
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Authors: Aditya Anand, Euiwoong Lee, Jason Li, and Thatchaphol Saranurak

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

Abstract
Given a directed graph G with n vertices and m edges, a parameter k and two disjoint subsets S,T ⊆ V(G), we show that the number of all-subsets important separators, which is the number of A-B important vertex separators of size at most k over all A ⊆ S and B ⊆ T, is at most β(|S|, |T|, k) = 4^k binom(|S|, ≤ k) binom(|T|, ≤ 2k), where binom(x, ≤ c) = ∑_{i = 1}^c binom(x,i), and that they can be enumerated in time 𝒪(β(|S|,|T|,k)k²(m+n)). This is a generalization of the folklore result stating that the number of A-B important separators for two fixed sets A and B is at most 4^k (first implicitly shown by Chen, Liu and Lu Algorithmica '09). From this result, we obtain the following applications: 1) We give a construction for detection sets and sample sets in directed graphs, generalizing the results of Kleinberg (Internet Mathematics' 03) and Feige and Mahdian (STOC' 06) to directed graphs. 2) Via our new sample sets, we give the first FPT algorithm for finding balanced separators in directed graphs parameterized by k, the size of the separator. Our algorithm runs in time 2^{𝒪(k)} ⋅ (m + n). 3) Additionally, we show a 𝒪(√{log k}) approximation algorithm for finding balanced separators in directed graphs in polynomial time. This improves the best known approximation guarantee of 𝒪(√{log n}) and matches the known guarantee in undirected graphs by Feige, Hajiaghayi and Lee (SICOMP' 08). 4) Finally, using our algorithm for listing all-subsets important separators, we give a deterministic construction of vertex cut sparsifiers in directed graphs when we are interested in preserving min-cuts of size upto c between bipartitions of the terminal set. Our algorithm constructs a sparsifier of size 𝒪(binom(t, ≤ 3c)2^{𝒪(c)}) and runs in time 𝒪(binom(t, ≤ 3c) 2^{𝒪(c)}(m + n)), where t is the number of terminals, and the sparsifier additionally preserves the set of important separators of size at most c between bipartitions of the terminals.
Cite as

Aditya Anand, Euiwoong Lee, Jason Li, and Thatchaphol Saranurak. All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.ICALP.2025.12,
  author =	{Anand, Aditya and Lee, Euiwoong and Li, Jason and Saranurak, Thatchaphol},
  title =	{{All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{12:1--12:20},
  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.12},
  URN =		{urn:nbn:de:0030-drops-233892},
  doi =		{10.4230/LIPIcs.ICALP.2025.12},
  annote =	{Keywords: directed graphs, important separators, sample sets, balanced separators}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.42
Hardness Amplification for Dynamic Binary Search Trees

Authors: Shunhua Jiang, Victor Lecomte, Omri Weinstein, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We prove direct-sum theorems for Wilber’s two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the question of dynamic optimality [Sleator and Tarjan, JACM'85]: the Alternation bound is the only bound to have yielded online BST algorithms beating log n competitive ratio, while the Funnel bound has repeatedly been conjectured to exactly characterize the cost of executing an access sequence using the optimal tree [Wilber, FOCS'86, Kozma'16], and has been explicitly linked to splay trees [Levy and Tarjan, SODA'19]. Previously, the direct-sum theorem for the Alternation bound was known only when approximation was allowed [Chalermsook, Chuzhoy and Saranurak, APPROX'20, ToC'24]. We use these direct-sum theorems to amplify the sequences from [Lecomte and Weinstein, ESA'20] that separate between Wilber’s Alternation and Funnel bounds, increasing the Alternation and Funnel bounds while optimally maintaining the separation. As a corollary, we show that Tango trees [Demaine et al., FOCS'04] are optimal among any BST algorithms that charge their costs to the Alternation bound. This is true for any value of the Alternation bound, even values for which Tango trees achieve a competitive ratio of o(log log n) instead of the default O(log log n). Previously, the optimality of Tango trees was shown only for a limited range of Alternation bound [Lecomte and Weinstein, ESA'20].
Cite as

Shunhua Jiang, Victor Lecomte, Omri Weinstein, and Sorrachai Yingchareonthawornchai. Hardness Amplification for Dynamic Binary Search Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ISAAC.2024.42,
  author =	{Jiang, Shunhua and Lecomte, Victor and Weinstein, Omri and Yingchareonthawornchai, Sorrachai},
  title =	{{Hardness Amplification for Dynamic Binary Search Trees}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.42},
  URN =		{urn:nbn:de:0030-drops-221696},
  doi =		{10.4230/LIPIcs.ISAAC.2024.42},
  annote =	{Keywords: Data Structures, Amortized Analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.38
The Group Access Bounds for Binary Search Trees

Authors: Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees (BSTs) that implies interesting consequences such as static optimality, static finger, and working set property on any access sequence X = (x_1,x_2,… ,x_m). However, there are known corollaries of the dynamic optimality that cannot be derived via the access lemma, such as the dynamic finger, and any o(log n)-competitive ratio to the optimal BST where n is the number of keys. In this paper, we introduce the group access bound that can be defined with respect to a reference group access tree. Group access bounds generalize the access lemma and imply properties that are far stronger than those implied by the classical access lemma. For each of the following results, there is a group access tree whose group access bound 1) Is O(√{log n})-competitive to the optimal BST. 2) Achieves the k-finger bound with an additive term of O(m log k log log n) (randomized) when the reference tree is an almost complete binary tree. 3) Satisfies the unified bound with an additive term of O(m log log n). 4) Matches the unified bound with a time window k with an additive term of O(m log k log log n) (randomized). Furthermore, we prove the simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(log n)-competitiveness of the Splay tree and Greedy, two prime candidates for the dynamic optimality conjecture.
Cite as

Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. The Group Access Bounds for Binary Search Trees. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2024.38,
  author =	{Chalermsook, Parinya and Gupta, Manoj and Jiamjitrak, Wanchote and Pareek, Akash and Yingchareonthawornchai, Sorrachai},
  title =	{{The Group Access Bounds for Binary Search Trees}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.38},
  URN =		{urn:nbn:de:0030-drops-201817},
  doi =		{10.4230/LIPIcs.ICALP.2024.38},
  annote =	{Keywords: Dynamic Optimality, Binary Search Tree, Online Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.70
Vertex Sparsifiers for Hyperedge Connectivity

Authors: Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Recently, Chalermsook et al. {[}SODA'21{]} introduces a notion of vertex sparsifiers for c-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for c-edge st-connectivity {[}Jin and Sun FOCS'22{]}. We study a natural extension called vertex sparsifiers for c-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs. More specifically, we show that, given a hypergraph G = (V,E) with n vertices and m hyperedges with k terminal vertices and a parameter c, there exists a hypergraph H containing only O(kc³) hyperedges that preserves all minimum cuts (up to value c) between all subset of terminals. This matches the best bound of O(kc³) edges for normal graphs by [Liu'20]. Moreover, H can be constructed in almost-linear O(p^{1+o(1)} + n(rclog n)^{O(rc)}log m) time where r = max_{e ∈ E}|e| is the rank of G and p = ∑_{e ∈ E}|e| is the total size of G, or in poly(m, n) time if we slightly relax the size to O(kc³log^{1.5}(kc)) hyperedges.
Cite as

Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ESA.2022.70,
  author =	{Jiang, Han and Huang, Shang-En and Saranurak, Thatchaphol and Zhang, Tian},
  title =	{{Vertex Sparsifiers for Hyperedge Connectivity}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.70},
  URN =		{urn:nbn:de:0030-drops-170081},
  doi =		{10.4230/LIPIcs.ESA.2022.70},
  annote =	{Keywords: Vertex sparsifier, hypergraph, connectivity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.37
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Authors: Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the "uniform case" of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mn k) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n²) can be obtained, but with a higher approximation guarantee of (2k-1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1+ε)-approximates the optimal fractional solution in Õ(m/ε²) time (independent of k), which can be turned into a (2+ε) approximation algorithm that runs in time Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.
Cite as

Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2022.37,
  author =	{Chalermsook, Parinya and Huang, Chien-Chung and Nanongkai, Danupon and Saranurak, Thatchaphol and Sukprasert, Pattara and Yingchareonthawornchai, Sorrachai},
  title =	{{Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.37},
  URN =		{urn:nbn:de:0030-drops-163785},
  doi =		{10.4230/LIPIcs.ICALP.2022.37},
  annote =	{Keywords: Approximation Algorithms, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.1
Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

Authors: Max Franck and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is k-connected if it remains connected after removing any k-1 vertices. The vertex connectivity of a graph is the maximum k such that the graph is k-connected. There is a long history of algorithmic development for efficiently computing vertex connectivity. Recently, two near linear-time algorithms for small k were introduced by [Forster et al. SODA 2020]. Prior to that, the best known algorithm was one by [Henzinger et al. FOCS'96] with quadratic running time when k is small. In this paper, we study the practical performance of the algorithms by Forster et al. In addition, we introduce a new heuristic on a key subroutine called local cut detection, which we call degree counting. We prove that the new heuristic improves space-efficiency (which can be good for caching purposes) and allows the subroutine to terminate earlier. According to experimental results on random graphs with planted vertex cuts, random hyperbolic graphs, and real world graphs with vertex connectivity between 4 and 15, the degree counting heuristic offers a factor of 2-4 speedup over the original non-degree counting version for most of our data. It also outperforms the previous state-of-the-art algorithm by Henzinger et al. even on relatively small graphs.
Cite as

Max Franck and Sorrachai Yingchareonthawornchai. Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{franck_et_al:LIPIcs.SEA.2021.1,
  author =	{Franck, Max and Yingchareonthawornchai, Sorrachai},
  title =	{{Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.1},
  URN =		{urn:nbn:de:0030-drops-137735},
  doi =		{10.4230/LIPIcs.SEA.2021.1},
  annote =	{Keywords: Algorithm Engineering, Algorithmic Graph Theory, Sublinear Algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.34
Analysis of Bounds on Hybrid Vector Clocks

Authors: Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Hybrid vector clocks (HVC) implement vector clocks (VC) in a space-efficient manner by exploiting the availability of loosely-synchronized physical clocks at each node. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, epsilon: uncertainty window, delta: minimum message delay, alpha: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases. Our model and simulations show the HVC size is a sigmoid function with respect to increasing epsilon; it has a slow start but it grows exponentially after a phase transition. We present equations to identify the phase transition point and show that for many practical applications and deployment environments, the size of HVC remains only as a couple entries and substantially less than n. We also find that, in a model with random unicast message transmissions, increasing n actually helps for reducing HVC size.
Cite as

Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas. Analysis of Bounds on Hybrid Vector Clocks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yingchareonthawornchai_et_al:LIPIcs.OPODIS.2015.34,
  author =	{Yingchareonthawornchai, Sorrachai and Kulkarni, Sandeep S. and Demirbas, Murat},
  title =	{{Analysis of Bounds on Hybrid Vector Clocks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.34},
  URN =		{urn:nbn:de:0030-drops-66771},
  doi =		{10.4230/LIPIcs.OPODIS.2015.34},
  annote =	{Keywords: Vector Clocks, Physical Clocks, Large Scale Systems}
}
  • Refine by Type
  • 12 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 6 2025
  • 2 2024
  • 2 2022
  • 1 2021
  • 1 2016

  • Refine by Author
  • 5 Yingchareonthawornchai, Sorrachai
  • 4 Saranurak, Thatchaphol
  • 2 Chalermsook, Parinya
  • 1 Anand, Aditya
  • 1 Apers, Simon
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Fixed parameter tractability
  • 2 Theory of computation → Online algorithms
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 2 Data Structures
  • 1 Algorithm Engineering
  • 1 Algorithmic Graph Theory
  • 1 Amortized Analysis
  • 1 Approximation Algorithms
  • 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