4 Search Results for "Hoang, Hung P."

Document
DOI: 10.4230/LIPIcs.MFCS.2024.55
Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes

Authors: Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a,b,c} denote the graph obtained from paths P_{a+1},P_{b+1},P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2,2,1}, S_{3,1,1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S_{2,1,1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2,2,2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.
Cite as

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt. Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goedgebeur_et_al:LIPIcs.MFCS.2024.55,
  author =	{Goedgebeur, Jan and Jooken, Jorik and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and Schaudt, Oliver},
  title =	{{Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.55},
  URN =		{urn:nbn:de:0030-drops-206110},
  doi =		{10.4230/LIPIcs.MFCS.2024.55},
  annote =	{Keywords: graph homomorphism, critical graphs, hereditary graph classes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.84
The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5

Authors: Sophia Heimann, Hung P. Hoang, and Stefan Hougardy

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k ≫ 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ 5.
Cite as

Sophia Heimann, Hung P. Hoang, and Stefan Hougardy. The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 84:1-84:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{heimann_et_al:LIPIcs.ICALP.2024.84,
  author =	{Heimann, Sophia and Hoang, Hung P. and Hougardy, Stefan},
  title =	{{The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{84:1--84:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.84},
  URN =		{urn:nbn:de:0030-drops-202270},
  doi =		{10.4230/LIPIcs.ICALP.2024.84},
  annote =	{Keywords: Traveling Salesman Problem, k-Opt algorithm, PLS-completeness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.6
Drawings of Complete Multipartite Graphs up to Triangle Flips

Authors: Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan’s Theorem states that for any two simple drawings of the complete graph K_n with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on n vertices is bounded by O(n^{16}). The latter proof uses a Carathéodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the following sense: For the complete bipartite graph K_{m,n} minus two edges and K_{m,n} plus one edge for any m,n ≥ 4, as well as K_n minus a 4-cycle for any n ≥ 5, there exist two simple drawings with the same ERS that cannot be transformed into each other using triangle flips. So having the same ERS does not remain sufficient when removing or adding very few edges.
Cite as

Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger. Drawings of Complete Multipartite Graphs up to Triangle Flips. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2023.6,
  author =	{Aichholzer, Oswin and Chiu, Man-Kwun and Hoang, Hung P. and Hoffmann, Michael and Kyn\v{c}l, Jan and Maus, Yannic and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Drawings of Complete Multipartite Graphs up to Triangle Flips}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.6},
  URN =		{urn:nbn:de:0030-drops-178563},
  doi =		{10.4230/LIPIcs.SoCG.2023.6},
  annote =	{Keywords: Simple drawings, simple topological graphs, complete graphs, multipartite graphs, k-partite graphs, bipartite graphs, Gioan’s Theorem, triangle flips, Reidemeister moves}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.69
A Subexponential Algorithm for ARRIVAL

Authors: Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in NP∩coNP but not known to be in 𝖯. The currently best algorithms have runtime 2^Θ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime 2^O(√nlog n). We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.
Cite as

Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A Subexponential Algorithm for ARRIVAL. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.ICALP.2021.69,
  author =	{G\"{a}rtner, Bernd and Haslebacher, Sebastian and Hoang, Hung P.},
  title =	{{A Subexponential Algorithm for ARRIVAL}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.69},
  URN =		{urn:nbn:de:0030-drops-141387},
  doi =		{10.4230/LIPIcs.ICALP.2021.69},
  annote =	{Keywords: Pseudorandom walks, reachability, graph games, switching systems}
}
  • Refine by Author
  • 3 Hoang, Hung P.
  • 1 Aichholzer, Oswin
  • 1 Chiu, Man-Kwun
  • 1 Goedgebeur, Jan
  • 1 Gärtner, Bernd
  • Show More...

  • Refine by Classification
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Graph enumeration
  • Show More...

  • Refine by Keyword
  • 1 Gioan’s Theorem
  • 1 PLS-completeness
  • 1 Pseudorandom walks
  • 1 Reidemeister moves
  • 1 Simple drawings
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2024
  • 1 2021
  • 1 2023

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