Search Results

Documents authored by Bals, Ben

Document
DOI: 10.4230/LIPIcs.ESA.2026.59
Revisiting Diameter in Directed Graphs

Authors: Ben Bals, Joakim Blikstad, Daniel Dadush, Yasamin Nazari, and Jonas Schmidt

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
The reachability diameter (ReachDiam) of a directed graph is the maximum distance over all pairs u,v where v is reachable from u. This notion is present in the definition of shortcut sets, and the name was recently coined in that context by Haeupler, Jiang, and Saranurak [SOSA 2026]. While this is a very natural notion of diameter in directed graphs, and especially DAGs, it is so far not computationally explored. Other definitions of diameter in directed graphs are either trivial (infinite) in graphs that are not strongly connected (e.g., the classical definition) or are non-trivial only in highly restrictive graph classes (e.g., Min-Diameter). We initiate the problem of computing the (approximate) reachability diameter from a fine-grained complexity point of view. Under certain fine-grained assumptions, we prove that there is no algorithm in time 𝒪(n^{ω - ε}) that gives any approximation of ReachDiam in weighted graphs. Similarly, there is no algorithm with better than 2-approximation for unweighted graphs in this time. To supplement this, we provide algorithmic upper bounds that lead to additive approximation of ReachDiam for unweighted graphs. Hence, we establish a strong separation between the weighted and unweighted cases, which makes this type of diameter different in nature than other known notions. Considering the hardness in general weighted graphs, we also study special graph classes and get small constant approximations for DAGs with bounded width or graphs with bounded treewidth. Interestingly, our techniques also lead to exact hopsets with hopbound 2 for bounded treewidth graphs. This and some of our upper bounds for general graphs show technical connections between approximating ReachDiam and computing shortcut sets and hopsets.
Cite as

