Home
Research
Teaching
 Name: Michael Lampis
Research interests:

I am generally interested in the field of theoretical computer science and more specifically in algorithm design and analysis. Favorite topics include approximation algorithms and fixed-parameter tractability.

Research projects and grants:

I am or have been the Principal Investigator of the following projects.

  1. Project S-EX-AP-PE-AL (Sub-EXponential APproximation and ParametErized ALgorithms). ANR-funded project under the young researcher (JCJC) program. Duration: Feb 2022-Feb 2026 (4 years). Total budget: 177,000 Euros.
  2. Project COAL-GAS (Complexity, Algorithms, Games, and Social Choice). Bilateral project with National Technical University of Athens, Greece, under the Global Seed Fund program of Université Paris-PSL and by the CNRS. Duration: Jan 2024-Dec 2024 (one year). Total budget: 11,000 Euros.
  3. Project PARAGA (Parameterized Approximation Graph Algorithms). Bilateral project with Japan, under the CNRS-JST PRC program. PI of Japanese team: Yota Otachi. Duration: Jan 2019-Dec 2020 (two years). Total budget: 16,000 Euros + 4,000,000 Yen.
  4. Project GRAPA (Graph Algorithms for Parameterized Approximation). Bilateral project with Japan, under the PHC Sakura Program. PI of Japanese team: Yota Otachi. Duration: Jan 2017-Dec 2018 (two years). Total budget: 12,000 Euros + 2,000,000 Yen.
  5. Project FAPA (Frontiers in Parameterized Approximation). Project funded under the JCJC program of the CNRS. Duration: Jan 2015-Dec 2015 (one year). Total budget: 6,000 Euros.

In addition, I am (or have been) a member of the following research projects.

  1. Project MultiFAC (Multiple Facility Location). PSL funded project in collaboration with the ENS. Duration: Jan 2017-Dec 2018 (two years). Total budget: 80,000 Euros. PI: Vangelis Paschos.
  2. Project Stability versus Optimality in Dynamic Environment Agorithmics. PGMO funded project in collaboration with LIP6. Duration: Jan 2017-Dec 2017 (one year). Total budget: 6,000 Euros. PI: Bruno Escoffier.
  3. Project APPEAR (Approximation Algorithms for the Efficient Allocation of Resources). Project funded under the JCJC program of the CNRS. Duration: Jan 2016-Dec 2016 (one year). Total budget: 12,000 Euros. PI: Julien Lesca.
Student Supervision:

PhD students

  1. Ioannis Katsikarelis. Starting date: Sep 2015. Graduated in Dec 2019. Jointly supervised with Vangelis Paschos. Thesis title: "Structurally Parameterized Tight Bounds and Approximation for Generalizations of Independence and Domination".
  2. Louis Dublois. Starting date: Sep 2017. Graduated in July 2021. Jointly supervised with Vangelis Paschos. Thesis topic: "Algorithms and Lower Bounds for Certain NP-hard Dominations Problems with Private Structure".
  3. Manolis Vasilakis. Starting date: Sep 2022. Thesis topic: "FPT Approximation algorithms".

Master's students

  1. Alban Guerbois. Mar 2021-Sep 2021. Master's thesis topic: Graph Alcuin Number.
  2. Hacene Kerkache. Mar 2016-Sep 2016. Master's thesis topic: The computational complexity of games and puzzles.
