76 Search Results for "Iwata, Satoru"

Volume

LIPIcs, Volume 283

34th International Symposium on Algorithms and Computation (ISAAC 2023)

ISAAC 2023, December 3-6, 2023, Kyoto, Japan

Editors: Satoru Iwata and Naonori Kakimura

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.46
Finding Small Dijoins in Transitive Closure Time

Authors: Chaitanya Nalam and Thatchaphol Saranurak

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We present a faster algorithm for finding a minimum dijoin, a smallest set of edges whose contraction makes a directed graph strongly connected. This problem has been studied since the 1960s [Seshu and Reed 1961] and is dual to finding a maximum sized family of disjoint dicuts [Lucchesi and Younger 1978]. Given a directed graph G with n vertices and m edges whose minimum dijoin has size d, our algorithm outputs both a minimum dijoin and a maximum sized family of disjoint dicuts in O(TC⋅ d) time, where TC = min(mn,n^ω) is the time to compute the transitive closure. This improves upon the state of the art of [Gabow 1993], which requires O(TC ⋅ min(m^{1/2},n^{2/3})) time when d = o(min(m^{1/2},n^{2/3})). Our result extends to finding a minimum weighted dijoin. We achieve this by observing that Frank’s algorithm [Frank 1981] can be sped up when warm-started with a 2-approximation solution, which we observed can be computed in near-linear time.
Cite as

Chaitanya Nalam and Thatchaphol Saranurak. Finding Small Dijoins in Transitive Closure Time. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 46:1-46:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nalam_et_al:LIPIcs.FSTTCS.2025.46,
  author =	{Nalam, Chaitanya and Saranurak, Thatchaphol},
  title =	{{Finding Small Dijoins in Transitive Closure Time}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{46:1--46:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-251265},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.46},
  annote =	{Keywords: Graph algorithms, Dijoin, Submodular flow}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.11
Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure

Authors: Mark de Berg, Andrés López Martínez, and Frits Spieksma

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

