81 Search Results for "Hon, Wing-Kai"

Volume

LIPIcs, Volume 359

36th International Symposium on Algorithms and Computation (ISAAC 2025)

ISAAC 2025, December 7-10, 2025, Tainan, Taiwan

Editors: Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai

Document
DOI: 10.4230/LIPIcs.SEA.2026.13
Practical Parallel Block Tree Construction

Authors: Robert Clausecker, Florian Kurpicz, and Etienne Palanga

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

Abstract
The block tree [Belazzougui et al., J. Comput. Syst. Sci. '21] is a compressed representation of a length-n text that supports access, rank, and select queries while requiring only O(z log n/z) words of space, where z is the number of Lempel-Ziv factors of the text. In other words, its space requirements are asymptotically comparable to those of the compressed text itself. In practice, block trees offer query performance comparable to that of state-of-the-art compressed rank and select indices. However, their construction is significantly slower, and the fastest known construction algorithms additionally require a significant amount of working memory. To address these limitations, we propose fast and lightweight parallel algorithms for the efficient construction of block trees. Our algorithm achieves similar construction speed than the currently fastest block tree construction algorithm on a single core and is up to eight times faster using 64 cores, while requiring an order of magnitude less memory. Overall, we achieve a speedup of up to 15.5 on 64 cores, which is in line with the parallel construction of the Lempel-Ziv compression.
Cite as

Robert Clausecker, Florian Kurpicz, and Etienne Palanga. Practical Parallel Block Tree Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{clausecker_et_al:LIPIcs.SEA.2026.13,
  author =	{Clausecker, Robert and Kurpicz, Florian and Palanga, Etienne},
  title =	{{Practical Parallel Block Tree Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.13},
  URN =		{urn:nbn:de:0030-drops-260175},
  doi =		{10.4230/LIPIcs.SEA.2026.13},
  annote =	{Keywords: block tree, shared memory, compression, SIMD, Karp-Rabin fingerprints}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.14
Hardness Results on Characteristics for Elastic-Degenerate Strings

Authors: Dominik Köppl and Jannik Olbrich

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

Abstract
Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al., 2022]. In that light, we wonder about other types of queries that are of particular interest to bioinformatics: unique substrings, absent words, anti-powers, longest previous factors, and Lempel-Ziv-like compression schemes. While we obtain a polynomial time algorithm for a variation of longest previous factors, we show that all other problems are NP-hard to compute, some of them even under the restriction that the input can be modeled as an indeterminate or GD string.
Cite as

Dominik Köppl and Jannik Olbrich. Hardness Results on Characteristics for Elastic-Degenerate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.14,
  author =	{K\"{o}ppl, Dominik and Olbrich, Jannik},
  title =	{{Hardness Results on Characteristics for Elastic-Degenerate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.14},
  URN =		{urn:nbn:de:0030-drops-259409},
  doi =		{10.4230/LIPIcs.CPM.2026.14},
  annote =	{Keywords: Elastic-degenerate strings, NP-hardness, longest common factor, minimal unique substring, minimal absent word, anti-power, longest previous factor}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.35
Efficient Index for Square Pattern Matching

Authors: Po-Chun Chen, Che-Wei Tsao, Wing-Kai Hon, and Dominik Köppl

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

Abstract
A string S is called a square if it can be written as the concatenation of two identical strings. Two strings P and Q of the same length are said to square match if, for every substring of P, it is a square if and only if the corresponding substring of Q is also a square. The square pattern matching problem asks for locating all substrings of a given text T of length n that square match a query pattern P of length m. This notion captures similarity in repetition structures and is motivated by applications in areas such as bioinformatics and music structure analysis. In this paper, we introduce a novel technique, called the longest prefix square (LPS) encoding, which represents the square structure of a string as an integer array of the same length. We show that two strings square match if and only if they have identical LPS encodings. Based on this result, we construct an index solving the square pattern matching problem in time O(m lg m + occ) using O(nlg²n) bits of space, where occ denotes the number of occurrences of substrings in T that square match P. If the LPS encoding of P is precomputed, the query time improves to O(m + occ).
Cite as

Po-Chun Chen, Che-Wei Tsao, Wing-Kai Hon, and Dominik Köppl. Efficient Index for Square Pattern Matching. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 35:1-35:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CPM.2026.35,
  author =	{Chen, Po-Chun and Tsao, Che-Wei and Hon, Wing-Kai and K\"{o}ppl, Dominik},
  title =	{{Efficient Index for Square Pattern Matching}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{35:1--35:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.35},
  URN =		{urn:nbn:de:0030-drops-259617},
  doi =		{10.4230/LIPIcs.CPM.2026.35},
  annote =	{Keywords: string algorithms, pattern matching, indexing, squares}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.36
Set Parameterized Matching via Multi-Layer Hashing

Authors: Moshe Lewenstein and Ely Porat

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

Abstract
We study the set parameterized matching problem, a generalization of the classical parameterized matching problem introduced by Baker [Baker, 1993; Baker, 1997]. In set parameterized matching, both the pattern and text are sequences where each position contains a set of characters rather than a single character. Two set-strings parameterized match if there exists a bijection between their alphabets that maps one to the other set-wise. Boussidan [Aaron Boussidan, 2025] introduced this problem for the case of equal-length set-strings. We present a randomized algorithm running in O(N + M) time with high probability, where N is the text size and M is the pattern size. Our approach employs a novel three-layer hashing scheme based on Karp-Rabin fingerprinting that addresses the challenges of (1) the size blowup in representations of the problem, (2) set-to-set matching, and (3) the dynamic nature of encodings of text substrings during pattern scanning.
Cite as

Moshe Lewenstein and Ely Porat. Set Parameterized Matching via Multi-Layer Hashing. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lewenstein_et_al:LIPIcs.CPM.2026.36,
  author =	{Lewenstein, Moshe and Porat, Ely},
  title =	{{Set Parameterized Matching via Multi-Layer Hashing}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.36},
  URN =		{urn:nbn:de:0030-drops-259620},
  doi =		{10.4230/LIPIcs.CPM.2026.36},
  annote =	{Keywords: Set Parameterized Matching, Pattern Matching, Randomized Algorithms, Hashing, Parameterized Matching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.26
Approximate Cartesian Tree Matching with Substitutions

Authors: Panagiotis Charalampopoulos, Jonas Ellert, and Manal Mohamed

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The Cartesian tree of a sequence captures the relative order of the sequence’s elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly due to its applications in time series analysis. Consider a text T of length n and a pattern P of length m. In the exact Cartesian tree matching problem, the task is to find all length-m fragments of T whose Cartesian tree coincides with the Cartesian tree CT(P) of the pattern. Although the exact version of the problem can be solved in linear time [Park et al., TCS 2020], it remains rather restrictive; for example, it is not robust to outliers in the pattern. To overcome this limitation, we consider the approximate setting, where the goal is to identify all fragments of T that are close to some string whose Cartesian tree matches CT(P). In this work, we quantify closeness via the widely used Hamming distance metric. For a given integer parameter k > 0, we present an algorithm that computes all fragments of T that are at Hamming distance at most k from a string whose Cartesian tree matches CT(P). Our algorithm runs in time 𝒪(n √m ⋅ k^{2.5}) for k ≤ m^{1/5} and in time 𝒪(nk⁵) for k ≥ m^{1/5}, thereby improving upon the state-of-the-art 𝒪(nmk)-time algorithm of Kim and Han [TCS 2025] in the regime k = o(m^{1/4}). On the way to our solution, we develop a toolbox of independent interest. First, we introduce a new notion of periodicity in Cartesian trees. Then, we lift multiple well-known combinatorial and algorithmic results for string matching and periodicity in strings to Cartesian tree matching and periodicity in Cartesian trees.
Cite as

Panagiotis Charalampopoulos, Jonas Ellert, and Manal Mohamed. Approximate Cartesian Tree Matching with Substitutions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.STACS.2026.26,
  author =	{Charalampopoulos, Panagiotis and Ellert, Jonas and Mohamed, Manal},
  title =	{{Approximate Cartesian Tree Matching with Substitutions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{26:1--26:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.26},
  URN =		{urn:nbn:de:0030-drops-255151},
  doi =		{10.4230/LIPIcs.STACS.2026.26},
  annote =	{Keywords: Cartesian tree, Hamming distance, approximate pattern matching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.53
Maximum Reachability Orientation of Mixed Graphs

Authors: Florian Hörsch

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We aim to find orientations of mixed graphs optimizing the total reachability, a problem that has applications in causality and biology. For given a digraph D, we use P(D) for the set of ordered pairs of distinct vertices in V(D) and we define κ_D:P(D) → {0,1} by κ_D(u,v) = 1 if v is reachable from u in D, and κ_D(u,v) = 0, otherwise. We use R(D) = ∑_{(u,v) ∈ P(D)}κ_D(u,v). Now, given a mixed graph G, we aim to find an orientation x⃑{G} of G that maximizes R(x⃑{G}). Hakimi, Schmeichel, and Young proved that the problem can be solved in polynomial time when restricted to undirected inputs. They inquired about the complexity in mixed graphs. We answer this question by showing that this problem is NP-hard, and, moreover, APX-hard. We then develop a finer understanding of how quickly the problem becomes difficult when going from undirected to mixed graphs. To this end, we consider the parameterized complexity of the problem with respect to the number k of preoriented arcs of G, a poorly studied form of parameterization. We show that the problem can be solved in time n^{O(k)} and that a (1-ε)-approximation can be computed in time f(k,ε)n^{O(1)} for any ε > 0.
Cite as

Florian Hörsch. Maximum Reachability Orientation of Mixed Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{horsch:LIPIcs.STACS.2026.53,
  author =	{H\"{o}rsch, Florian},
  title =	{{Maximum Reachability Orientation of Mixed Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.53},
  URN =		{urn:nbn:de:0030-drops-255421},
  doi =		{10.4230/LIPIcs.STACS.2026.53},
  annote =	{Keywords: orientations, mixed graphs, reachability, parameterized complexity, approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.10
New Algorithmic Directions in Optimal Transport and Applications for Product Spaces

Authors: Salman Beigi, Omid Etesami, Mohammad Mahmoody, and Amir Najafi

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We consider the problem of optimal transport between two high-dimensional distributions μ,ν in ℝⁿ from a new algorithmic perspective, in which we are given a sample x ∼ μ and we have to find a close y ∼ ν while running in poly(n) time, where n is the size/dimension of x,y. In other words, we are interested in making the running time bounded in dimension of the spaces rather than bounded in the total size of the representations of the two distributions. Our main result is a general algorithmic transport result between any product distribution μ and an arbitrary distribution ν of total cost Δ + δ under 𝓁_p^p cost; here Δ is the cost of the so-called Knothe–Rosenblatt transport from μ to ν, while δ is a computational error that goes to zero for larger running time in the transport algorithm. For this result, we need ν to be "sequentially samplable" with a "bounded average sampling cost" which is a novel but natural notion of independent interest. In addition, we prove the following. - We prove an algorithmic version of the celebrated Talagrand’s inequality for transporting the standard Gaussian distribution Φⁿ to an arbitrary ν under the Euclidean-squared cost. When ν is Φⁿ conditioned on a set S of measure ε, we show how to implement the needed sequential sampler for ν in expected time poly(n/ε), using membership oracle access to S. Hence, we obtain an algorithmic transport that maps Φⁿ to Φⁿ|S in time poly(n/ε) and expected Euclidean-squared distance O(log 1/ε), which is optimal for a general set S of measure ε. - As corollary, we find the first computational concentration (Etesami et al. SODA 2020) result for the Gaussian measure under the Euclidean distance with a dimension-independent transportation cost, resolving a question of Etesami et al. More precisely, for any set S of Gaussian measure ε, we map most of Φⁿ samples to S with Euclidean distance O(√{log 1/ε}) in time poly(n/ε).
Cite as

Salman Beigi, Omid Etesami, Mohammad Mahmoody, and Amir Najafi. New Algorithmic Directions in Optimal Transport and Applications for Product Spaces. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beigi_et_al:LIPIcs.ISAAC.2025.10,
  author =	{Beigi, Salman and Etesami, Omid and Mahmoody, Mohammad and Najafi, Amir},
  title =	{{New Algorithmic Directions in Optimal Transport and Applications for Product Spaces}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.10},
  URN =		{urn:nbn:de:0030-drops-249187},
  doi =		{10.4230/LIPIcs.ISAAC.2025.10},
  annote =	{Keywords: Optimal transport, Randomized algorithms, Concentration bounds}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.8
Parameterized Algorithms for the Drone Delivery Problem

Authors: Simon Bartlmae, Andreas Hene, Joshua Könen, and Heiko Röglin

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Timely delivery and optimal routing remain fundamental challenges in the modern logistics industry. Building on prior work that considers single-package delivery across networks using multiple types of collaborative agents with restricted movement areas (e.g., drones or trucks), we examine the complexity of the problem under structural and operational constraints. Our focus is on minimizing total delivery time by coordinating agents that differ in speed and movement range across a graph. This problem formulation aligns with the recently proposed Drone Delivery Problem with respect to delivery time (DDT), introduced by Erlebach et al. [ISAAC 2022]. We first resolve an open question posed by Erlebach et al. [ISAAC 2022] by showing that even when the delivery network is a path graph, DDT admits no polynomial-time approximation within any polynomially encodable factor a(n), unless P=NP. Additionally, we identify the intersection graph of the agents, where nodes represent agents and edges indicate an overlap of the movement areas of two agents, as an important structural concept. For path graphs, we show that DDT becomes tractable when parameterized by the treewidth w of the intersection graph, and we present an exact FPT algorithm with running time f(w)⋅poly(n,k), for some computable function f. For general graphs, we give an FPT algorithm with running time f(Δ,w)⋅poly(n,k), where Δ is the maximum degree of the intersection graph. In the special case where the intersection graph is a tree, we provide a simple polynomial-time algorithm.
Cite as

Simon Bartlmae, Andreas Hene, Joshua Könen, and Heiko Röglin. Parameterized Algorithms for the Drone Delivery Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bartlmae_et_al:LIPIcs.ISAAC.2025.8,
  author =	{Bartlmae, Simon and Hene, Andreas and K\"{o}nen, Joshua and R\"{o}glin, Heiko},
  title =	{{Parameterized Algorithms for the Drone Delivery Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.8},
  URN =		{urn:nbn:de:0030-drops-249162},
  doi =		{10.4230/LIPIcs.ISAAC.2025.8},
  annote =	{Keywords: Complexity, Delivery, FPT algorithms, Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.7
Polynomial Equivalence of Extended Chemical Reaction Models

Authors: Divya Bajaj, Jose-Luis Castellanos, Ryan Knobel, Austin Luchsinger, Aiden Massie, Adrian Salinas, Pablo Santos, Ramiro Santos, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The ability to detect whether a species (or dimension) is zero in Chemical Reaction Networks (CRN), Vector Addition Systems, or Petri Nets is known to increase the power of these models - making them capable of universal computation. While this ability may appear in many forms, such as extending the models to allow transitions to be inhibited, prioritized, or synchronized, we present an extension that directly performs this zero checking. We introduce a new void genesis CRN variant with a simple design that merely increments the count of a specific species when any other species' count goes to zero. As with previous extensions, we show that the model is Turing Universal. We then analyze several other studied CRN variants and show that they are all equivalent through a polynomial simulation with the void genesis model, which does not merely follow from Turing-universality. Thus, inhibitor species, reactions that occur at different rates, being allowed to run reactions in parallel, or even being allowed to continually add more volume to the CRN, does not add additional simulation power beyond simply detecting if a species count becomes zero.
Cite as

Divya Bajaj, Jose-Luis Castellanos, Ryan Knobel, Austin Luchsinger, Aiden Massie, Adrian Salinas, Pablo Santos, Ramiro Santos, Robert Schweller, and Tim Wylie. Polynomial Equivalence of Extended Chemical Reaction Models. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bajaj_et_al:LIPIcs.ISAAC.2025.7,
  author =	{Bajaj, Divya and Castellanos, Jose-Luis and Knobel, Ryan and Luchsinger, Austin and Massie, Aiden and Salinas, Adrian and Santos, Pablo and Santos, Ramiro and Schweller, Robert and Wylie, Tim},
  title =	{{Polynomial Equivalence of Extended Chemical Reaction Models}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.7},
  URN =		{urn:nbn:de:0030-drops-249158},
  doi =		{10.4230/LIPIcs.ISAAC.2025.7},
  annote =	{Keywords: Chemical Reaction Networks, Simulations, Petri-nets, Vector Addition Systems, Bi-simulation, Turing-universality, Inhibitors}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.5
Graph Coloring Below Guarantees via Co-Triangle Packing

Authors: Shyan Akmal and Tomohiro Koana

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In the 𝓁-Coloring problem, we are given a graph on n nodes, and tasked with determining if its vertices can be properly colored using 𝓁 colors. In this paper we study below-guarantee graph coloring, which tests whether an n-vertex graph can be properly colored using g-k colors, where g is a trivial upper bound such as n. We introduce an algorithmic framework that builds on a packing of co-triangles K₃ (independent sets of three vertices): the algorithm greedily finds co-triangles and employs a win-win analysis. If many are found, we immediately return yes; otherwise these co-triangles form a small co-triangle modulator, whose deletion makes the graph co-triangle-free. Extending the work of [Gutin et al., SIDMA 2021], who solved 𝓁-Coloring (for any 𝓁) in randomized O^∗(2^k) time when given a K₂-free modulator of size k, we show that this problem can likewise be solved in randomized O^*(2^{k}) time when given a K₃-free modulator of size k. This result in turn yields a randomized O^*(2^{3k/2}) algorithm for (n-k)-Coloring (also known as Dual Coloring), improving the previous O^*(4^k) bound. We then introduce a smaller parameterization, (ω+μ-k)-Coloring, where ω is the clique number and μ is the size of a maximum matching in the complement graph; since ω+μ ≤ n for any graph, this problem is strictly harder. Using the same co-triangle-packing argument, we obtain a randomized O^*(2^{6k}) algorithm, establishing its fixed-parameter tractability for a smaller parameter. Complementing this finding, we show that no fixed-parameter tractable algorithm exists for (ω-k)-Coloring or (μ-k)-Coloring under standard complexity assumptions.
Cite as

Shyan Akmal and Tomohiro Koana. Graph Coloring Below Guarantees via Co-Triangle Packing. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ISAAC.2025.5,
  author =	{Akmal, Shyan and Koana, Tomohiro},
  title =	{{Graph Coloring Below Guarantees via Co-Triangle Packing}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.5},
  URN =		{urn:nbn:de:0030-drops-249130},
  doi =		{10.4230/LIPIcs.ISAAC.2025.5},
  annote =	{Keywords: coloring, parameterized algorithms, algebraic algorithms, above-guarantee, below-guarantee, subset convolution, determinants}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.9
Small Space Encoding and Recognition of k-Palindromic Prefixes

Authors: Gabriel Bathie, Jonas Ellert, and Tatiana Starikovskaya

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Palindromes are non-empty strings that read the same forward and backward. We study the problem of recognizing so-called k-palindromic strings, which can be represented as the concatenation of exactly k palindromes. [Rubinchik and Shur, MFCS 2020] showed that the problem is solvable in linear space and time. We present a read-only algorithm that recognizes all k-palindromic prefixes of a string T of length n in O(n ⋅ 6^{k²} ⋅ log^k n) time and O(6^{k²} ⋅ log^k n) space. As a corollary, we also obtain a read-only algorithm for computing the palindromic length of T, i.e., the smallest k such that T is k-palindromic, in O(n ⋅ 6^{k²} ⋅ log^⌈k/2⌉ n) time and O(6^{k²} ⋅ log^⌈k/2⌉ n) space.
Cite as

Gabriel Bathie, Jonas Ellert, and Tatiana Starikovskaya. Small Space Encoding and Recognition of k-Palindromic Prefixes. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bathie_et_al:LIPIcs.ISAAC.2025.9,
  author =	{Bathie, Gabriel and Ellert, Jonas and Starikovskaya, Tatiana},
  title =	{{Small Space Encoding and Recognition of k-Palindromic Prefixes}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.9},
  URN =		{urn:nbn:de:0030-drops-249178},
  doi =		{10.4230/LIPIcs.ISAAC.2025.9},
  annote =	{Keywords: palindromic length, read-only algorithms, palindromes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.4
Finding d-Cuts in Claw-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets B and R such that the edges between B and R form a matching, that is, every vertex in B has at most one neighbour in R, and vice versa. If for some integer d ≥ 1, we allow every vertex in B to have at most d neighbours in R, and vice versa, we obtain the more general problem d-Cut. It is known that d-Cut is NP-complete for every d ≥ 1. However, for claw-free graphs, it is only known that d-Cut is polynomial-time solvable for d = 1 and NP-complete for d ≥ 3. We resolve the missing case d = 2 by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every d ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 2d+3. Moreover, in the former case, we can find a d-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to S_{1^t,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times.
Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith. Finding d-Cuts in Claw-Free Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2025.4,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Paulusma, Dani\"{e}l and Smith, Siani},
  title =	{{Finding d-Cuts in Claw-Free Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.4},
  URN =		{urn:nbn:de:0030-drops-249121},
  doi =		{10.4230/LIPIcs.ISAAC.2025.4},
  annote =	{Keywords: matching cut, d-cut, claw-free, maximum degree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.6
A Dimension-Reducing Fréchet Simplification Oracle

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n).
Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. A Dimension-Reducing Fréchet Simplification Oracle. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2025.6,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{A Dimension-Reducing Fr\'{e}chet Simplification Oracle}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.6},
  URN =		{urn:nbn:de:0030-drops-249149},
  doi =		{10.4230/LIPIcs.ISAAC.2025.6},
  annote =	{Keywords: Computational geometry, discrete Fr\'{e}chet distance, curve simplification oracle, restricted minimum enclosing disk queries}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.3
Circle-Segment Intersection Queries in Connected Geometric Graphs

Authors: Peyman Afshani, Yannick Bosch, and Sabine Storandt

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.
Cite as

Peyman Afshani, Yannick Bosch, and Sabine Storandt. Circle-Segment Intersection Queries in Connected Geometric Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ISAAC.2025.3,
  author =	{Afshani, Peyman and Bosch, Yannick and Storandt, Sabine},
  title =	{{Circle-Segment Intersection Queries in Connected Geometric Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.3},
  URN =		{urn:nbn:de:0030-drops-249114},
  doi =		{10.4230/LIPIcs.ISAAC.2025.3},
  annote =	{Keywords: Intersection data structure, Graph partitioning, Dobkin-Kirkpatrick hierarchy}
}
  • Refine by Type
  • 80 Document/PDF
  • 73 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 6 2026
  • 71 2025
  • 1 2018
  • 3 2016

  • Refine by Author
  • 8 Hon, Wing-Kai
  • 5 Thankachan, Sharma V.
  • 4 Shah, Rahul
  • 3 Ferragina, Paolo
  • 3 Ganguly, Arnab
  • Show More...

  • Refine by Series/Journal
  • 73 LIPIcs
  • 7 OASIcs

  • Refine by Classification
  • 12 Theory of computation → Design and analysis of algorithms
  • 11 Theory of computation → Pattern matching
  • 10 Theory of computation → Graph algorithms analysis
  • 8 Theory of computation → Computational geometry
  • 7 Theory of computation
  • Show More...

  • Refine by Keyword
  • 4 Computational geometry
  • 3 Burrows-Wheeler transform
  • 3 NP-hardness
  • 3 Sparsification
  • 3 pattern matching
  • 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