Ben Bals, Joakim Blikstad, Daniel Dadush, Yasamin Nazari, and Jonas Schmidt. Revisiting Diameter in Directed Graphs. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 59:1-59:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bals_et_al:LIPIcs.ESA.2026.59,
  author =	{Bals, Ben and Blikstad, Joakim and Dadush, Daniel and Nazari, Yasamin and Schmidt, Jonas},
  title =	{{Revisiting Diameter in Directed Graphs}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{59:1--59:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.59},
  URN =		{urn:nbn:de:0030-drops-271959},
  doi =		{10.4230/LIPIcs.ESA.2026.59},
  annote =	{Keywords: Graph algorithms, Diameter, Fine-grained complexity, Shortcut sets}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.60
Optimal Enumeration of Eulerian Trails in Directed Graphs

Authors: Ben Bals, Solon P. Pissis, and Matei Tinca

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
The BEST theorem, due to de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, is a classical tool from graph theory that links the Eulerian trails in a directed graph G = (V,E) with the arborescences in G. In particular, one can use the BEST theorem to count the Eulerian trails in G in polynomial time. For enumerating the Eulerian trails in G, one could naturally resort to first enumerating the arborescences in G and then exploiting the insight of the BEST theorem to enumerate the Eulerian trails in G: every arborescence in G corresponds to at least one Eulerian trail in G. For over two decades, the fastest algorithm for enumerating arborescences in G took 𝒪(m log n + n + z_A log²n) time, where n = |V|, m = |E|, and z_A is the number of arborescences in G [Uno, ISAAC 1998]. Since Uno’s algorithm does not lead to an optimal enumeration of Eulerian trails in directed graphs, we were motivated to develop a direct algorithm for this problem. Our central contribution is a remarkably simple algorithm to directly enumerate the z_T Eulerian trails in G in the optimal 𝒪(m + z_T) time. As a consequence, our result improves on an implementation of the BEST theorem for counting Eulerian trails in G when z_T = o(n²), and also unconditionally improves the combinatorial 𝒪(m⋅z_T)-time algorithm of Conte et al. [TKDD 2026] for the same task. Moreover, we show that, with some care, our algorithm can be extended to enumerate Eulerian trails in directed multigraphs in optimal time, enabling applications in bioinformatics and data privacy.
Cite as

Ben Bals, Solon P. Pissis, and Matei Tinca. Optimal Enumeration of Eulerian Trails in Directed Graphs. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bals_et_al:LIPIcs.ESA.2026.60,
  author =	{Bals, Ben and Pissis, Solon P. and Tinca, Matei},
  title =	{{Optimal Enumeration of Eulerian Trails in Directed Graphs}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{60:1--60:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.60},
  URN =		{urn:nbn:de:0030-drops-271960},
  doi =		{10.4230/LIPIcs.ESA.2026.60},
  annote =	{Keywords: graph algorithms, enumeration algorithms, Eulerian trails, Eulerian paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.68
Text Indexing: From Reporting to Counting

Authors: Ben Bals, Panagiotis Charalampopoulos, Oded Lachish, Solon P. Pissis, and Hilde Verbeek

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We prove an elementary yet powerful combinatorial lemma: in any rooted tree with L leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is at most L. For any string T of length n, a direct application of this lemma to the suffix trie of T yields that the number of substrings of T whose length is smaller than their number of occurrences in T is at most n. This combinatorial insight leads to space-efficient data structures with optimal query times for string counting problems via the following algorithmic framework: store the counts for the at most n "frequent" substrings of T in a preprocessing step, and use a reporting query to count for the "infrequent" substrings. Our framework acts as a convenient black box, lifting indexes with reporting time 𝒪(|P|+|Occ_T(P)|) to support counting queries in time 𝒪(|P|), where P is the queried pattern and Occ_T(P) is the set of occurrences of P in T. As applications, we show efficient indexes for consecutive occurrences, weighted sequences, strings with utilities, and non-overlapping occurrences.
Cite as

Ben Bals, Panagiotis Charalampopoulos, Oded Lachish, Solon P. Pissis, and Hilde Verbeek. Text Indexing: From Reporting to Counting. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bals_et_al:LIPIcs.ESA.2026.68,
  author =	{Bals, Ben and Charalampopoulos, Panagiotis and Lachish, Oded and Pissis, Solon P. and Verbeek, Hilde},
  title =	{{Text Indexing: From Reporting to Counting}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.68},
  URN =		{urn:nbn:de:0030-drops-272046},
  doi =		{10.4230/LIPIcs.ESA.2026.68},
  annote =	{Keywords: text indexing, data structures, string algorithms, string processing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.105
String Matching in (Block) Graphs: A Full Classification by Walk Length

Authors: Sebastian Angrick, Ben Bals, Paweł Gawrychowski, Solon P. Pissis, and Yuki Yonemoto

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph G = (V,E) and a pattern of length m, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. [J. Algorithms, 2000] showed that SMLG can be solved in 𝒪(m |E| + N) time, where N is the total length of all node labels. Equi et al. [ACM Trans. Algorithms, 2023] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length Θ(|V|). Thus, we might be able to bypass this lower bound by restricting the walk length to b-1, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into b blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the b-SMBG problem. Equi et al. [Algorithmica, 2023] showed that, if we impose no restriction on b, the existing algorithm of Amir et al. is essentially optimal for b-SMBG (again under SETH). We provide a more fine-grained classification that essentially settles the complexity of b-SMBG parameterized by b: 1) For b = 2, Pissis [SOSA 2025] already provided a simple 𝒪(m + |E|+N)-time algorithm. 2) We design a new 𝒪̃(m + |E| + N)-time algorithm for b = 3. As a direct implication of this result, the SMLG problem for b ≤ 3 (walks of length at most 2) also admits near-linear-time complexity. 3) There is no 𝒪((m |E|)^{1-ε} + N)-time combinatorial algorithm, for any b ≥ 4 and ε > 0. 4) There is an algorithm working in 𝒪(max(|V|, m)^ω+N) time, where ω is the matrix multiplication exponent, which is conditionally optimal for graphs with b ≥ 4 blocks. 5) Under SETH, no 𝒪((m |E|)^{1-ε} + N)-time algorithm exists, for any b = ω(log |V|) and ε > 0. Although our motivation is primarily of a theoretical nature, we stress that our algorithms are simple to implement. As such, they may contribute to practical advancements in applications where the SMLG problem is an important primitive, such as in the analysis of pangenome graphs.
Cite as

