Search Results

Documents authored by Tsai, Meng-Tsung

Document
DOI: 10.4230/LIPIcs.WADS.2025.18
Parameterized Streaming Algorithms for Topological Sorting

Authors: Ho-Lin Chen, Peng-Ting Lin, and Meng-Tsung Tsai

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

Abstract
Computing a topological ordering for an n-node directed acyclic graph (DAG) G is computationally challenging in streaming models. Chakrabarti et al. {[}SODA 2020{]} showed that in the insertion-only streaming model, every single-pass algorithm requires Ω(n²) space, and every k-pass algorithm requires n^{1+Ω(1/k)} space for any constant k ≥ 1. We study the parameterized complexity of streaming algorithms for topological sorting, considering two parameters: the independence number α and the maximum displacement δ. Our results include an O(1/ε)-pass O(α n^{1+ε})-space streaming algorithm and an O(n^{1/2})-pass O(n+δ²)-space streaming algorithm. For dense random DAGs, both α and δ are small, allowing us to improve the state-of-the-art for topological sorting in random DAGs. As applications, we show that strongly connected components (SCC) decomposition and 2-satisfiability (2-SAT) can be solved in O(1/ε) passes using O(α n^{1+ε}) space and O(α_I n^{1+ε}) space, respectively, where α_I denotes the independence number of the implication graph induced by the input 2-SAT instance.
Cite as

Ho-Lin Chen, Peng-Ting Lin, and Meng-Tsung Tsai. Parameterized Streaming Algorithms for Topological Sorting. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.WADS.2025.18,
  author =	{Chen, Ho-Lin and Lin, Peng-Ting and Tsai, Meng-Tsung},
  title =	{{Parameterized Streaming Algorithms for Topological Sorting}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.18},
  URN =		{urn:nbn:de:0030-drops-242495},
  doi =		{10.4230/LIPIcs.WADS.2025.18},
  annote =	{Keywords: Independence Number, Chain Cover, SCC Decomposition, 2-Satisfiability}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.43
On the Complexity of Finding 1-Center Spanning Trees

Authors: Pin-Hsian Lee, Meng-Tsung Tsai, and Hung-Lung Wang

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

Abstract
We consider the problem of finding a spanning tree T of a given undirected graph G such that any other spanning tree can be obtained from T by removing k edges and subsequently adding k edges, where k is minimized over all spanning trees of G. We refer to this minimum k as the treeradius of G. Treeradius is an interesting graph parameter with natural interpretations: (1) It is the smallest radius of a Hamming ball centered at an extreme point of the spanning tree polytope that covers the entire polytope. (2) Any graph with bounded treeradius also has bounded treewidth. Consequently, if a problem admits a fixed-parameter algorithm parameterized by treewidth, it also admits a fixed-parameter algorithm parameterized by treeradius. In this paper, we show that computing the exact treeradius for n-vertex graphs requires 2^Ω(n) time under the Exponential Time Hypothesis (ETH) and does not admit a PTAS, with an inapproximability bound of 1153/1152, unless P = NP. This hardness result is surprising, as treeradius has significantly higher ETH complexity compared to analogous problems on shortest path polytopes and star subgraph polytopes.
Cite as

Pin-Hsian Lee, Meng-Tsung Tsai, and Hung-Lung Wang. On the Complexity of Finding 1-Center Spanning Trees. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.WADS.2025.43,
  author =	{Lee, Pin-Hsian and Tsai, Meng-Tsung and Wang, Hung-Lung},
  title =	{{On the Complexity of Finding 1-Center Spanning Trees}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.43},
  URN =		{urn:nbn:de:0030-drops-242743},
  doi =		{10.4230/LIPIcs.WADS.2025.43},
  annote =	{Keywords: Treeradius, Spanning tree polytope, Shortest s, t-path polytope}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.84
Dependent k-Set Packing on Polynomoids

