11 papers
Pure Nash Equilibria in Graphical Games of Bounded Width Revisited
Michael Lampis, Yiren Lu
We revisit the complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE) parameterized by standard measures of the input graph, such as treewidth. The na…
First Order Logic on Pathwidth Revisited Again
Michael Lampis
Courcelle's celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied b…
Parameterized Spanning Tree Congestion
Michael Lampis, Valia Mitsou, Edouard Nemery +3
In this paper we study the Spanning Tree Congestion problem, where we are given a graph and are asked to find a spanning tree of minimum maximum congestion. Here, the…
Parameterized Capacitated Vertex Cover Revisited
Michael Lampis, Manolis Vasilakis
Capacitated Vertex Cover is the hard-capacitated variant of Vertex Cover: given a graph, a capacity for every vertex, and an integer , the task is to select at most vertices…
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…
Parameterized Maximum Node-Disjoint Paths
Michael Lampis, Manolis Vasilakis
We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of Node-Disjoint Paths, where we are given a graph , pairs of vertices and…