Sebastian Angrick, Ben Bals, Paweł Gawrychowski, Solon P. Pissis, and Yuki Yonemoto. String Matching in (Block) Graphs: A Full Classification by Walk Length. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 105:1-105:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.ESA.2026.105,
  author =	{Angrick, Sebastian and Bals, Ben and Gawrychowski, Pawe{\l} and Pissis, Solon P. and Yonemoto, Yuki},
  title =	{{String Matching in (Block) Graphs: A Full Classification by Walk Length}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{105:1--105:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.105},
  URN =		{urn:nbn:de:0030-drops-272417},
  doi =		{10.4230/LIPIcs.ESA.2026.105},
  annote =	{Keywords: string algorithms, pattern matching, lower bounds, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.53
When Is String Reconstruction Using de Bruijn Graphs Hard?

Authors: Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, and Hilde Verbeek

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

Abstract
The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly. This reduction employs the notion of de Bruijn graph G = (V,E) of order k over an alphabet Σ. A single Eulerian trail in G represents a candidate genome reconstruction. Bernardini et al. have also introduced the complementary idea in data privacy [ALENEX 2020] based on z-anonymity. Let S be a private string that we would like to release, preventing, however, its full reconstruction. For a privacy threshold z > 0, we compute the largest k for which there exist at least z Eulerian trails in the order-k de Bruijn graph of S, and release a string S' obtained via a random Eulerian trail. The pressing question is: How hard is it to reconstruct a best string from a de Bruijn graph given a function that models domain knowledge? Such a function maps every length-k string to an interval of positions where it may occur in the reconstructed string. By the above reduction to de Bruijn graphs, the latter function translates into a function c mapping every edge to an interval where it may occur in an Eulerian trail. This gives rise to the following basic problem on graphs: Given an instance (G,c), can we efficiently compute an Eulerian trail respecting c? Hannenhalli et al. [CABIOS 1996] formalized this problem and showed that it is NP-complete. Ben-Dor et al. [J. Comput. Biol. 2002] showed that it is NP-complete, even on de Bruin graphs with |Σ| = 4. In this work, we settle the lower-bound side of this problem by showing that finding a c-respecting Eulerian trail in de Bruijn graphs over alphabets of size 2 is NP-complete. We then shift our focus to parametrization aiming to capture the quality of our domain knowledge in the complexity. Ben-Dor et al. developed an algorithm to solve the problem on de Bruijn graphs in 𝒪(m⋅w^{1.5} 4^w) time, where m = |E| and w is the maximum interval length over all edges in E. Bumpus and Meeks [Algorithmica 2023] later rediscovered the same algorithm on temporal graphs, which highlights the relevance of this problem in other contexts. Our central contribution is showing how combinatorial insights lead to exponential-time improvements over the state-of-the-art algorithm. In particular, for the important class of de Bruijn graphs, we develop an algorithm parametrized by w (log w+1) /(k-1): for a de Bruijn graph of order k, it runs in 𝒪(mw⋅2^{w(log(w)+1)/(k-1)}) time. Our result improves on the state of the art by roughly an exponent of (log(w)+1)/(k-1). The existing algorithms have a natural interpretation for string reconstruction: when for each length-k string, we know a small range of positions it must lie in, string reconstruction can be solved in linear time. Our improved algorithm shows that it is enough when the range of positions is small relative to k. We then generalize both the existing and our novel FPT algorithm by allowing the cost at every position of an interval to vary. In this optimization version, our hardness result translates into inapproximability and the FPT algorithms work with a slight extension. Surprisingly, even in this more general setting, we extend the FPT algorithms to count and enumerate the min-cost Eulerian trails. The counting result has direct applications in the data privacy framework of Bernardini et al.
Cite as

Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, and Hilde Verbeek. When Is String Reconstruction Using de Bruijn Graphs Hard?. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bals_et_al:LIPIcs.ESA.2025.53,
  author =	{Bals, Ben and van Krieken, Sebastiaan and Pissis, Solon P. and Stougie, Leen and Verbeek, Hilde},
  title =	{{When Is String Reconstruction Using de Bruijn Graphs Hard?}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.53},
  URN =		{urn:nbn:de:0030-drops-245215},
  doi =		{10.4230/LIPIcs.ESA.2025.53},
  annote =	{Keywords: string algorithm, graph algorithm, de Bruijn graph, Eulerian trail}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.11
How to Reduce Temporal Cliques to Find Sparse Spanners

Authors: Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells

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

Abstract
Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge-set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with 𝒪(nlog n) many edges. We present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques. We adapt techniques used in previous works and heavily expand and generalize them. This allows us to show that the existence of a linear spanner in cliques and bi-cliques is equivalent and using this, we provide a simpler and more intuitive proof of the 𝒪(nlog n) bound by giving an efficient algorithm for finding linearithmic spanners. Moreover, we use our novel and efficiently computable approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes and we develop novel algorithmic techniques for establishing the existence of linear temporal spanners in these graph classes as well.
Cite as

Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells. How to Reduce Temporal Cliques to Find Sparse Spanners. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.ESA.2024.11,
  author =	{Angrick, Sebastian and Bals, Ben and Friedrich, Tobias and Gawendowicz, Hans and Hastrich, Niko and Klodt, Nicolas and Lenzner, Pascal and Schmidt, Jonas and Skretas, George and Wells, Armin},
  title =	{{How to Reduce Temporal Cliques to Find Sparse Spanners}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.11},
  URN =		{urn:nbn:de:0030-drops-210822},
  doi =		{10.4230/LIPIcs.ESA.2024.11},
  annote =	{Keywords: Temporal Graphs, temporal Clique, temporal Spanner, Reachability, Graph Connectivity, Graph Sparsification}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.10
Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover

Authors: Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
In the Directed Feedback Vertex Set (DFVS) problem, one is given a directed graph G = (V,E) and wants to find a minimum cardinality set S ⊆ V such that G-S is acyclic. DFVS is a fundamental problem in computer science and finds applications in areas such as deadlock detection. The problem was the subject of the 2022 PACE coding challenge. We develop a novel exact algorithm for the problem that is tailored to perform well on instances that are mostly bi-directed. For such instances, we adapt techniques from the well-researched vertex cover problem. Our core idea is an iterative reduction to vertex cover. To this end, we also develop a new reduction rule that reduces the number of not bi-directed edges. With the resulting algorithm, we were able to win third place in the exact track of the PACE challenge. We perform computational experiments and compare the running time to other exact algorithms, in particular to the winning algorithm in PACE. Our experiments show that we outpace the other algorithms on instances that have a low density of uni-directed edges.
Cite as

Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10,
  author =	{Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
  title =	{{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10},
  URN =		{urn:nbn:de:0030-drops-183602},
  doi =		{10.4230/LIPIcs.SEA.2023.10},
  annote =	{Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2022.28
PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set

Authors: Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
In this document we describe the techniques we used and implemented for our submission to the Parameterized Algorithms and Computational Experiments Challenge (PACE) 2022. The given problem is Directed Feedback Vertex Set (DFVS), where one is given a directed graph G = (V,E) and wants to find a minimum S ⊆ V such that G-S is acyclic. We approach this problem by first exhaustively applying a set of reduction rules. In order to find a minimum DFVS on the remaining instance, we create and solve a series of Vertex Cover instances.
Cite as

Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.IPEC.2022.28,
  author =	{Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
  title =	{{PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{28:1--28:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.28},
  URN =		{urn:nbn:de:0030-drops-173847},
  doi =		{10.4230/LIPIcs.IPEC.2022.28},
  annote =	{Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
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