Peer-reviewed Publications:
Below is a list of publications, including drafts. For papers published in an open access journal, you can also find link to the "official" version (which is usually better than the draft).
  1. Title: The Primal Pathwidth SETH
    Author(s): Michael Lampis
    Conference: SODA 2025
    Links: arxiv
  2. Title: Core Stability in Additively Separable Hedonic Games of Low Treewidth
    Author(s): Tesshu Hanaka, Michael Lampis, and Noleen Köhler
    Conference: ISAAC 2024
    Links: arxiv
  3. Title: Parameterized Vertex Integrity Revisited
    Author(s): Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari
    Conference: MFCS 2024
    Links: arxiv
  4. Title: Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
    Author(s): Andreas Emil Feldmann and Michael Lampis
    Conference: ICALP 2024
    Links: arxiv
  5. Title: Faster Winner Determination Algorithms for (Colored) Arc Kayles
    Author(s): Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono and Kanae Yoshiwatari
    Conference: SOFSEM 2024 (Best Paper Award)
    Links: draft
  6. Title: Structural Parameterizations for Two Bounded Degree Problems Revisited
    Author(s): Michael Lampis and Manolis Vasilakis
    Conference: ESA 2023
    Links: draft
  7. Title: Parameterized Max Min Feedback Vertex Set
    Author(s): Michael Lampis, Nikolaos Melissinos, and Manolis Vasilakis
    Conference: MFCS 2023
    Links: draft
  8. Title: First Order Logic on Pathwidth Revisited Again
    Author(s): Michael Lampis
    Conference: ICALP 2023
    Links: draft
  9. Title: Hedonic Games and Treewidth Revisited
    Author(s): Tesshu Hanaka and Michael Lampis
    Conference: ESA 2022
    Links: draft
  10. Title: Determining a Slater Winner is Complete for Parallel Access to NP
    Author(s): Michael Lampis
    Conference: STACS 2022
    Links: draft
  11. Title: Fine-Grained Meta-Theorems for Vertex Integrity
    Author(s): Michael Lampis, Valia Mitsou
    Conference: ISAAC 2021
    Journal: LMCS (2024)
    Links: online
  12. Title: Filling Crosswords is Very Hard
    Author(s): Laurent Gourvès, Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos
    Conference: ISAAC 2021
    Journal: TCS (2024)
    Links: draft
  13. Title: Minimum Stable Cut and Treewidth
    Author(s): Michael Lampis
    Conference: ICALP 2021
    Links: draft
  14. Title: Digraph Coloring and Distance to Acyclicity
    Author(s): Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos
    Conference: STACS 2021
    Journal: ToCS (2023) special issue for STACS 2021
    Links: draft
  15. Title: Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
    Author(s): Louis Dublois, Michael Lampis, and Vangelis Th. Paschos
    Conference: CIAC 2021
    Journal: TCS (2022)
    Links: draft
  16. Title: New Algorithms for Mixed Dominating Set
    Author(s): Louis Dublois, Michael Lampis, and Vangelis Th. Paschos
    Conference: IPEC 2020
    Journal: DMTCS (2021)
    Links: online
  17. Title: (In)approximability of Maximum Minimal FVS
    Author(s): Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos
    Conference: ISAAC 2020
    Journal: JCSS (2021)
    Links: draft
  18. Title: Grundy Distinguishes Treewidth from Pathwidth
    Author(s): Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi
    Conference: ESA 2020
    Journal: SIDMA (2022)
    Links: draft
  19. Title: Parameterized Complexity of (A,l)-Path Packing
    Author(s): Remy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, and Yota Otachi
    Conference: IWOCA 2020
    Journal: Algorithmica (2021)
    Links: draft
  20. Title: K3 Edge Cover Problem in a Wide Sense
    Author(s): Kyohei Chiba, Remy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, and Yota Otachi
    Journal:        JIP 2020
    Links: online
  21. Title: Improved (In-)Approximability Bounds for d-Scattered Set
    Author(s): Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos
    Conference: WAOA 2019
    Journal: JGAA (2023)
    Links: online
  22. Title: Maximum Independent Sets in Subcubic Graphs: New Results
    Author(s): Ararat Harutyunyan, Michael Lampis, Vadim Lozin, and Jerome Monnot
    Conference: WG 2019
    Journal: TCS (2020)
    Links: draft
  23. Title: Independent Set Reconfiguration Parameterized by Modular-Width
    Author(s): Remy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, and Yota Otachi
    Conference: WG 2019
    Journal: Algorithmica (2020)
    Links: draft
  24. Title: Token Sliding on Split Graphs
    Author(s): Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora
    Conference: STACS 2019
    Journal: ToCS (2020)
    Links: draft
  25. Title: Parameterized Complexity of Safe Set
    Author(s): Remy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, and Yota Otachi
    Conference: CIAC 2019
    Journal: JGAA (2020)
    Links: online
  26. Title: Finer Tight Bounds for Coloring on Clique-width
    Author(s): Michael Lampis
    Conference: ICALP 2018
    Journal: SIDMA (2020)
    Links: draft
  27. Title: New Results on Directed Edge Dominating Set
    Author(s): Remy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis
    Conference: MFCS 2018
    Journal: DMTCS (2023)
    Links: online
  28. Title: Parameterized Orientable Deletion
    Author(s): Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora
    Conference: SWAT 2018
    Journal: Algorithmica (2020)
    Links: draft
  29. Title: Multistage Matchings
    Author(s): Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos
    Conference: SWAT 2018
    Links: draft
  30. Title: Structurally Parameterized d-Scattered Set
    Author(s): Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos
    Conference: WG 2018
    Journal: DAM (2020)
    Links: draft
  31. Title: How Bad is the Freedom to Flood-It?
    Author(s): Remy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi
    Conference: FUN 2018
    Journal: JGAA (2019)
    Links: online
  32. Title: QBF as an Alternative to Courcelle's Theorem
    Author(s): Michael Lampis, Stefan Mengel, and Valia Mitsou
    Conference: SAT 2018
    Links: draft
  33. Title: Parameterized (Approximate) Defective Coloring
    Author(s): Remy Belmonte, Michael Lampis, and Valia Mitsou
    Conference: STACS 2018
    Journal: SIDMA (2020)
    Links: draft
  34. Title: Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
    Author(s): Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos
    Conference: ISAAC 2017
    Journal: DAM (2019)
    Links: draft
  35. Title: Treewidth with a Quantifier Alternation Revisited
    Author(s): Michael Lampis and Valia Mitsou
    Conference: IPEC 2017
    Links: draft
  36. Title: On the Parameterized Complexity of Red-Blue Points Separation
    Author(s): Edouard Bonnet, Panos Giannopoulos, and Michael Lampis
    Conference: IPEC 2017
    Journal: JoCG (2019)
    Links: online
  37. Title: Defective Coloring on Classes of Perfect Graphs
    Author(s): Rémy Belmonte, Michael Lampis, Valia Mitsou
    Conference: WG 2017
    Journal: DMTCS (2022)
    Links: link
  38. Title: The Many Facets of Upper Domination
    Author(s): Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jerome Monnot, Vangelis Th. Paschos
    Conference: IWOCA 2016 (approximation part) and AAIM 2016 (parameterized part)
    Journal: TCS 2017 (merged paper)
    Links: draft
  39. Title: Parameterized Power Vertex Cover
    Author(s): Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis
    Conference: WG 2016
    Journal: DMTCS (2018)
    Links: online
  40. Title: Sub-Exponential Approximation Schemes for CSPs: From Dense to Almost-Sparse.
    Author(s): Dimitris Fotakis, Michael Lampis and Vangelis Paschos
    Conference: STACS 2016
    Links: draft
  41. Title: Time-Approximation Trade-offs for Inapproximable Problems.
    Author(s): Edouard Bonnet, Michael Lampis and Vangelis Paschos
    Conference: STACS 2016
    Journal: JCSS (2018)
    Links: draft
  42. Title: Complexity and Approximability for Parameterized CSPs
    Author(s): Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Moemke
    Conference: IPEC 2015
    Journal: Algorithmica (2017)
    Links: draft
  43. Title: Parameterized Algorithms for Parity Games
    Author(s): Jakub Gajarsky, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak
    Conference: MFCS 2015
    Links: draft
  44. Title: Parameterized Approximation Schemes Using Graph Widths
    Author(s): Michael Lampis
    Conference: ICALP 2014
    Links: draft
  45. Title: Parameterized Edge Hamiltonicity
    Author(s): Michael Lampis, Kazuhisa Makino, Valia Mitsou and Yushi Uno
    Conference: WG 2014
    Journal: DAM (2017)
    Links: draft
  46. Title: The Computational Complexity of the Game of Set and its Theoretical Applications
    Author(s): Michael Lampis and Valia Mitsou
    Conference: LATIN 2014
    Links: draft
  47. Title: New Inapproximability Bounds for TSP
    Author(s): Marek Karpinski, Michael Lampis and Richard Schmied
    Conference: ISAAC 2013
    Journal: JCSS (2015)
    Links: draft
  48. Title: Parameterized Algorithms for Modular-Width
    Author(s): Jakub Gajarsky, Michael Lampis and Sebastian Ordyniak
    Conference: IPEC 2013
    Links: draft
  49. Title: Model Checking Lower Bounds for Simple Graphs
    Author(s): Michael Lampis
    Conference: ICALP 2013
    Journal: Logical Methods in Computer Science (2014)
    Links: online
  50. Title: Improved Inapproximability for TSP
    Author(s): Michael Lampis
    Conference: APPROX 2012
    Journal: Theory of Computing (2014)
    Links: online
  51. Title: Scrabble is PSPACE-complete
    Author(s): Michael Lampis, Valia Mitsou and Karolina Soltys
    Conference: FUN with Algorithms 2012
    Journal: Journal of Information Processing (2015)
    Links: draft
  52. Title: A kernel of order 2k-clogk for Vertex Cover
    Author(s): Michael Lampis
    Journal:        Information Processing Letters (2011)
    Links: draft
  53. Title: Parameterized Maximum Path Coloring
    Author(s): Michael Lampis
    Conference: IPEC 2011
    Journal: Theoretical Computer Science (2013)
    Links: draft
  54. Title: Algorithmic Meta-Theorems for Restrictions of Treewidth
    Author(s): Michael Lampis
    Conference: ESA 2010
    Journal: Algorithmica (2012)
    Links: draft
  55. Title: Parameterized Modal Satisfiability
    Author(s): Antonis Achilleos, Michael Lampis and Valia Mitsou
    Conference: ICALP 2010
    Journal: Algorithmica (2012)
    Links: draft
  56. Title: Vertex Cover Problem Parameterized Above and Below Tight Bounds
    Author(s): Gregory Gutin, Eun Jung Kim, Michael Lampis and Valia Mitsou
    Journal:        Theory of Computing Systems (2011)
    Links: draft
  57. Title: Online Maximum Directed Cut
    Author(s): Amotz Bar-Noy and Michael Lampis
    Conference: ISAAC 2009
    Journal: Journal of Combinatorial Optimization (2012)
    Links: draft
  58. Title: Ordered Coloring for Grids and Related Graphs
    Author(s): Amotz Bar-Noy, Panagiotis Cheilaris, Michael Lampis, Valia Mitsou and Stathis Zachos
    Conference: SIROCCO 2009
    Journal: Theoretical Computer Science (2012)
    Links: draft
  59. Title: Queen Labelings
    Author(s):     Gary Bloom, Michael Lampis, Francisco Antoni Muntaner-Batle, and Miquel Rius-Font
    Journal:    AKCE Int. J. of Graphs and Combinatorics (2010)
    Links: draft
  60. Title: On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
    Author(s): Michael Lampis, Georgia Kaouri and Valia Mitsou
    Conference: ISAAC 2008
    Journal: Discrete Optimization (2011)
    Links: draft
  61. Title: The Ferry Cover Problem
    Author(s): Michael Lampis and Valia Mitsou
    Conference: FUN with Algorithms 2007
    Journal: Theory of Computing Systems (2009)
    Links:
  62. Title: Periodic Metro Scheduling
    Author(s): Evangelos Bampas, Georgia Kaouri, Michael Lampis and Aris Pagourtzis
    Conference: ATMOS 2006
    Links: online
  63. Title: Quantum Data and Control Made Easier
    Author(s): Michael Lampis, Kyriakos G. Ginis, Michalis A. Papakyriakou and Nikolaos S. Papaspyrou
    Conference: QPL 2006
    Journal: Electronic Notes on Theoretical Computer Science (2008)
    Links: draft
