Michael Lampis

According to our database, Michael Lampis authored at least 80 papers between 2006 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

k-SUM Hardness Implies Treewidth-SETH.

Michael Lampis

CoRR, October, 2025

Structural Parameters for Steiner Orientation.

Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, Manolis Vasilakis

CoRR, July, 2025

Structural Parameterizations for Induced and Acyclic Matching.

Michael Lampis, Manolis Vasilakis

CoRR, February, 2025

On the Tractability Landscape of the Conditional Minisum Approval Voting Rule.

Georgios Amanatidis, Michael Lampis, Evangelos Markakis, Georgios Papasotiropoulos

Inf. Process. Lett., 2025

The Primal Pathwidth SETH.

Michael Lampis

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Parameterized Spanning Tree Congestion.

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

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Broadcasting Under Structural Restrictions.

Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, Daniel Vaz

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Satisfactory Budget Division.

Laurent Gourvès, Michael Lampis, Nikolaos Melissinos, Aris Pagourtzis

Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, 2025

2024

Circuits and Backdoors: Five Shades of the SETH.

Michael Lampis

CoRR, 2024

Parameterized Maximum Node-Disjoint Paths.

Michael Lampis, Manolis Vasilakis

CoRR, 2024

Faster Winner Determination Algorithms for (Colored) Arc Kayles.

Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono, Kanae Yoshiwatari

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

Parameterized Vertex Integrity Revisited.

Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, Kanae Yoshiwatari

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Core Stability in Additively Separable Hedonic Games of Low Treewidth.

Tesshu Hanaka, Noleen Köhler, Michael Lampis

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs.

Andreas Emil Feldmann, Michael Lampis

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Parameterized Max Min Feedback Vertex Set.

Michael Lampis, Nikolaos Melissinos, Manolis Vasilakis

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

First Order Logic on Pathwidth Revisited Again.

Michael Lampis

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Structural Parameterizations for Two Bounded Degree Problems Revisited.

Michael Lampis, Manolis Vasilakis

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Determining a Slater Winner Is Complete for Parallel Access to NP.

Michael Lampis

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Hedonic Games and Treewidth Revisited.

Tesshu Hanaka, Michael Lampis

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Structural Graph Parameters, Fine-Grained Complexity, and Approximation.

Michael Lampis

, 2022

2021

Digraph Coloring and Distance to Acyclicity.

Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Fine-Grained Meta-Theorems for Vertex Integrity.

Michael Lampis, Valia Mitsou

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Filling Crosswords Is Very Hard.

Laurent Gourvès, Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Minimum Stable Cut and Treewidth.

Michael Lampis

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-exponential Approximation.

Louis Dublois, Michael Lampis, Vangelis Th. Paschos

Proceedings of the Algorithms and Complexity - 12th International Conference, 2021

2020

<i>K</i>₃ Edge Cover Problem in a Wide Sense.

Kyohei Chiba, Rémy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, Yota Otachi

J. Inf. Process., 2020

New Algorithms for Mixed Dominating Set.

Louis Dublois, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Parameterized Complexity of (A, ℓ )-Path Packing.

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

Proceedings of the Combinatorial Algorithms - 31st International Workshop, 2020

(In)approximability of Maximum Minimal FVS.

Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, Nikolaos Melissinos

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Grundy Distinguishes Treewidth from Pathwidth.

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Maximum Independent Sets in Subcubic Graphs: New Results.

Ararat Harutyunyan, Michael Lampis, Vadim V. Lozin, Jérôme Monnot

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Independent Set Reconfiguration Parameterized by Modular-Width.

Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Improved (In-)Approximability Bounds for d-Scattered Set.

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

Proceedings of the Approximation and Online Algorithms - 17th International Workshop, 2019

Token Sliding on Split Graphs.

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Parameterized Complexity of Safe Set.

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018

The many facets of upper domination.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

Theor. Comput. Sci., 2018

Structurally Parameterized d-Scattered Set.

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Parameterized Orientable Deletion.

Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Multistage Matchings.

Evripidis Bampis, Bruno Escoffier, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Parameterized (Approximate) Defective Coloring.

Rémy Belmonte, Michael Lampis, Valia Mitsou

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

QBF as an Alternative to Courcelle's Theorem.

Michael Lampis, Stefan Mengel, Valia Mitsou

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

