13 citations · 46 across the 31 of their papers we have counts for
22 papers · 1 filter
The Primal Pathwidth SETH
Michael Lampis
Motivated by the importance of dynamic programming (DP) in parameterized complexity, we consider several fine-grained questions, such as the following examples: (i) can Dominating…
Filling Crosswords is Very Hard
Laurent Gourvès, Ararat Harutyunyan, Michael Lampis +1
We revisit a classical crossword filling puzzle which already appeared in Garey\&Jonhson's book. We are given a grid with vertical and horizontal slots and a dictionary with $m…
Fine-grained Meta-Theorems for Vertex Integrity
Michael Lampis, Valia Mitsou
Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a struc…
Minimum Stable Cut and Treewidth
Michael Lampis
A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem…
Determining a Slater Winner is Complete for Parallel Access to NP
Michael Lampis
We consider the complexity of deciding the winner of an election under the Slater rule. In this setting we are given a tournament , where the vertices of V represent ca…
Digraph Coloring and Distance to Acyclicity
Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos
In -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most sets, so that each set induces a DAG. This well-known problem is NP-hard, as…