Community Service:
  • Conferences
    • I have served (or I am currently serving) on the PC of
    • I have been an external reviewer for the following conferences: STACS 2025, ESA 2024, MFCS 2024, ICALP 2024, SWAT 2024, IWOCA 2024, FOCS 2023, ICALP 2023, MFCS 2023, IWOCA 2023, MFCS 2022, FUN 2022, STACS 2022, FSTTCS 2021, ISAAC 2021, ICALP 2021, STACS 2021, CIAC 2021, IPEC 2020, ISAAC 2020, MFCS 2020, WG 2020, SODA 2020, SWAT 2020, WALCOM 2020, IPEC 2019, ESA 2019, MFCS 2019, WADS 2019, WG 2019, LICS 2019, STOC 2019, STACS 2019, SODA 2019, CIAC 2019, WALCOM 2019, ESA 2018, MFCS 2018, ICALP 2018, WG 2018, SWAT 2018, SAT 2018, STACS 2018, LATIN 2018, IWOCA 2018, ESA 2017, IPEC 2017, WG 2017, COCOON 2017, FCT 2017, EUROCOMB 2017, ISAAC 2016, IPEC 2016, WAOA 2016, ESA 2016, MFCS 2016, ICALP 2016, SODA 2016, ISCO 2016, IWOCA 2016, ICALP 2015, IPEC 2015, SoCG 2015, STACS 2015, WADS 2015, ESA 2014, ISAAC 2014, SODA 2014, WG 2014, CCC 2013, CIAC 2013, FAW-AAIM 2013, FCT 2013, WADS 2013, ESA 2012, SWAT 2012, TAMC 2012, MFCS 2011, ICALP 2011, IPEC 2010, WG 2010, APPROX 2010, SIROCCO 2010, IWPEC 2009, WAOA 2008, CiE 2008
  • Journals
    • I have been an external reviewer for the following journals: Theoretical Computer Science (x16), Discrete Applied Mathematics (x3), Journal of Computer and System Sciences (x5), SIAM Journal on Discrete Mathematics (x4), ACM Transactions on Algorithms (x4), Logical Methods in Computer Science (x2), Discrete Optimization (x3), Information Processing Letters, Journal of Discrete Algorithms, Acta Informatica, Discrete Mathematics and Theoretical Computer Science (x2), SIAM Journal of Computing, Theory of Computing Systems (x3), Algorithmica (x3), Operational Research.
