I'm a postdoctoral researcher in the Algorithms and Complexity Group at TU Wien under the mentorship of Robert Ganian since Nov 2023. Before that, I worked at Amazon for a year as an applied scientist, where I built and analysed optimisation models for the transportation network of the company.
In 2022, I finished my doctorate at ETH Zurich, in the Theory of Combinatorial Algorithm Group of Bernd Gärtner and Emo Welzl. Before, I studied a master's programme in operational research at London School of Economics, where I wrote a dissertation under the supervision of Gregory Sorkin.
My general research interests are algorithms, computational complexity, discrete mathematics, combinatorics, and optimisation. In particular, I am interested in algorithmic questions in many areas such as combinatorial optimisation, graph theory, operational research, and computational geometry. I am also interested in interdisciplinary topics, especially the application of optimisation and algorithmic thinking in the real world as well as the discovery of mathematical patterns and structures in other fields.
E-mail: phuchung.hoang{at}gmail
Fine-grained complexity of computing degree-constrained spanning tree [arxiv]
(with
Narek Bojikian,
Alexander Firbas,
Robert Ganian,
Krisztina Szilágyi)
Minimum maximal matchings in permutahedra [arxiv]
(with Sofia Brenner,
Jiří Fink,
Arturo Merino,
Vincent Pilaud)
Parameterized complexity of efficient sortation [arxiv]
(with Robert Ganian and Simon Wietheger)
Drawings of complete multipartite graphs up to triangle flips
(with Oswin Aichholzer,
Man-Kwun Chiu,
Michael Hoffmann,
Jan Kynčl,
Yannic Maus,
Birgit Vogtenhuber,
Alexandra Weinberger)
in Journal of Computational Geometry, 15(2), 2024
Conflict-free coloring: Graphs of bounded clique width and intersection graphs [arxiv]
(with Sriram Bhyravarapu, Tim A. Hartmann, Subrahmanyam Kalyanasundaram, and
I. Vinod Reddy)
in Algorithmica, 86:2250–2280, 2024
Assistance and interdiction problems on interval graphs [arxiv]
(with Stefan Lendl and Lasse Wulf)
in Discrete Applied Mathematics, 340:153-170, 2023
Combinatorial generation via permutation languages. V. Acyclic orientations [arxiv]
(with Jean Cardinal,
Arturo Merino,
Ondřej Mička, and
Torsten Mütze)
in SIAM Journal on Discrete Mathematics, 37(3), 2023
On approximating the rank of graph divisors [arxiv]
(with Kristóf Bérczi and Lilla Tóthmérész)
in Discrete Mathematics, 346(9), 2023
Combinatorial generation via permutation languages: I. Fundamentals [arxiv]
(with Elizabeth Hartung,
Torsten Mütze, and
Aaron Williams)
in Transactions of the AMS, 375:2255-2291, 2022
Combinatorial generation via permutation languages: II. Lattice congruences [arxiv]
(with Torsten Mütze)
in Israel Journal of Mathematics, 244:359–417, 2021
Signotopes with few plus signs [arxiv]
(with Helena Bergold and Lukas Egeling)
in Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025), to appear
Generating all invertible matrices by row operations [arxiv]
(with
Petr Gregor,
Arturo Merino, and
Ondřej Mička)
in Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024)
The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5 [arxiv]
(with Sophia Heimann and Stefan Hougardy)
in Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Drawings of complete multipartite graphs up to triangle flips
(with Oswin Aichholzer,
Man-Kwun Chiu,
Michael Hoffmann,
Jan Kynčl,
Yannic Maus,
Birgit Vogtenhuber,
Alexandra Weinberger)
in Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)
Zigzagging through acyclic orientations of graphs and hypergraphs
(with Jean Cardinal,
Arturo Merino,
Ondřej Mička, and
Torsten Mütze)
in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA23)
A Subexponential algorithm for ARRIVAL
(with Bernd Gärtner and Sebastian Haslebacher)
in Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Combinatorial generation via permutation languages [poster]
(with Elizabeth Hartung, Torsten Mütze, and Aaron Williams)
in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA20)
On the PLS-completeness of TSP/k-Opt
(with Stefan Hougardy)
Technical report at University of Bonn
On two combinatorial reconfiguration problems: Reachability and Hamiltonicity
Doctoral thesis at ETH Zürich
Efficient Algorithms, TU Wien, Summer 2025
Frontiers of Algorithms and Complexity, TU Wien, Winter 2024
Efficient Algorithms, TU Wien, Summer 2024
Optimization in Data Science, ETH Zurich, Spring 2022
Algorithms Lab, ETH Zurich, Autumn 2021
Computer Science 1, ETH Zurich, Spring 2021
Algorithms Lab, ETH Zurich, Autumn 2020
Optimization in Data Science, ETH Zurich, Spring 2020 (Head Assistant)
Algorithms, Probability, and Computing, ETH Zurich, Autumn 2019
Optimization in Data Science, ETH Zurich, Spring 2019
Fine-grained complexity of computing degree-constrained spanning trees, Oberseminar Discrete Optimization, University of Bonn, Germany, Mar 2025
Signotope with few plus signs,
Generating all invertible matrices by row operations,
Parameterized complexity of efficient sortation IGAFIT Workshop for Algorithms Postdocs in Europe (AlgPiE by IGAFIT 2024), Dagstuhl, Germany, Sep 2024
The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Tallinn, Estonia, Jul 2024
Drawings of Complete Multipartite Graphs Up to Triangle Flips Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2023, Paderborn, Germany, Jul 2023
Zigzagging through acyclic orientations of graphs and hypergraphs Mittagsseminar, ETH Zürich, Switzerland, May 2023
Hardness of Approximating the Rank of a Graph Divisor Mittagsseminar, ETH Zürich, Switzerland, May 2022
Gioan's Theorem for complete bipartite graph Mittagsseminar, ETH Zürich, Switzerland, Dec 2021
A subexponential algorithm for ARRIVAL,
Assistance and interdiction problems on interval graphs Mittagsseminar, ETH Zürich, Switzerland, Nov 2020
Flip graph of combinatorial triangulations, Mittagsseminar, ETH Zürich, Switzerland, May 2020
ARRIVAL: A zero-player reachability switching game,
Combinatorial generation via permutation languages, ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA20), Salt Lake City, UT, US, Jan 2020
Lattice quotients of the weak order, Mittagsseminar, ETH Zürich, Switzerland, Nov 2019
Exhaustive generation of pattern-avoiding permutations, Permutation Patterns 2019, Zurich, Switzerland, Jun 2019
Rank deficiency distribution of constrained random k-XORSAT matrix, ETH Zürich, Switzerland, Jul 2018
Lukas Egeling, Representation of Signotopes and Their Structures, Master CS, Mar 2024, with Helena Bergold and Bernd Gärtner
Ferdinand Nussbaum, Minimal and Maximal Elements of Lattice Congruences, Bachelor CS, Sep 2022
Lukas Hächler, Statistics for Tram Traffic Safety in Zurich, Master CS, Aug 2022, with Bernd Gärtner and Julia Hörrmann
Alain Bastian, Minimum partition into plane subgraphs, Master CS, Mar 2022, with Michael Hoffmann
Manuel Wiedmer, Reachability in the Hunger Game, Semester Thesis Maths, Sep 2021, with Bernd Gärtner
Chio Ge, The Multi-Run Procedure in ARRIVAL, Bachelor CS, Jul 2021, with Bernd Gärtner
Sebastian Haslebacher, Restrictions on ARRIVAL (part 2), Practical Work CS, Jan 2021, with Bernd Gärtner
Sebastian Haslebacher, Restrictions on ARRIVAL, Bachelor CS, Jul 2020, with Bernd Gärtner
Manuel Nowack, Minimum jump graph, Bachelor CS, Jul 2020, with Torsten Mütze
Janis Nertinger, One line and n points deterministically, Master Maths, Sep 2019, with Michael Hoffmann
Giovanni Compagnoni, Flip graphs of combinatorial triangulations, Master Maths, Sep 2019, with Michael Hoffmann
Jan Schilliger, Unique sink orientations and End of potential line, Bachelor CS, Jul 2019, with Bernd Gärtner
Jakob Roffler, Solving small unique sink orientations, Bachelor CS, Mar 2019, with Bernd Gärtner