10 Search Results for "Lanzinger, Matthias"

Document
Database Theory in Action
DOI: 10.4230/LIPIcs.ICDT.2026.24
Database Theory in Action: Evaluation of Aggregate Queries Without Materialisation

Authors: Matthias Lanzinger, Reinhard Pichler, and Alexander Selzer

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
Aggregate queries often require computing large intermediate joins despite producing only small outputs. We identify broad classes of acyclic aggregate queries that can be evaluated without materialising any join results, using a bottom-up, semi-join–based propagation of cardinalities and partial aggregates. An implementation in Spark SQL shows that this approach is widely applicable and yields substantial performance gains on standard benchmarks.
Cite as

Matthias Lanzinger, Reinhard Pichler, and Alexander Selzer. Database Theory in Action: Evaluation of Aggregate Queries Without Materialisation. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 24:1-24:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lanzinger_et_al:LIPIcs.ICDT.2026.24,
  author =	{Lanzinger, Matthias and Pichler, Reinhard and Selzer, Alexander},
  title =	{{Database Theory in Action: Evaluation of Aggregate Queries Without Materialisation}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{24:1--24:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.24},
  URN =		{urn:nbn:de:0030-drops-256380},
  doi =		{10.4230/LIPIcs.ICDT.2026.24},
  annote =	{Keywords: Join Processing, Aggregate Queries, Acyclic Conjunctive Queries}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.46
Symmetric Algebraic Circuits and Homomorphism Polynomials

Authors: Anuj Dawar, Benedikt Pago, and Tim Seppelt

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The central open question of algebraic complexity is whether VP ≠ VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020), who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting.
Cite as

Anuj Dawar, Benedikt Pago, and Tim Seppelt. Symmetric Algebraic Circuits and Homomorphism Polynomials. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.ITCS.2026.46,
  author =	{Dawar, Anuj and Pago, Benedikt and Seppelt, Tim},
  title =	{{Symmetric Algebraic Circuits and Homomorphism Polynomials}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.46},
  URN =		{urn:nbn:de:0030-drops-253330},
  doi =		{10.4230/LIPIcs.ITCS.2026.46},
  annote =	{Keywords: algebraic complexity, finite model theory, symmetric circuits, homomorphism counting, graph homomorphism, treewidth, counting width, first-order logic with counting quantifiers}
}
Document
Invited Paper
DOI: 10.4230/OASIcs.RW.2024/2025.2
Fine-Grained Complexity of Ontology Mediated Queries (Invited Paper)

Authors: Cristina Feier

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract
This article surveys some approaches for establishing fine-grained complexity results for evaluation of ontology mediated queries (OMQs). It accompanies a related talk given at the Reasoning Web Summer School 2024. It zooms into some characterizations of efficiency in a parameterized complexity framework for OMQs based on various description logics and guarded tgds. As such results were established using results from query evaluation on databases, it also discusses the relevant results from the database world. After surveying some successive results on OMQs which all leverage database results in custom ways, it describes an approach which provides a general fpt reduction from query evaluation in the database world to query evaluation in the OMQ world. The reduction enables porting hardness results from the DB world to the OMQ world in a black-box fashion. Along these mentioned approaches, it also provides a brief survey of other approaches which are concerned with fine-grained complexity of OMQs and are based on rewriting techniques.
Cite as

Cristina Feier. Fine-Grained Complexity of Ontology Mediated Queries (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feier:OASIcs.RW.2024/2025.2,
  author =	{Feier, Cristina},
  title =	{{Fine-Grained Complexity of Ontology Mediated Queries}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{2:1--2:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.2},
  URN =		{urn:nbn:de:0030-drops-250476},
  doi =		{10.4230/OASIcs.RW.2024/2025.2},
  annote =	{Keywords: complexity analysis, guarded logics, guarded tgds, database theory, ontology mediated queries}
}
Document
Invited Paper
DOI: 10.4230/OASIcs.RW.2024/2025.9
Reasoning About Time in DatalogMTL: Course Notes (Invited Paper)

Authors: Przemysław Andrzej Wałęga

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract
Many real-world applications, such as those in healthcare, finance, and logistics, require reasoning over temporal data. Standard rule-based languages like Datalog, however, lack explicit mechanisms for handling time and temporal dependencies. In this chapter, we discussDatalogMTL, an extension of Datalog with operators frommetric temporal logic that allow to express complex temporal properties. We focus on reasoning algorithms for DatalogMTL, discussing bothmaterialisation, based on fixpoint applications of the immediate consequence operator, and anovel saturation-based extensionthat detects and halts infinite derivations, ensuring both completeness and termination of reasoning.
Cite as

Przemysław Andrzej Wałęga. Reasoning About Time in DatalogMTL: Course Notes (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{walega:OASIcs.RW.2024/2025.9,
  author =	{Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  title =	{{Reasoning About Time in DatalogMTL: Course Notes}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{9:1--9:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.9},
  URN =		{urn:nbn:de:0030-drops-250546},
  doi =		{10.4230/OASIcs.RW.2024/2025.9},
  annote =	{Keywords: DatalogMTL, Logic Programming, Temporal Reasoning}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.96
Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

Authors: Radu Curticapean, Simon Döring, and Daniel Neuen

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

Abstract
In the parameterized problem #IndSub(Φ) for fixed graph properties Φ, given as input a graph G and an integer k, the task is to compute the number of induced k-vertex subgraphs satisfying Φ. Dörfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that #IndSub(Φ) is #W[1]-hard for all non-meager properties Φ, i.e., properties that are nontrivial for infinitely many k. This conjecture has been confirmed for several restricted types of properties, including all hereditary properties [STOC 2022] and all edge-monotone properties [STOC 2024]. We refute this conjecture by showing that induced k-vertex graphs that are scorpions can be counted in time O(n⁴) for all k. Scorpions were introduced more than 50 years ago in the context of the evasiveness conjecture. A simple variant of this construction results in graph properties that achieve arbitrary intermediate complexity assuming ETH. Moreover, we formulate an updated conjecture on the complexity of #IndSub(Φ) that correctly captures the complexity status of scorpions and related constructions.
Cite as

Radu Curticapean, Simon Döring, and Daniel Neuen. Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 96:1-96:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{curticapean_et_al:LIPIcs.ESA.2025.96,
  author =	{Curticapean, Radu and D\"{o}ring, Simon and Neuen, Daniel},
  title =	{{Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{96:1--96: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.96},
  URN =		{urn:nbn:de:0030-drops-245651},
  doi =		{10.4230/LIPIcs.ESA.2025.96},
  annote =	{Keywords: induced subgraphs, counting complexity, parameterized complexity, scorpions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.7
Parameterised Holant Problems

Authors: Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt

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

Abstract
We investigate the complexity of parameterised holant problems p-Holant(𝒮) for families of symmetric signatures 𝒮. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures 𝒮: Depending on the signatures, p-Holant(𝒮) is either 1) solvable in "FPT-near-linear time", i.e., in time f(k)⋅ 𝒪̃(|x|), or 2) solvable in "FPT-matrix-multiplication time", i.e., in time f(k)⋅ {𝒪}(n^{ω}), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or 3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)⋅ {𝒪}(n^{ω}). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(𝒮), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(𝒮) is different: Depending on 𝒮 all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).
Cite as

Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt. Parameterised Holant Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aivasiliotis_et_al:LIPIcs.ICALP.2025.7,
  author =	{Aivasiliotis, Panagiotis and G\"{o}bel, Andreas and Roth, Marc and Schmitt, Johannes},
  title =	{{Parameterised Holant Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{7:1--7:14},
  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.7},
  URN =		{urn:nbn:de:0030-drops-233842},
  doi =		{10.4230/LIPIcs.ICALP.2025.7},
  annote =	{Keywords: holant problems, counting problems, parameterised algorithms, fine-grained complexity theory, homomorphisms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.124
Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs

Authors: Daniel Paul-Pena and C. Seshadhri

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

Abstract
We study the classic problem of subgraph counting, where we wish to determine the number of occurrences of a fixed pattern graph H in an input graph G of n vertices. Our focus is on bounded degeneracy inputs, a rich family of graph classes that also characterizes real-world massive networks. Building on the seminal techniques introduced by Chiba-Nishizeki (SICOMP 1985), a recent line of work has built subgraph counting algorithms for bounded degeneracy graphs. Assuming fine-grained complexity conjectures, there is a complete characterization of patterns H for which linear time subgraph counting is possible. For every r ≥ 6, there exists an H with r vertices that cannot be counted in linear time. In this paper, we initiate a study of subquadratic algorithms for subgraph counting on bounded degeneracy graphs. We prove that when H has at most 9 vertices, subgraph counting can be done in Õ(n^{5/3}) time. As a secondary result, we give improved algorithms for counting cycles of length at most 10. Previously, no subquadratic algorithms were known for the above problems on bounded degeneracy graphs. Our main conceptual contribution is a framework that reduces subgraph counting in bounded degeneracy graphs to counting smaller hypergraphs in arbitrary graphs. We believe that our results will help build a general theory of subgraph counting for bounded degeneracy graphs.
Cite as

Daniel Paul-Pena and C. Seshadhri. Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 124:1-124:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{paulpena_et_al:LIPIcs.ICALP.2025.124,
  author =	{Paul-Pena, Daniel and Seshadhri, C.},
  title =	{{Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{124:1--124:18},
  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.124},
  URN =		{urn:nbn:de:0030-drops-235010},
  doi =		{10.4230/LIPIcs.ICALP.2025.124},
  annote =	{Keywords: Homomorphism counting, Bounded degeneracy graphs, Fine-grained complexity, Subgraph counting}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.TIME.2024.3
Rule-Based Temporal Reasoning: Exploring DatalogMTL (Invited Talk)

Authors: Przemysław Andrzej Wałęga

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
I will introduce DatalogMTL - an extension of Datalog, augmenting it with operators known from metric temporal logic (MTL). DatalogMTL is an expressive language which allows us for complex temporal reasoning over a dense timeline and, at the same time, remains decidable. I will provide an overview of research on DatalogMTL by discussing its computational complexity, syntactic and semantic modifications, practical reasoning approaches, applications, and future research directions.
Cite as

Przemysław Andrzej Wałęga. Rule-Based Temporal Reasoning: Exploring DatalogMTL (Invited Talk). In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{walega:LIPIcs.TIME.2024.3,
  author =	{Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  title =	{{Rule-Based Temporal Reasoning: Exploring DatalogMTL}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{3:1--3:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.3},
  URN =		{urn:nbn:de:0030-drops-212106},
  doi =		{10.4230/LIPIcs.TIME.2024.3},
  annote =	{Keywords: Temporal Datalog, Temporal Logic Programming, Temporal Reasoning}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.48
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs

Authors: Matthias Lanzinger and Igor Razgon

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
Generalised hypertree width (ghw) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing ghw of a hypergraph is notoriously hard. The decision version of the problem, checking whether ghw(H) ≤ k, is paraNP-hard when parameterised by k. Furthermore, approximation of ghw is at least as hard as approximation of Set-Cover, which is known to not admit any FPT approximation algorithms. Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs - such as bounds on the size of edge intersections - that permit XP algorithms for ghw. Yet, even under these restrictions that problem has so far evaded any kind of FPT algorithm. In this paper we make the first step towards FPT algorithms for ghw by showing that the parameter can be approximated in FPT time for graphs of bounded edge intersection size. In concrete terms we show that there exists an FPT algorithm, parameterised by k and d, that for input hypergraph H with maximal cardinality of edge intersections d and integer k either outputs a tree decomposition with ghw(H) ≤ 4k(k+d+1)(2k-1), or rejects, in which case it is guaranteed that ghw(H) > k. Thus, in the special case of hypergraphs of bounded edge intersection, we obtain an FPT O(k³)-approximation algorithm for ghw.
Cite as

Matthias Lanzinger and Igor Razgon. FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lanzinger_et_al:LIPIcs.STACS.2024.48,
  author =	{Lanzinger, Matthias and Razgon, Igor},
  title =	{{FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.48},
  URN =		{urn:nbn:de:0030-drops-197588},
  doi =		{10.4230/LIPIcs.STACS.2024.48},
  annote =	{Keywords: generalized hypertree width, hypergraphs, parameterized algorithms, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.41
Fractional Covers of Hypergraphs with Bounded Multi-Intersection

Authors: Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. This allows us to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤ k for some constant k. We also show how our results translate to fractional vertex covers.
Cite as

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. Fractional Covers of Hypergraphs with Bounded Multi-Intersection. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gottlob_et_al:LIPIcs.MFCS.2020.41,
  author =	{Gottlob, Georg and Lanzinger, Matthias and Pichler, Reinhard and Razgon, Igor},
  title =	{{Fractional Covers of Hypergraphs with Bounded Multi-Intersection}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.41},
  URN =		{urn:nbn:de:0030-drops-127317},
  doi =		{10.4230/LIPIcs.MFCS.2020.41},
  annote =	{Keywords: Fractional graph theory, fractional edge cover, fractional hypertree width, bounded multi-intersection, fractional cover, fractional vertex cover}
}
  • Refine by Type
  • 10 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 5 2025
  • 2 2024
  • 1 2020

  • Refine by Author
  • 3 Lanzinger, Matthias
  • 2 Pichler, Reinhard
  • 2 Razgon, Igor
  • 2 Wałęga, Przemysław Andrzej
  • 1 Aivasiliotis, Panagiotis
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Hypergraphs
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Computing methodologies → Temporal reasoning
  • 1 Information systems → Database query processing
  • Show More...

  • Refine by Keyword
  • 2 Temporal Reasoning
  • 1 Acyclic Conjunctive Queries
  • 1 Aggregate Queries
  • 1 Bounded degeneracy graphs
  • 1 DatalogMTL
  • 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