Authors: Meng-Tsung Tsai, Shi-Chun Tsai, and Tsung-Ta Wu

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Specialized hereditary systems, e.g., matroids, are known to have many applications in algorithm design. We define a new notion called d-polynomoid as a hereditary system (E, ℱ ⊆ 2^E) so that every two maximal sets in ℱ have less than d elements in common. We study the problem that, given a d-polynomoid (E, ℱ), asks if the ground set E contains 𝓁 disjoint k-subsets that are not in ℱ, and obtain a complexity trichotomy result for all pairs of k ≥ 1 and d ≥ 0. Our algorithmic result yields a sufficient and necessary condition that decides whether each hypergraph in some classes of r-uniform hypergraphs has a perfect matching, which has a number of algorithmic applications.
Cite as

Meng-Tsung Tsai, Shi-Chun Tsai, and Tsung-Ta Wu. Dependent k-Set Packing on Polynomoids. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tsai_et_al:LIPIcs.MFCS.2023.84,
  author =	{Tsai, Meng-Tsung and Tsai, Shi-Chun and Wu, Tsung-Ta},
  title =	{{Dependent k-Set Packing on Polynomoids}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{84:1--84:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.84},
  URN =		{urn:nbn:de:0030-drops-186180},
  doi =		{10.4230/LIPIcs.MFCS.2023.84},
  annote =	{Keywords: Hereditary Systems, Hypergraph Matchings, Compleixty Trichotomy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.34
Streaming Complexity of Spanning Tree Computation

Authors: Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai

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

Abstract
The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using Õ(n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertion-only model. In both models, some graph problems, such as spanning trees, k-connectivity, densest subgraph, degeneracy, cut-sparsifier, and (Δ+1)-coloring, can be exactly solved or (1+ε)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require Ω̃(n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees, including BFS, DFS, and maximum-leaf spanning trees. Our results, in both the insertion-only and the turnstile models, are as follows. - Maximum-Leaf Spanning Trees: This problem is known to be APX-complete with inapproximability constant ρ ∈ [245/244, 2). By constructing an ε-MLST sparsifier, we show that for every constant ε > 0, MLST can be approximated in a single pass to within a factor of 1+ε w.h.p. (albeit in super-polynomial time for ε ≤ ρ-1 assuming P ≠ NP) and can be approximated in polynomial time in a single pass to within a factor of ρ_n+ε w.h.p., where ρ_n is the supremum constant that MLST cannot be approximated to within using polynomial time and Õ(n) space. In the insertion-only model, these algorithms can be deterministic. - BFS Trees: It is known that BFS trees require ω(1) passes to compute, but the naïve approach needs O(n) passes. We devise a new randomized algorithm that reduces the pass complexity to O(√n), and it offers a smooth tradeoff between pass complexity and space usage. This gives a polynomial separation between single-source and all-pairs shortest paths for unweighted graphs. - DFS Trees: It is unknown whether DFS trees require more than one pass. The current best algorithm by Khan and Mehta [STACS 2019] takes Õ(h) passes, where h is the height of computed DFS trees. Note that h can be as large as Ω(m/n) for n-node m-edge graphs. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for k-node-connectivity. Second, we present a randomized algorithm that reduces the pass complexity to O(√n), and it also offers a smooth tradeoff between pass complexity and space usage.
Cite as

Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai. Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.STACS.2020.34,
  author =	{Chang, Yi-Jun and Farach-Colton, Mart{\'\i}n and Hsu, Tsan-Sheng and Tsai, Meng-Tsung},
  title =	{{Streaming Complexity of Spanning Tree Computation}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{34:1--34:19},
  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.34},
  URN =		{urn:nbn:de:0030-drops-118951},
  doi =		{10.4230/LIPIcs.STACS.2020.34},
  annote =	{Keywords: Max-Leaf Spanning Trees, BFS Trees, DFS Trees}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.16
Syntactic Separation of Subset Satisfiability Problems

Authors: Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai

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

Abstract
Variants of the Exponential Time Hypothesis (ETH) have been used to derive lower bounds on the time complexity for certain problems, so that the hardness results match long-standing algorithmic results. In this paper, we consider a syntactically defined class of problems, and give conditions for when problems in this class require strongly exponential time to approximate to within a factor of (1-epsilon) for some constant epsilon > 0, assuming the Gap Exponential Time Hypothesis (Gap-ETH), versus when they admit a PTAS. Our class includes a rich set of problems from additive combinatorics, computational geometry, and graph theory. Our hardness results also match the best known algorithmic results for these problems.
Cite as

Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai. Syntactic Separation of Subset Satisfiability Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.APPROX-RANDOM.2019.16,
  author =	{Allender, Eric and Farach-Colton, Mart{\'\i}n and Tsai, Meng-Tsung},
  title =	{{Syntactic Separation of Subset Satisfiability Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.16},
  URN =		{urn:nbn:de:0030-drops-112319},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.16},
  annote =	{Keywords: Syntactic Class, Exponential Time Hypothesis, APX, PTAS}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.29
A Dichotomy Result for Cyclic-Order Traversing Games

Authors: Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Traversing game is a two-person game played on a connected undirected simple graph with a source node and a destination node. A pebble is placed on the source node initially and then moves autonomously according to some rules. Alice is the player who wants to set up rules for each node to determine where to forward the pebble while the pebble reaches the node, so that the pebble can reach the destination node. Bob is the second player who tries to deter Alice's effort by removing edges. Given access to Alice's rules, Bob can remove as many edges as he likes, while retaining the source and destination nodes connected. Under the guide of Alice's rules, if the pebble arrives at the destination node, then we say Alice wins the traversing game; otherwise the pebble enters an endless loop without passing through the destination node, then Bob wins. We assume that Alice and Bob both play optimally. We study the problem: When will Alice have a winning strategy? This actually models a routing recovery problem in Software Defined Networking in which some links may be broken. In this paper, we prove a dichotomy result for certain traversing games, called cyclic-order traversing games. We also give a linear-time algorithm to find the corresponding winning strategy, if one exists.
Cite as

Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai. A Dichotomy Result for Cyclic-Order Traversing Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.29,
  author =	{Chen, Yen-Ting and Tsai, Meng-Tsung and Tsai, Shi-Chun},
  title =	{{A Dichotomy Result for Cyclic-Order Traversing Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.29},
  URN =		{urn:nbn:de:0030-drops-99775},
  doi =		{10.4230/LIPIcs.ISAAC.2018.29},
  annote =	{Keywords: st-planar graphs, biconnectivity, fault-tolerant routing algorithms, software defined network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.47
Streaming Algorithms for Planar Convex Hulls

Authors: Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Many classical algorithms are known for computing the convex hull of a set of n point in R^2 using O(n) space. For large point sets, whose size exceeds the size of the working space, these algorithms cannot be directly used. The current best streaming algorithm for computing the convex hull is computationally expensive, because it needs to solve a set of linear programs. In this paper, we propose simpler and faster streaming and W-stream algorithms for computing the convex hull. Our streaming algorithm has small pass complexity, which is roughly a square root of the current best bound, and it is simpler in the sense that our algorithm mainly relies on computing the convex hulls of smaller point sets. Our W-stream algorithms, one of which is deterministic and the other of which is randomized, have nearly-optimal tradeoff between the pass complexity and space usage, as we established by a new unconditional lower bound.
Cite as

Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai. Streaming Algorithms for Planar Convex Hulls. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{farachcolton_et_al:LIPIcs.ISAAC.2018.47,
  author =	{Farach-Colton, Mart{\'\i}n and Li, Meng and Tsai, Meng-Tsung},
  title =	{{Streaming Algorithms for Planar Convex Hulls}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.47},
  URN =		{urn:nbn:de:0030-drops-99951},
  doi =		{10.4230/LIPIcs.ISAAC.2018.47},
  annote =	{Keywords: Convex Hulls, Streaming Algorithms, Lower Bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact