Search Results

Documents authored by Lanzinger, Matthias

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact