91 Search Results for "Stephan, Frank"

Document
DOI: 10.4230/LIPIcs.SAT.2026.20
New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions

Authors: Sanjay Jain, Junqiang Peng, Frank Stephan, Haoyun Tang, and Mingyu Xiao

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract
Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical ⊕P-complete problem, it represents a fundamental variant of the exact model counting problem (#SAT). Under the Strong Exponential Time Hypothesis (SETH), Parity-SAT admits no O^*((2-ε)ⁿ)-time or O^*((2-ε)^m)-time algorithm for any constant ε > 0, where n and m denote the numbers of variables and clauses, respectively. Thus, breaking the 2ⁿ or 2^m barrier appears impossible in full generality. In this work, we revisit this barrier through structural restrictions and a refined exploitation of parity. We study Parity-d-occ-SAT, where each variable appears in at most d clauses, and obtain three main results. First, we design {a randomized} O^*(2^{m(1-1/O(d))})-time algorithm, thereby breaking the 2^m barrier for every fixed d. Second, for the special case d = 2, we develop a significantly sharper branching algorithm running in O^*(1.1193ⁿ) time or O^*(1.3248^m) time. Third, leveraging the structural insights underlying the d = 2 case, we obtain an O^*(1.1052^L)-time algorithm for general Parity-SAT, where L denotes the formula length. All algorithms use only polynomial space. Notably, our running-time bounds are better than the best known bounds for the corresponding exact counting counterparts, highlighting a genuine algorithmic advantage of parity over counting. Conceptually, our results demonstrate that parity admits finer structural reductions and more efficient branching than exact model counting, and that bounded occurrence can be systematically leveraged to circumvent classical exponential barriers.
Cite as

Sanjay Jain, Junqiang Peng, Frank Stephan, Haoyun Tang, and Mingyu Xiao. New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions. In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.SAT.2026.20,
  author =	{Jain, Sanjay and Peng, Junqiang and Stephan, Frank and Tang, Haoyun and Xiao, Mingyu},
  title =	{{New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.20},
  URN =		{urn:nbn:de:0030-drops-263263},
  doi =		{10.4230/LIPIcs.SAT.2026.20},
  annote =	{Keywords: Parity-SAT, Exact Exponential Algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSCD.2026.2
Saturation-Guided Inductive Synthesis (Invited Talk)

Authors: Laura Kovács

Published in: LIPIcs, Volume 378, 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)

Abstract
Proof by induction is common-place in mathematics [Josef Urban and Geoff Sutcliffe, 2010; Martin Desharnais et al., 2022], formal verification [Raven Beutner and Bernd Finkbeiner, 2024; Wolfgang Ahrendt et al., 2000; Pamina Georgiou et al., 2022], cybersecurity [Simon Jeanteur et al., 2024; Evan Laufer et al., 2024], and many more areas. This talk overviews recent progress in automating inductive reasoning in quantified logic, with applications to code synthesis. Key to our work is saturation-based first-order theorem proving [Laura Kovács and Andrei Voronkov, 2013], using variants of the superposition calculus [Robert Nieuwenhuis and Albert Rubio, 2001]. We show that induction and synthesis are better together in saturation, allowing us not only to prove quantified properties F, but also generate a functional implementation of F during proof search. We showcase our results using the first-order theorem prover Vampire [Filip Bártek et al., 2025], a completely automatic push-button theorem prover for first-order logic with theories, including arithmetic, inductively defined datatypes, induction, and higher-order logic. We structure our talk within three inter-connected parts. First, we overview the main ingredients behind saturation provers [Filip Bártek et al., 2025; Stephan Schulz et al., 2019; Christoph Weidenbach et al., 2009] using superposition. Such provers work by negating an input conjecture F, transforming ¬ F into a clausal normal form, and using superposition inferences to derive new clauses from existing ones until a contradiction is reached; when a contradiction is derived, validity of F is established. Many years of development in saturation-based theorem proving have gone into making this process as efficient as possible, while deriving new clauses only when needed in order to tame growth of the search space. Doing so, highly-efficient superposition calculi parametrized by so-called clause selection functions have been proposed, in order to make as few inferences between clauses as possible. Redundancy elimination techniques further prune the search space. Next, we show how to formalize applications of induction in the saturation process [Márton Hajdú et al., 2022], without bringing drastic changes into the overall framework of first-order proving. A natural choice for implementing induction would be by reducing goals to subgoals, in particular by proving a base case and an inductive step case of a valid induction principle. For example, a goal ∀ x. F(x) over natural numbers x can be proven using structural induction: we prove F[0] (base case) and ∀ x. F(x) ⇒ F(x+1) (step case). However, saturation theorem proving is not about reducing goals to subgoals: in principle, each clause in the search space can be chosen during any step of saturation. We therefore automate induction in saturation as follows. When a clause F(x) is chosen and inductive reasoning over F should be applied (for example, because F uses inductively defined data types x, such as natural numbers), we combine the application of a valid induction schema over F(x) with resolution. Put it simply, induction and resolution are combined in one step of saturation, allowing us to use parts of F(x) as subgoals of F(x). Interestingly with this approach is that clauses generated during saturation may be stronger than the induction schema and, most importantly, are friendly to saturation provers: they are mostly quantifier-free Horn clauses and their (at most one) positive equality cannot be used in many inferences during saturation. Thus, applying many induction inferences during proof search would hardly affect the performance of a saturation prover. Figure 1 lists a property over natural numbers: every natural number x is the half of another natural number y. Proving this property in saturation, and in particular using Vampire, can be achieved by (structural) induction over x. Finally, we extend saturation proof search with code synthesis [Petra Hozzová et al., 2024]. While proving formula F, we track the constructive parts of the proof of F using so-called answer literals [Cordell Green, 1969]. We use these parts to synthesize a program satisfying F and use the applications of induction in saturation to construct recursive programs satisfying F. In a nutshell, the base case and inductive case steps of induction in saturation express how to construct the desired program for the next recursive step using the program for the previous recursive step; we capture this information via answer literals. When we apply induction in saturation, we introduce a special term into the answer literal and record the program corresponding to the induction step. As we prove induction steps, we capture their corresponding programs in the answer literal. Finally, we convert the special tracker terms from the answer literals into recursive functions, and obtain a program satisfying property F. For example, from the proof of property of Figure 1, our approach implemented in Vampire infers the following functional implementation of a recursive function r, while using only the signature of Figure 1: 𝗋(0) & := 0 𝗋(s(x)) & := s(s(𝗋(x))) The above inferred function r satisfies the property of Figure 1 and, for each input natural number x, computes a natural number 𝗋(x) such that x is half of 𝗋(x). In summary, induction and synthesis are better together in saturation-based theorem proving using the superposition calculus. Soundness and practical use of our work has been addressed and experimented using the Vampire theorem prover, both in the case of automating induction [Márton Hajdú et al., 2022; Márton Hajdú et al., 2024] and program synthesis [Petra Hozzová et al., 2023; Petra Hozzová et al., 2024]. Interesting questions regarding completeness arise: if a program satisfying a given property exists, can we derive it from saturation-based proof search? Our recent results [Hajdu et al., 2026] answer this question for recursion-free program using additional assumptions of realizability. A natural direction for future work is to identify realizability assumptions for recursive program synthesis and induction.
Cite as

Laura Kovács. Saturation-Guided Inductive Synthesis (Invited Talk). In 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 378, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kovacs:LIPIcs.FSCD.2026.2,
  author =	{Kov\'{a}cs, Laura},
  title =	{{Saturation-Guided Inductive Synthesis}},
  booktitle =	{11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-433-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{378},
  editor =	{Pfenning, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2026.2},
  URN =		{urn:nbn:de:0030-drops-263521},
  doi =		{10.4230/LIPIcs.FSCD.2026.2},
  annote =	{Keywords: automated reasoning, first-order theorem proving, saturation, induction, program synthesis}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.11
Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms

Authors: Yuya Uezato

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

Abstract
Pattern languages (PAT) are a class of languages generated by expressions called patterns that may contain variables. In a pattern, each variable can be instantiated with an arbitrary string. Typed pattern languages extend PAT by associating a type (constraint) with each variable that restricts the domain of allowed substitutions. In this paper, we study regular-typed PAT (PATwRT), where all types are represented either by a regular expression or by an ε-NFA. We consider the PATwRT matching problem for patterns with a single repeated variable of the form P = α₁ β α₂ β ⋯ β α_K. We present simple algorithms whose running time is linear in K and quadratic in the input length N, with polynomial dependence on the sizes of the type representations. Our results extend previous quadratic-time work in two directions: (1) the quadratic-time algorithm for untyped PAT of Fernau et al. (STACS 2015), and (2) the quadratic-time algorithm for the restricted PATwRT K = 3, i.e., α₁ β α₂ β α₃ of Nogami and Terauchi (MFCS 2025).
Cite as

Yuya Uezato. Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uezato:LIPIcs.CPM.2026.11,
  author =	{Uezato, Yuya},
  title =	{{Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{11:1--11:20},
  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.11},
  URN =		{urn:nbn:de:0030-drops-259374},
  doi =		{10.4230/LIPIcs.CPM.2026.11},
  annote =	{Keywords: Pattern languages, Regular expressions, String algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.20
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Authors: Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n^{7/3+ o(1)}), where n denotes the number of disks [Jared Espenant et al., 2023; J. Mark Keil and Debajyoti Mondal, 2025]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O^*(n^{2t}) [J. Mark Keil and Debajyoti Mondal, 2025]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: [(i)] 1) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(n/ε²); and 2) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(f(t)⋅ (1/ε)^{O(t)} ⋅ n), for some (exponential) function f(t).
Cite as

Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi. Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.SWAT.2026.20,
  author =	{Gao, Jie and Gawrychowski, Pawe{\l} and Giannopoulos, Panos and Mulzer, Wolfgang and Singh, Satyam and Staals, Frank and Zehavi, Meirav},
  title =	{{Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.20},
  URN =		{urn:nbn:de:0030-drops-260563},
  doi =		{10.4230/LIPIcs.SWAT.2026.20},
  annote =	{Keywords: Maximum Clique, Disk Graphs, Unit Disk Graphs, FPT Approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.25
Parameterized Critical Node Cut Revisited

Authors: Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph G and integers k,x ≥ 0, Critical Node Cut (CNC) asks whether we can delete at most k vertices so that the number of remaining unordered pairs of connected vertices is at most x. CNC generalizes Vertex Cover (the case x = 0) and models tasks in network design, epidemiology, and social network analysis. We comprehensively map the structural parameterized complexity landscape for Critical Node Cut. First, we prove W[1]-hardness for the combined parameter k + fes + Δ + pw, where fes is the feedback edge set number, Δ the maximum degree, and pw the pathwidth of the input graph, respectively. This significantly improves over the known W[1]-hardness for k+tw, where tw denotes the treewidth, and is tight in that tree-depth together with maximum degree trivially yields FPT. Second, we give new positive results. Specifically, we identify three structural parameters-max-leaf number, vertex integrity, and modular-width-that render the problem fixed-parameter tractable, and develop a polynomial-time algorithm for graphs of constant clique-width. Third, leveraging a technique introduced by Lampis [ICALP '14], we develop an FPT approximation scheme that, for any ε > 0, computes a (1+ε)-approximate solution in time (tw / ε)^{𝒪(tw)} n^{𝒪(1)}. Finally, we show that CNC admits no polynomial kernel when parameterized by vertex cover number, unless standard assumptions fail. Together, these results substantially sharpen the known complexity landscape for CNC.
Cite as

Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Critical Node Cut Revisited. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.SWAT.2026.25,
  author =	{Knop, Du\v{s}an and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Parameterized Critical Node Cut Revisited}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.25},
  URN =		{urn:nbn:de:0030-drops-260617},
  doi =		{10.4230/LIPIcs.SWAT.2026.25},
  annote =	{Keywords: Critical Node Cut, Parameterized Complexity, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.45
Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications

Authors: Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The weak visibility polygon of a line segment s inside a simple polygon P, denoted by V_P(s), is the region of the polygon that is visible from at least one point on s. Given its fundamental nature in computational geometry, several algorithms have been proposed to compute weak visibility polygons efficiently, each with different trade-offs in terms of preprocessing time, query time, and space complexity. Although there are many applications that require computing these polygons such as computer graphics, robot motion planning, and network communication systems, there is a lack of any implementations of these algorithms in the literature - not to mention one that is exact, robust, and scalable. Furthermore, weak segment visibility polygons are used as basic building blocks in several other algorithms, such as in minimum-link path computation. In this work, we present an implementation of an optimal linear-time algorithm for computing the weak visibility polygon of a segment inside a triangulated simple polygon. Our implementation provides exact, robust geometric primitives and optimizations to handle large inputs with more than 18,000,000 vertices. We demonstrate two concrete applications: (1) construction of window partitions, a standard data structure in visibility algorithms, and (2) support for optimal minimum-link path queries between two points in a simple polygon, the latter serving as a direct use case of the former. Experimental results on a variety of polygon families confirm that the end-to-end running time scales linearly with the size of the polygon and is dominated by the cost of computing the triangulation, validating the practicality and scalability of the approach. The implementation is released as open source in the format of a CGAL package to support reproducibility and further research.
Cite as

Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk. Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.45,
  author =	{Fekete, S\'{a}ndor P. and Kasthurirangan, Prahlad Narasimhan and Keldenich, Phillip and Kollhoff, Fabian and Loi, Chek-Manh and Perk, Michael},
  title =	{{Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.45},
  URN =		{urn:nbn:de:0030-drops-258516},
  doi =		{10.4230/LIPIcs.SoCG.2026.45},
  annote =	{Keywords: Visibility, line segments, link distance, window partition, computation, implementation, robustness, scalability, exactness, CGAL}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.71
Approximating Euclidean Shallow-Light Trees

Authors: Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
For a weighted graph G = (V, E, w) and a designated source vertex s ∈ V, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source s and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an (α, β)-SLT of G w.r.t. s ∈ V is a spanning tree of G with root-stretch α (preserving all distances between s and all other vertices up to a factor of α) and lightness β (its weight is at most β times the weight of a minimum spanning tree of G). It was shown in the early 1990s that (1) for any graph, any source, and any ε > 0, there is a (1 + ε, O(1/ε))-SLT, and (2) there exist graphs for which β = Ω(1/ε) for any (1+ε,β)-SLT. The focus of this work is on SLTs in low-dimensional Euclidean spaces, which are of special interest for some applications of SLTs, in geometric network optimization problems. The aforementioned existential lower bound applies to Euclidean plane, as well. It was shown more than a decade ago that (1) by using Steiner points, one can reduce the lightness bound from O(1/ε) to O(√{1/ε}), and (2) there exist point sets in the plane for which β = Ω(√{1/ε}) for any Steiner (1+ε,β)-SLT. These tight existential bounds for the Euclidean case yield approximation factors of O(1/ε) and O(√{1/ε}) on the minimum weight of any non-Steiner and Steiner tree with root-stretch 1+ε, respectively. Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards resolving this question by presenting two bicriteria approximation algorithms. For any ε > 0, a set P of n points in constant-dimensional Euclidean space and a source s ∈ P, our first (respectively, second) algorithm returns, in O(n log n ⋅ polylog(ε^{-1})) time, a non-Steiner (resp., Steiner) tree with root-stretch 1+O(ε log ε^{-1}) and weight at most O(opt_ε ⋅ log² ε^{-1}) (resp., O(opt_ε ⋅ log ε^{-1})), where opt_ε denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch 1+ε.
Cite as

Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang. Approximating Euclidean Shallow-Light Trees. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2026.71,
  author =	{Le, Hung and Solomon, Shay and Than, Cuong and T\'{o}th, Csaba D. and Zhang, Tianyi},
  title =	{{Approximating Euclidean Shallow-Light Trees}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.71},
  URN =		{urn:nbn:de:0030-drops-258789},
  doi =		{10.4230/LIPIcs.SoCG.2026.71},
  annote =	{Keywords: geometric network design, optimization, shallow-light tree, Steiner point}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.93
Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations

Authors: Raphaël Tinarrage

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Cite as

Raphaël Tinarrage. Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tinarrage:LIPIcs.SoCG.2026.93,
  author =	{Tinarrage, Rapha\"{e}l},
  title =	{{Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{93:1--93:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.93},
  URN =		{urn:nbn:de:0030-drops-258991},
  doi =		{10.4230/LIPIcs.SoCG.2026.93},
  annote =	{Keywords: Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.13
The Berlin Safe House Puzzle: Spycraft via Interval Graphs

Authors: Gennaro Cordasco, Luisa Gargano, and Adele Anna Rescigno

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We propose a gamified application of the {Identifying Code} problem on {Interval Graphs}, framed as a high-stakes Cold War counter-intelligence operation. We present a polynomial-time algorithm to assign "Listening Devices" (bugs) to "Safe Houses" (intervals) so that every safe house is uniquely identifiable by its bug signature. While the problem is NP-hard on several graph classes, including chordal and bipartite graphs, the interval-graph structure allows us to compute a 2-approximate solution efficiently.
Cite as

Gennaro Cordasco, Luisa Gargano, and Adele Anna Rescigno. The Berlin Safe House Puzzle: Spycraft via Interval Graphs. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cordasco_et_al:LIPIcs.FUN.2026.13,
  author =	{Cordasco, Gennaro and Gargano, Luisa and Rescigno, Adele Anna},
  title =	{{The Berlin Safe House Puzzle: Spycraft via Interval Graphs}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.13},
  URN =		{urn:nbn:de:0030-drops-257325},
  doi =		{10.4230/LIPIcs.FUN.2026.13},
  annote =	{Keywords: Interval Graphs, Watching-System, Approximate Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.75
Effective Versions of Strong Measure Zero

Authors: Matthew Rayman

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

Abstract
Effective versions of strong measure zero sets are developed for various levels of complexity and computability. It is shown that the sets can be equivalently defined using a generalization of supermartingales called odds supermartingales, success rates on supermartingales, predictors, and coverings. We show Borel’s conjecture that a set has strong measure zero if and only if it is countable holds in the time and space bounded setting. At the level of computability this does not hold. We show the computable level contains sequences at arbitrary levels of the hyperarithmetical hierarchy. This is done by proving a correspondence principle yielding a condition for the sets of computable strong measure zero to agree with the classical sets of strong measure zero. An algorithmic version of strong measure zero using lower semicomputability is defined. We show that this notion is equivalent to the set of NCR reals studied by Reimann and Slaman, thereby giving new characterizations of this set. Effective strong packing dimension zero is investigated by requiring success with respect to the limit inferior instead of the limit superior. It is proven that every sequence in the corresponding algorithmic class is decidable. At the level of computability, the sets coincide with a notion of weak countability that we define.
Cite as

Matthew Rayman. Effective Versions of Strong Measure Zero. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rayman:LIPIcs.STACS.2026.75,
  author =	{Rayman, Matthew},
  title =	{{Effective Versions of Strong Measure Zero}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{75:1--75:18},
  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.75},
  URN =		{urn:nbn:de:0030-drops-255648},
  doi =		{10.4230/LIPIcs.STACS.2026.75},
  annote =	{Keywords: Strong measure zero, NCR, Effective fractal dimensions, Borel’s Conjecture, Hausdorff dimension, Packing dimension}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.41
Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide

Authors: Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté, and Florent Madelaine

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
In this work we take a step towards characterising strongly flip-flat classes of graphs. Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. We prove that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide.
Cite as

Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté, and Florent Madelaine. Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghasemi_et_al:LIPIcs.CSL.2026.41,
  author =	{Ghasemi, Fatemeh and Grange, Julien and Kant\'{e}, Mamadou Moustapha and Madelaine, Florent},
  title =	{{Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.41},
  URN =		{urn:nbn:de:0030-drops-254668},
  doi =		{10.4230/LIPIcs.CSL.2026.41},
  annote =	{Keywords: Almost-wide, Flip-flatness}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.23
A Logic for Fresh Labelled Transition Systems

Authors: Mohamed H. Bandukara and Nikos Tzevelekos

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
We introduce a Hennessy-Milner logic with recursion for Fresh Labelled Transition Systems (FLTSs). These are nominal labelled transition systems which keep track of the history, i.e. of data values seen so far, and can model fresh data generation. In particular, FLTSs generalise the computations of Fresh-Register Automata, which in turn can be seen as a "regular" class of history-tracking automata operating on infinite input alphabets. The logic we introduce is a modal mu-calculus equipped with infinite disjunctions over arbitrary and fresh data values respectively, while its recursion is parameterised on vectors of data values. It can express a variety of properties, such as the existence of an infinite path of distinct data values, the absence of paths where values are repeated, or the existence of a finite path where some taint property is violated. We study the model-checking problem and its complexity via a reduction to parity games and, using nominal sets techniques, provide an exponential upper bound for it.
Cite as

Mohamed H. Bandukara and Nikos Tzevelekos. A Logic for Fresh Labelled Transition Systems. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bandukara_et_al:LIPIcs.CSL.2026.23,
  author =	{Bandukara, Mohamed H. and Tzevelekos, Nikos},
  title =	{{A Logic for Fresh Labelled Transition Systems}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.23},
  URN =		{urn:nbn:de:0030-drops-254478},
  doi =		{10.4230/LIPIcs.CSL.2026.23},
  annote =	{Keywords: Nominal Transition Systems, Hennessy-Milner Logic, Modal Mu-Calculus, Register Automata, Nominal Sets, Parity Games}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.29
Hitting Geodesic Intervals in Structurally Restricted Graphs

Authors: Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada, Yota Otachi, and Hayato Takaike

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Given a graph G = (V,E), a set T of vertex pairs, and an integer k, Hitting Geodesic Intervals asks whether there is a set S ⊆ V of size at most k such that for each terminal pair {u,v} ∈ T, the set S intersects at least one shortest u-v path. Aravind and Saxena [WALCOM 2024] introduced this problem and showed several parameterized complexity results. In this paper, we extend the known results in both negative and positive directions and present sharp complexity contrasts with respect to structural graph parameters. We first show that the problem is NP-complete even on graphs with highly restricted shortest-path structures. More precisely, we show the NP-completeness on graphs obtained by adding a single vertex to a disjoint union of 5-vertex paths. By modifying the proof of this result, we also show the NP-completeness on graphs obtained from a path by adding one vertex and on graphs obtained from a disjoint union of triangles by adding one universal vertex. Furthermore, we show the NP-completeness on graphs of bandwidth 4 and maximum degree 5 by replacing the universal vertex in the last case with a long path. Under standard complexity assumptions, these negative results rule out fixed-parameter algorithms for most of the structural parameters studied in the literature (if the solution size k is not part of the parameter). We next present fixed-parameter algorithms parameterized by k plus modular-width and by k plus vertex integrity. The algorithm for the latter case does indeed solve a more general setting that includes the parameterization by the minimum vertex multiway-cut size of the terminal vertices. We show that this is tight in the sense that the problem parameterized by the minimum vertex multicut size of the terminal pairs is W[2]-complete. We then modify the proof of this intractability result and show that the problem is W[2]-complete parameterized by k even in the setting where T = binom(Q,2) for some Q ⊆ V.
Cite as

Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada, Yota Otachi, and Hayato Takaike. Hitting Geodesic Intervals in Structurally Restricted Graphs. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.IPEC.2025.29,
  author =	{Gima, Tatsuya and Kobayashi, Yasuaki and Okada, Yuto and Otachi, Yota and Takaike, Hayato},
  title =	{{Hitting Geodesic Intervals in Structurally Restricted Graphs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.29},
  URN =		{urn:nbn:de:0030-drops-251618},
  doi =		{10.4230/LIPIcs.IPEC.2025.29},
  annote =	{Keywords: Terminal monitoring set, Structural graph parameter, Geodesic interval}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.4
On the Complexity of Secluded Path Problems

Authors: Tesshu Hanaka and Daisuke Tsuru

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
This paper investigates the complexity of finding secluded paths in graphs. We focus on the Short Secluded Path problem and a natural new variant we introduce, Shortest Secluded Path. Formally, given an undirected graph G = (V, E), two vertices s,t ∈ V, and two integers k,l, the Short Secluded Path problem asks whether there exists an s-t path of length at most k with at most l neighbors. This problem is known to be computationally hard: it is W[1]-hard when parameterized by the path length k or by cliquewidth, and para-NP-complete when parameterized by the number l of neighbors. The fixed-parameter tractability is known for k+l or treewidth. In this paper, we expand the parameterized complexity landscape by designing (1) an XP algorithm parameterized by cliquewidth and (2) fixed-parameter algorithms parameterized by neighborhood diversity and twin cover number, respectively. As a byproduct, our results also provide parameterized algorithms for the classic s-t k-Path problem. Furthermore, we introduce the Shortest Secluded Path problem, which seeks a shortest s-t path with the minimum number of neighbors. In contrast to the hardness of the original problem, we reveal that this variant is solvable in polynomial time on unweighted graphs. We complete this by showing that for edge-weighted graphs, the problem becomes W[1]-hard yet remains in XP when parameterized by the shortest path distance between s and t.
Cite as

Tesshu Hanaka and Daisuke Tsuru. On the Complexity of Secluded Path Problems. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.IPEC.2025.4,
  author =	{Hanaka, Tesshu and Tsuru, Daisuke},
  title =	{{On the Complexity of Secluded Path Problems}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.4},
  URN =		{urn:nbn:de:0030-drops-251361},
  doi =		{10.4230/LIPIcs.IPEC.2025.4},
  annote =	{Keywords: Secluded path, Parameterized complexity, Polynomial-time algorithm}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.IPEC.2025.1
A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk)

Authors: Martin Koutecký

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Integer Programming (IP) is a fundamental but computationally hard problem. Still, certain efficiently solvable subclasses have been identified over time, most notably totally unimodular IPs in the 1950s, and fixed-dimension IPs in the 1980s. Starting around the year 2000, a stream of research has identified block-structured IPs as yet another tractable subclass. In this paper, we give a brief and incomplete review of this history, with a focus on several of the author’s contributions.
Cite as

Martin Koutecký. A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk). In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koutecky:LIPIcs.IPEC.2025.1,
  author =	{Kouteck\'{y}, Martin},
  title =	{{A Brief History of Parameterized Algorithms for Block-Structured Integer Programs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.1},
  URN =		{urn:nbn:de:0030-drops-251338},
  doi =		{10.4230/LIPIcs.IPEC.2025.1},
  annote =	{Keywords: Integer Programming, Parameterized Algorithm, Graver Basis, Treedepth, n-fold, tree-fold, 2-stage stochastic, multistage stochastic, Mixed-Integer Programming}
}
  • Refine by Type
  • 91 Document/PDF
  • 64 Document/HTML

  • Refine by Publication Year
  • 12 2026
  • 45 2025
  • 10 2024
  • 5 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 12 Stephan, Frank
  • 6 Jain, Sanjay
  • 3 Calbimonte, Jean-Paul
  • 3 Hoi, Gordon
  • 2 Bonifati, Angela
  • Show More...

  • Refine by Series/Journal
  • 66 LIPIcs
  • 5 OASIcs
  • 8 LITES
  • 11 TGDK
  • 1 DagSemProc

  • Refine by Classification
  • 9 Theory of computation → Parameterized complexity and exact algorithms
  • 8 Theory of computation → Design and analysis of algorithms
  • 5 Theory of computation
  • 4 Information systems → Semantic web description languages
  • 4 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 2 Enumeration
  • 2 Exponential Time Algorithms
  • 2 Knowledge Graphs
  • 2 Large Language Models
  • 2 OWL
  • 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