New Results on Directed Edge Dominating Set.

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, Michael Lampis

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Finer Tight Bounds for Coloring on Clique-Width.

Michael Lampis

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

How Bad is the Freedom to Flood-It?.

Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

Proceedings of the 9th International Conference on Fun with Algorithms, 2018

2017

Defective Coloring on Classes of Perfect Graphs.

Rémy Belmonte, Michael Lampis, Valia Mitsou

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Treewidth with a Quantifier Alternation Revisited.

Michael Lampis, Valia Mitsou

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

On the Parameterized Complexity of Red-Blue Points Separation.

Édouard Bonnet, Panos Giannopoulos, Michael Lampis

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Structural Parameters, Tight Bounds, and Approximation for (k, r)-Center.

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

2016

Parameterized Power Vertex Cover.

Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse.

Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Time-Approximation Trade-offs for Inapproximable Problems.

Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Upper Domination: Complexity and Approximation.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Algorithmic Aspects of Upper Domination: A Parameterised Perspective.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015

Algorithmic Aspects of Upper Domination.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

CoRR, 2015

Parameterized Algorithms for Parity Games.

Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Complexity and Approximability of Parameterized MAX-CSPs.

Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Mömke

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

2014

Guest column: the elusive inapproximability of the TSP.

Michael Lampis

SIGACT News, 2014

Parameterized Edge Hamiltonicity.

Michael Lampis, Kazuhisa Makino, Valia Mitsou, Yushi Uno

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

The Computational Complexity of the Game of Set and Its Theoretical Applications.

Michael Lampis, Valia Mitsou

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Parameterized Approximation Schemes Using Graph Widths.

Michael Lampis

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Review of exact exponential algorithms by Fedor V. Fomin and Dieter Kratsch.

Michael Lampis

SIGACT News, 2013

Closing a Gap in the Complexity of Refinement Modal Logic.

Antonis Achilleos, Michael Lampis

CoRR, 2013

Parameterized Algorithms for Modular-Width.

Jakub Gajarský, Michael Lampis, Sebastian Ordyniak

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

New Inapproximability Bounds for TSP.

Marek Karpinski, Michael Lampis, Richard Schmied

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Model Checking Lower Bounds for Simple Graphs.

Michael Lampis

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Local Improvement Gives Better Expanders

Michael Lampis

CoRR, 2012

Scrabble Is PSPACE-Complete.

Michael Lampis, Valia Mitsou, Karolina Soltys

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

Improved Inapproximability for TSP.

Michael Lampis

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Vertex Cover Problem Parameterized Above and Below Tight Bounds.

Gregory Z. Gutin, Eun Jung Kim, Michael Lampis, Valia Mitsou

Theory Comput. Syst., 2011

A kernel of order 2 k-c log k for vertex cover.

Michael Lampis

Inf. Process. Lett., 2011

Parameterized Maximum Path Coloring.

Michael Lampis

Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

2010

Parameterized Modal Satisfiability.

Antonis Achilleos, Michael Lampis, Valia Mitsou

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Algorithmic Meta-theorems for Restrictions of Treewidth.

Michael Lampis

Proceedings of the Algorithms, 2010

2009

Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover

Michael Lampis

CoRR, 2009

Ordered Coloring Grids and Related Graphs.

Amotz Bar-Noy, Panagiotis Cheilaris, Michael Lampis, Valia Mitsou, Stathis Zachos

Proceedings of the Structural Information and Communication Complexity, 2009

Online Maximum Directed Cut.

Amotz Bar-Noy, Michael Lampis

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures.

Michael Lampis, Georgia Kaouri, Valia Mitsou

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

The Ferry Cover Problem.

Michael Lampis, Valia Mitsou

Proceedings of the Fun with Algorithms, 4th International Conference, 2007

2006

Quantum Data and Control Made Easier.

Michael Lampis, Kyriakos G. Ginis, Michalis A. Papakyriakou, Nikolaos S. Papaspyrou

Proceedings of the 4th International Workshop on Quantum Programming Languages, 2006

Periodic Metro Scheduling.

Evangelos Bampas, Georgia Kaouri, Michael Lampis, Aris Pagourtzis

Proceedings of the 6th Workshop on Algorithmic Methods and Models for Optimization of Railways, 2006