Dissertations:
  • Structural Graph Parameters, Fine-Grained Complexity, and Approximation. (full text). Habilitation (HDR) March 2022, Université Paris-Dauphine. Advisor: Vangelis Paschos.
  • Structural Parameterizations of Hard Graph Problems (full text). PhD thesis. September 2011, Graduate Center, CUNY. Advisor: Amotz Bar-Noy.
Other Talks:
  • Invited talk: "Quantifier Alternations and Graph Widths", Graph Width Parameters Workshop 2023, July 2023.
  • Invited talk: "Grundy Distinguishes Treewidth from Pathwidth", Indian Parameterized Complexity Seminar, Sep 2020.
  • Invited Keynote: ACAC 2016, Athens, Aug 2016. "Trading Time for Approximation"
  • Simons Institute, UC Berkeley, Nov 5th 2015. "Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse" (link)
  • KAIST, South Korea, May 13th 2014. "Parameterized Approximation Schemes Using Graph Widths" (video)
  • New York University, May 3rd 2013. "Baby steps towards TSP inapproximability"
  • Masaryk University, Brno, March 11th 2013. "Model Checking Lower Bounds for Simple Graphs"
  • University of Bonn, January 22nd 2013. "Improved Inapproximability for TSP: The Role of Bounded Occurrence CSPs"
  • New York Colloquium on Algorithms and Complexity, CUNY Graduate Center, November 17th 2011. "The Landscape of Structural Graph Parameters".
  • Royal Holloway University of London, Computer Science Department Algorithms Seminar, July 13th 2010. "Algorithmic Meta-Theorems for Restrictions of Treewidth".
  • Royal Holloway University of London, Computer Science Department Algorithms Seminar, June 1st 2009. "On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures" (Based on joint work with Georgia Kaouri and Valia Mitsou)
  • Athens Colloquium on Algorithms and Complexity (ACAC) 2006: "On the Relation Between Vehicle Scheduling and Path Coloring", August 22nd, 2006 (Based on joint work with Evangelos Bampas, Georgia Kaouri, Aris Pagourtzis)