3 Search Results for "Stacho, Ladislav"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.65
Parameterized Spanning Tree Congestion

Authors: Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

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

Abstract
In this paper we study the Spanning Tree Congestion problem, where we are given an undirected graph G = (V,E) and are asked to find a spanning tree T of minimum maximum congestion. Here, the congestion of an edge e ∈ T is the number of edges uv ∈ E such that the (unique) path from u to v in T traverses e. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results: - We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form "vertex-deletion distance to class 𝒞", thus obtaining W[1]-hardness for more restricted parameters, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on graphs of modular-width 4. - Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. - Complementing the problem’s W[1]-hardness for treewidth, we formulate an algorithm that runs in time roughly {(k+w)}^{𝒪(w)}, where k is the desired congestion and w the treewidth, improving a previous argument for parameter k+w that was based on Courcelle’s theorem. This explicit algorithm pays off in two ways: it allows us to obtain an FPT approximation scheme for parameter treewidth, that is, a (1+ε)-approximation running in time roughly {(w/ε)}^{𝒪(w)}; and it leads to an exact FPT algorithm for parameter clique-width+k via a Win/Win argument. - Finally, motivated by the problem’s hardness for most standard structural parameters, we present FPT algorithms for several more restricted cases, namely, for the parameters vertex-deletion distance to clique; vertex integrity; and feedback edge set, in the latter case also achieving a single-exponential running time dependence on the parameter.
Cite as

Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Parameterized Spanning Tree Congestion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.MFCS.2025.65,
  author =	{Lampis, Michael and Mitsou, Valia and Nemery, Edouard and Otachi, Yota and Vasilakis, Manolis and Vaz, Daniel},
  title =	{{Parameterized Spanning Tree Congestion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{65:1--65:20},
  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.65},
  URN =		{urn:nbn:de:0030-drops-241724},
  doi =		{10.4230/LIPIcs.MFCS.2025.65},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Graph Width Parameters}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.31
Flexible List Colorings in Graphs with Special Degeneracy Conditions

Authors: Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Δ that are ε-flexibly Δ-choosable for some ε = ε(Δ) > 0, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020], and we give conditions for list assignments by which graphs of treewidth k are 1/(k+1)-flexibly (k+1)-choosable. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable. Finally, we introduce a notion of flexible degeneracy, which strengthens flexible choosability, and we show that apart from a well-understood class of exceptions, 3-connected non-regular graphs of maximum degree Δ are flexibly (Δ - 1)-degenerate.
Cite as

Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho. Flexible List Colorings in Graphs with Special Degeneracy Conditions. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bradshaw_et_al:LIPIcs.ISAAC.2020.31,
  author =	{Bradshaw, Peter and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Stacho, Ladislav},
  title =	{{Flexible List Colorings in Graphs with Special Degeneracy Conditions}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.31},
  URN =		{urn:nbn:de:0030-drops-133750},
  doi =		{10.4230/LIPIcs.ISAAC.2020.31},
  annote =	{Keywords: Flexibility, List Coloring, Choosability, Degeneracy}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.360
Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems

Authors: Ho-Lin Chen, David Doty, Ján Manuch, Arash Rafiey, and Ladislav Stacho

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly and avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.
Cite as

Ho-Lin Chen, David Doty, Ján Manuch, Arash Rafiey, and Ladislav Stacho. Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 360-373, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.SOCG.2015.360,
  author =	{Chen, Ho-Lin and Doty, David and Manuch, J\'{a}n and Rafiey, Arash and Stacho, Ladislav},
  title =	{{Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{360--373},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.360},
  URN =		{urn:nbn:de:0030-drops-50935},
  doi =		{10.4230/LIPIcs.SOCG.2015.360},
  annote =	{Keywords: self-assembly, hierarchical, pumping}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2020
  • 1 2015

  • Refine by Author
  • 2 Stacho, Ladislav
  • 1 Bradshaw, Peter
  • 1 Chen, Ho-Lin
  • 1 Doty, David
  • 1 Lampis, Michael
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Graph coloring
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Choosability
  • 1 Degeneracy
  • 1 Flexibility
  • 1 Graph Width Parameters
  • 1 List Coloring
  • 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