Search Results

Documents authored by Masaříková, Jana

Document
DOI: 10.4230/LIPIcs.MFCS.2025.28
Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument

Authors: Romain Bourneuf, Jana Masaříková, Wojciech Nadara, and Marcin Pilipczuk

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
For a fixed integer t ⩾ 1, a (t-)long claw, denoted S_{t,t,t}, is the unique tree with three leaves, each at distance exactly t from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gyárfás' path argument for S_{t,t,t}-free graphs: given an n-vertex S_{t,t,t}-free graph, one can delete neighborhoods of 𝒪(log n) vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. In this work, we refine the argument of Majewski et al. to its arguably final form: we show that a constant number of neighborhoods suffice. The statement of Majewski et al. is one of the two pillars of a recent quasi-polynomial time algorithm for Maximum Weight Independent Set in S_{t,t,t}-free graphs [Gartland et al., STOC 2024]; our work immediately improves the quasi-polynomial function in the running time bound. Furthermore, our result significantly simplifies known polynomial-time algorithms for Maximum Weight Independent Set in S_{t,t,t}-free graphs with an additional sparsity assumption such as bounded degree or excluding a fixed biclique as a subgraph.
Cite as

Romain Bourneuf, Jana Masaříková, Wojciech Nadara, and Marcin Pilipczuk. Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourneuf_et_al:LIPIcs.MFCS.2025.28,
  author =	{Bourneuf, Romain and Masa\v{r}{\'\i}kov\'{a}, Jana and Nadara, Wojciech and Pilipczuk, Marcin},
  title =	{{Graphs with No Long Claws: An Improved Bound for the Analog of the Gy\'{a}rf\'{a}s' Path Argument}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.28},
  URN =		{urn:nbn:de:0030-drops-241350},
  doi =		{10.4230/LIPIcs.MFCS.2025.28},
  annote =	{Keywords: long-claw-free graphs, extended strip decomposition, maximum weight independent set, Gy\'{a}rf\'{a}s' path, three in a tree}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.67
Separator Theorem and Algorithms for Planar Hyperbolic Graphs

Authors: Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar δ-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed δ ⩾ 0, we can find a small balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set Z) with any subset of the connected components of G - Z induces again a planar δ-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that the size of the separator is poly(δ) ⋅ log n. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar δ-hyperbolic graphs. We prove that both Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant δ, running in n polylog(n) ⋅ 2^𝒪(δ²) ⋅ ε^{-𝒪(δ)} time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no n^{o(δ)}-time algorithm on planar δ-hyperbolic graphs, unless ETH fails.
Cite as

Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki. Separator Theorem and Algorithms for Planar Hyperbolic Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.SoCG.2024.67,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Masa\v{r}{\'\i}kov\'{a}, Jana and van Leeuwen, Erik Jan and Walczak, Bartosz and W\k{e}grzycki, Karol},
  title =	{{Separator Theorem and Algorithms for Planar Hyperbolic Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{67:1--67:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.67},
  URN =		{urn:nbn:de:0030-drops-200126},
  doi =		{10.4230/LIPIcs.SoCG.2024.67},
  annote =	{Keywords: Hyperbolic metric, Planar Graphs, r-Division, Approximation Algorithms}
}
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