DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2025.15

Symmetry Classes of Hamiltonian Cycles

Authors: Júlia Baligács, Sofia Brenner, Annette Lutz, and Lena Volk

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

Abstract

We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry.

Cite as

Júlia Baligács, Sofia Brenner, Annette Lutz, and Lena Volk. Symmetry Classes of Hamiltonian Cycles. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.MFCS.2025.15,
  author =	{Balig\'{a}cs, J\'{u}lia and Brenner, Sofia and Lutz, Annette and Volk, Lena},
  title =	{{Symmetry Classes of Hamiltonian Cycles}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{15:1--15:18},
  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.15},
  URN =		{urn:nbn:de:0030-drops-241221},
  doi =		{10.4230/LIPIcs.MFCS.2025.15},
  annote =	{Keywords: Hamiltonian cycles, graph automorphisms, Cayley graphs, abelian groups, Cartesian product of graphs}
}

Document

DOI: 10.4230/LIPIcs.ESA.2024.47

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Authors: Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial (α,μ)-approximation is possible, i.e., a solution that with budget B+α for all B ∈ ℝ_{≥ 0} is a multiplicative μ-approximation compared to the optimum solution with budget B. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a (χ,1)-approximation, where χ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is (γ,2)-competitive where γ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a (γ,3)-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a (3χ,8)-approximation and, more generally, a ((4𝓁 - 1)χ, (2^{𝓁 + 2})/(2^𝓁 -1))-approximation for every fixed 𝓁 ∈ ℕ.

Cite as

Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2024.47,
  author =	{Disser, Yann and Griesbach, Svenja M. and Klimm, Max and Lutz, Annette},
  title =	{{Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.47},
  URN =		{urn:nbn:de:0030-drops-211188},
  doi =		{10.4230/LIPIcs.ESA.2024.47},
  annote =	{Keywords: incremental optimization, competitive analysis, prize-collecting Steiner-tree}
}

Search Results

Documents authored by Lutz, Annette

Symmetry Classes of Hamiltonian Cycles

Abstract

Cite as

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message