Showing 2022Show all
3 papers · 1 filter
cs.CC2022
VEST is W[2]-hard
Michael Skotnica
In this short note, we show that the problem of VEST is -hard for parameter . This strengthens a result of Matoušek, who showed -hardness of that problem. The conseq…
cs.CG2022
NP-hardness of computing PL geometric category in dimension 2
Michael Skotnica, Martin Tancer
The PL geometric category of a polyhedron , denoted , provides a natural upper bound for the Lusternik--Schnirelmann category and it is defined as the minimum…
cs.DM2022
How Expressive Are Friendly School Partitions?
Josef Minařík, Shay Moran, Michael Skotnica
A natural procedure for assigning students to classes in the beginning of the school-year is to let each student write down a list of other students with whom she/he wants to b…