Abstract
We generalize the polynomial-time solvability of k-Diverse Minimum s-t Cuts (De Berg et al., ISAAC'23) to a wider class of combinatorial problems whose solution sets have a distributive lattice structure. We identify three structural conditions that, when met by a problem, ensure that a k-sized multiset of maximally-diverse solutions - measured by the sum of pairwise Hamming distances - can be found in polynomial time. We apply this framework to obtain polynomial-time algorithms for finding diverse minimum s-t cuts, diverse stable matchings, and diverse market-clearing price vectors. Moreover, we show that the framework extends to two other natural measures of diversity. Lastly, we present a simpler algorithmic framework for finding a largest set of pairwise disjoint solutions in problems that meet these structural conditions.
Cite as

Mark de Berg, Andrés López Martínez, and Frits Spieksma. Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.11,
  author =	{de Berg, Mark and L\'{o}pez Mart{\'\i}nez, Andr\'{e}s and Spieksma, Frits},
  title =	{{Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{11:1--11:19},
  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.11},
  URN =		{urn:nbn:de:0030-drops-249197},
  doi =		{10.4230/LIPIcs.ISAAC.2025.11},
  annote =	{Keywords: Diversity, Lattice Theory, Submodular Function Minimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.112
A Faster Parametric Search for the Integral Quickest Transshipment Problem

Authors: Mariia Anapolska, Dario van den Boom, Christina Büsing, and Timo Gersing

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

Abstract
Algorithms for computing fractional solutions to the quickest transshipment problem have been significantly improved since Hoppe and Tardos first solved the problem in strongly polynomial time. For integral solutions, however, no structural improvements on their algorithm itself have yet been proposed. Runtime improvements are limited to general progress on submodular function minimization (SFM), which is an integral part of Hoppe and Tardos' algorithm. In fact, SFM constitutes the main computational load of the algorithm, as the runtime is blown up by using it within Megiddo’s parametric search algorithm. We replace this part of Hoppe and Tardos' algorithm with a more efficient routine that solves only a linear number of SFM and, in contrast to previous techniques, exclusively uses minimum cost flow algorithms within Megiddo’s parametric search. Our approach improves the state-of-the-art runtime from 𝒪̃(m⁴ k^15) down to 𝒪̃(m²k⁵ + m⁴ k²), where k is the number of terminals and m is the number of arcs.
Cite as

Mariia Anapolska, Dario van den Boom, Christina Büsing, and Timo Gersing. A Faster Parametric Search for the Integral Quickest Transshipment Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 112:1-112:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anapolska_et_al:LIPIcs.ESA.2025.112,
  author =	{Anapolska, Mariia and van den Boom, Dario and B\"{u}sing, Christina and Gersing, Timo},
  title =	{{A Faster Parametric Search for the Integral Quickest Transshipment Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{112:1--112:15},
  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.112},
  URN =		{urn:nbn:de:0030-drops-245817},
  doi =		{10.4230/LIPIcs.ESA.2025.112},
  annote =	{Keywords: Flow over time, dynamic transshipment, quickest transshipment, parametric submodular functions, efficient algorithms}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.23
Novel Complexity Results for Temporal Separators with Deadlines

Authors: Riccardo Dondi and Manuel Lafond

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

Abstract
We consider two variants, (s,z,𝓁)-Temporal Separator and (s,z,𝓁)-Temporal Cut, respectively, of the vertex separator and the edge cut problem in temporal graphs. The goal is to remove the minimum number of vertices (temporal edges, respectively) in order to delete all the temporal paths that have time travel at most 𝓁 between a source vertex s and target vertex z. First, we solve an open problem in the literature showing that (s,z,𝓁)-Temporal Separator is NP-hard even when the underlying graph has pathwidth bounded by four. We complement this result showing that (s,z,𝓁)-Temporal Separator can be solved in polynomial time for graphs of pathwidth bounded by three. Then we consider the approximability of (s,z,𝓁)-Temporal Separator and we show that it cannot be approximated within factor 2^Ω(log^{1-ε}|V|) for any constant ε > 0, unless NP ⊆ ZPP (V is the vertex set of the input temporal graph) and that the strict version is approximable within factor 𝓁-1 (we show also that it is unliklely that this factor can be improved). Then we consider the (s,z,𝓁)-Temporal Cut problem, we show that it is APX-hard and we present a 2 log₂(2𝓁) approximation algorithm.
Cite as

Riccardo Dondi and Manuel Lafond. Novel Complexity Results for Temporal Separators with Deadlines. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dondi_et_al:LIPIcs.WADS.2025.23,
  author =	{Dondi, Riccardo and Lafond, Manuel},
  title =	{{Novel Complexity Results for Temporal Separators with Deadlines}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{23:1--23:14},
  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.23},
  URN =		{urn:nbn:de:0030-drops-242545},
  doi =		{10.4230/LIPIcs.WADS.2025.23},
  annote =	{Keywords: Temporal Graphs, Graph Algorithms, Graph Separators, Parameterized Complexity, Approximation Complexity}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.41
Scheduling on Identical Machines with Setup Time and Unknown Execution Time

Authors: Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, and Hanna Sumita

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

Abstract
In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines.
Cite as

Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, and Hanna Sumita. Scheduling on Identical Machines with Setup Time and Unknown Execution Time. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.WADS.2025.41,
  author =	{Kawase, Yasushi and Makino, Kazuhisa and Phan, Vinh Long and Sumita, Hanna},
  title =	{{Scheduling on Identical Machines with Setup Time and Unknown Execution Time}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{41:1--41:16},
  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.41},
  URN =		{urn:nbn:de:0030-drops-242728},
  doi =		{10.4230/LIPIcs.WADS.2025.41},
  annote =	{Keywords: Online scheduling, Competitive analysis, Makespan minimization, Identical machines scheduling}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.50
Deterministic (2/3 - ε)-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries

Authors: Tatsuya Terao

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

Abstract
In the matroid intersection problem, we are given two matroids ℳ₁ = (V, ℐ₁) and ℳ₂ = (V, ℐ₂) defined on the same ground set V of n elements, and the objective is to find a common independent set S ∈ ℐ₁ ∩ ℐ₂ of largest possible cardinality, denoted by r. In this paper, we consider a deterministic matroid intersection algorithm with only a nearly linear number of independence oracle queries. Our contribution is to present a deterministic O(n/(ε) + r log r)-independence-query (2/3-ε)-approximation algorithm for any ε > 0. Our idea is very simple: we apply a recent Õ(n √r/ε)-independence-query (1 - ε)-approximation algorithm of Blikstad [ICALP 2021], but terminate it before completion. Moreover, we also present a semi-streaming algorithm for (2/3 -ε)-approximation of matroid intersection in O(1/ε) passes.
Cite as

Tatsuya Terao. Deterministic (2/3 - ε)-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{terao:LIPIcs.WADS.2025.50,
  author =	{Terao, Tatsuya},
  title =	{{Deterministic (2/3 - \epsilon)-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{50:1--50:18},
  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.50},
  URN =		{urn:nbn:de:0030-drops-242812},
  doi =		{10.4230/LIPIcs.WADS.2025.50},
  annote =	{Keywords: Matroid intersection, approximation algorithm, streaming algorithm}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.20
Subsequence-Based Indices for Genome Sequence Analysis

Authors: Giovanni Buzzega, Alessio Conte, Veronica Guerrini, Giulia Punzi, Giovanna Rosone, and Lorenzo Tattini

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
Compact indices are a fundamental tool in string analysis, even more so in bioinformatics, where genomic sequences can reach billions in length. This paper presents some recent results in which Roberto Grossi has been involved, showing how some of these indices do more than just efficiently represent data, but rather are able to bring out salient information within it, which can be exploited for their downstream analysis. Specifically, we first review a recently-introduced method [Guerrini et al., 2023] that employs the Burrows-Wheeler Transform to build reasonably accurate phylogenetic trees in an assembly-free scenario. We then describe a recent practical tool [Buzzega et al., 2025] for indexing Maximal Common Subsequences between strings, which can enable analysis of genomic sequence similarity. Experimentally, we show that the results produced by the one index are consistent with the expectations about the results of the other index.
Cite as

Giovanni Buzzega, Alessio Conte, Veronica Guerrini, Giulia Punzi, Giovanna Rosone, and Lorenzo Tattini. Subsequence-Based Indices for Genome Sequence Analysis. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buzzega_et_al:OASIcs.Grossi.20,
  author =	{Buzzega, Giovanni and Conte, Alessio and Guerrini, Veronica and Punzi, Giulia and Rosone, Giovanna and Tattini, Lorenzo},
  title =	{{Subsequence-Based Indices for Genome Sequence Analysis}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{20:1--20:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.20},
  URN =		{urn:nbn:de:0030-drops-238199},
  doi =		{10.4230/OASIcs.Grossi.20},
  annote =	{Keywords: String Indices, Burrows-Wheeler Transform, Maximal Common Subsequences, Sequence Analysis, Phylogeny}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

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

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36: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.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.15
Encoding Co-Lex Orders of Finite-State Automata in Linear Space

Authors: Ruben Becker, Nicola Cotumaccio, Sung-Hwan Kim, Nicola Prezza, and Carlo Tosoni

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
The Burrows-Wheeler transform (BWT) is a string transformation that enhances string indexing and compressibility. Cotumaccio and Prezza [SODA '21] extended this transformation to nondeterministic finite automata (NFAs) through co-lexicographic partial orders, i.e., by sorting the states of an NFA according to the co-lexicographic order of the strings reaching them. As the BWT of an NFA shares many properties with its original string variant, the transformation can be used to implement indices for locating specific patterns on the NFA itself. The efficiency of the resulting index is influenced by the width of the partial order on the states: the smaller the width, the faster the index. The most efficient index for arbitrary NFAs currently known in the literature is based on the coarsest forward-stable co-lex (CFS) order of Becker et al. [SPIRE '24]. In this paper, we prove that this CFS order can be encoded within linear space in the number of states in the automaton. The importance of this result stems from the fact that encoding such an order in linear space represents a big first step in the direction of building the index based on this order in near-linear time - the biggest open research question in this context. The currently most efficient known algorithm for this task run in quadratic time in the number of transitions in the NFA and are thus infeasible to run on very large graphs (e.g., pangenome graphs). At this point, a near-linear time algorithm is solely known for the simpler case of deterministic automata [Becker et al., ESA '23] and, in fact, this algorithmic result was enabled by a linear space encoding for deterministic automata [Kim et al., CPM '23].
Cite as

Ruben Becker, Nicola Cotumaccio, Sung-Hwan Kim, Nicola Prezza, and Carlo Tosoni. Encoding Co-Lex Orders of Finite-State Automata in Linear Space. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.CPM.2025.15,
  author =	{Becker, Ruben and Cotumaccio, Nicola and Kim, Sung-Hwan and Prezza, Nicola and Tosoni, Carlo},
  title =	{{Encoding Co-Lex Orders of Finite-State Automata in Linear Space}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.15},
  URN =		{urn:nbn:de:0030-drops-231094},
  doi =		{10.4230/LIPIcs.CPM.2025.15},
  annote =	{Keywords: Burrows-Wheeler Transform, Co-Lexicographic Orders, Nondeterministic Finite Automata, Graph Walks}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.42
Local Enumeration: The Not-All-Equal Case

Authors: Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, and Navid Talebanfard

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number k and a parameter t, given an n-variate k-CNF with no satisfying assignment of Hamming weight less than t(n), enumerate all satisfying assignments of Hamming weight exactly t(n). Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely k = 3. In particular, they solved Enum(3, n/2) in expected 1.598ⁿ time. A simple construction shows a lower bound of 6^{n/4} ≈ 1.565ⁿ. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number k and a parameter t, given an n-variate k-CNF with no satisfying assignment of Hamming weight less than t(n), enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly t(n), i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time poly(n) ⋅ 6^{n/4}.
Cite as

Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, and Navid Talebanfard. Local Enumeration: The Not-All-Equal Case. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gurumukhani_et_al:LIPIcs.STACS.2025.42,
  author =	{Gurumukhani, Mohit and Paturi, Ramamohan and Saks, Michael and Talebanfard, Navid},
  title =	{{Local Enumeration: The Not-All-Equal Case}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.42},
  URN =		{urn:nbn:de:0030-drops-228680},
  doi =		{10.4230/LIPIcs.STACS.2025.42},
  annote =	{Keywords: Depth 3 circuits, k-CNF satisfiability, Circuit lower bounds, Majority function}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.71
Unfairly Splitting Separable Necklaces

Authors: Patrick Schnider, Linus Stalder, and Simon Weber

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the α-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for α-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of α-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for α-Ham Sandwich.
Cite as

Patrick Schnider, Linus Stalder, and Simon Weber. Unfairly Splitting Separable Necklaces. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schnider_et_al:LIPIcs.STACS.2025.71,
  author =	{Schnider, Patrick and Stalder, Linus and Weber, Simon},
  title =	{{Unfairly Splitting Separable Necklaces}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{71:1--71:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.71},
  URN =		{urn:nbn:de:0030-drops-228963},
  doi =		{10.4230/LIPIcs.STACS.2025.71},
  annote =	{Keywords: Necklace splitting, n-separability, well-separation, Ham Sandwich, alpha-Ham Sandwich, unfair splitting, fair division}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.6
Twin-Width One

Authors: Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We investigate the structure of graphs of twin-width at most 1, and obtain the following results: - Graphs of twin-width at most 1 are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a 1-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a 1-contraction sequence of a graph, or guarantees that it has twin-width more than 1. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs.
Cite as

Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht. Twin-Width One. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.STACS.2025.6,
  author =	{Ahn, Jungho and Jacob, Hugo and K\"{o}hler, Noleen and Paul, Christophe and Reinald, Amadeus and Wiederrecht, Sebastian},
  title =	{{Twin-Width One}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.6},
  URN =		{urn:nbn:de:0030-drops-228319},
  doi =		{10.4230/LIPIcs.STACS.2025.6},
  annote =	{Keywords: Twin-width, Hereditary graph classes, Intersection model}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.62
Faster Algorithms on Linear Delta-Matroids

Authors: Tomohiro Koana and Magnus Wahlström

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We present new algorithms and constructions for linear delta-matroids. Delta-matroids are generalizations of matroids that also capture structures such as matchable vertex sets in graphs and path-packing problems. As with matroids, an important class of delta-matroids is given by linear delta-matroids, which generalize linear matroids and are represented via a "twist" of a skew-symmetric matrix. We observe an alternative representation, termed a contraction representation over a skew-symmetric matrix. This representation is equivalent to the more standard twist representation up to O(n^ω)-time transformations (where n is the dimension of the delta-matroid and ω < 2.372 the matrix multiplication exponent), but it is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions for linear delta-matroids. In particular, we show that the union and delta-sum of linear delta-matroids are again linear delta-matroids, and that a representation for the resulting delta-matroid can be constructed in randomized time O(n^ω) (or more precisely, in O(n^ω) field operations, over a field of size at least Ω(n⋅(1/ε)), where ε > 0 is an error parameter). Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single O(n^ω)-time matrix rank computation. Using the methods of Harvey, previously applied by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the O(n⁴)-time augmenting path algorithm of Geelen, Iwata and Murota, albeit with randomization. Finally, we consider the maximum-cardinality delta-matroid intersection problem (equivalently, the maximum-cardinality delta-matroid matching problem). Using Storjohann’s algorithms for symbolic determinants, we show that such a solution can be found in O(n^{ω+1}) time. This provides the first (randomized) polynomial-time solution for the problem, thereby solving an open question of Kakimura and Takamatsu.
Cite as

Tomohiro Koana and Magnus Wahlström. Faster Algorithms on Linear Delta-Matroids. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2025.62,
  author =	{Koana, Tomohiro and Wahlstr\"{o}m, Magnus},
  title =	{{Faster Algorithms on Linear Delta-Matroids}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.62},
  URN =		{urn:nbn:de:0030-drops-228876},
  doi =		{10.4230/LIPIcs.STACS.2025.62},
  annote =	{Keywords: Delta-matroids, Randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.58
The Computational Complexity of Factored Graphs

Authors: Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, and Christopher Ye

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier? We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time.
Cite as

Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, and Christopher Ye. The Computational Complexity of Factored Graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2025.58,
  author =	{Gupta, Shreya and Huang, Boyang and Impagliazzo, Russell and Woo, Stanley and Ye, Christopher},
  title =	{{The Computational Complexity of Factored Graphs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{58:1--58:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.58},
  URN =		{urn:nbn:de:0030-drops-226865},
  doi =		{10.4230/LIPIcs.ITCS.2025.58},
  annote =	{Keywords: Parameterized Complexity, Fine-grained complexity, Fixed-parameter tractability, Graph algorithms}
}
  • Refine by Type
  • 75 Document/PDF
  • 14 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 14 2025
  • 60 2023
  • 1 2020
  • 1 2017

  • Refine by Author
  • 4 de Berg, Mark
  • 3 Iwata, Satoru
  • 2 Ahn, Jungho
  • 2 Buchin, Maike
  • 2 Conte, Alessio
  • Show More...

  • Refine by Series/Journal
  • 74 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 14 Theory of computation → Design and analysis of algorithms
  • 10 Theory of computation → Graph algorithms analysis
  • 8 Theory of computation → Computational geometry
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 3 Burrows-Wheeler Transform
  • 3 Graph algorithms
  • 3 Parameterized Complexity
  • 2 Approximation Algorithms
  • 2 Diversity
  • 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