50 citations · 125 across the 28 of their papers we have counts for
38 papers
Shellability is hard even for balls
Pavel Paták, Martin Tancer
The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary)…
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…
Parameterized complexity of untangling knots
Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer
Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized…
Weak saturation of multipartite hypergraphs
Denys Bulavka, Martin Tancer, Mykhaylo Tyomkyn
Given -uniform hypergraphs (-graphs) and , where is a spanning subgraph of , is called weakly -saturated in if the edges in ad…
Optimal bounds for the colorful fractional Helly theorem
Denys Bulavka, Afshin Goodarzi, Martin Tancer
The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: For every and every…
Barycentric cuts through a convex body
Zuzana Patáková, Martin Tancer, Uli Wagner
Let be a convex body in (i.e., a compact convex set with nonempty interior). Given a point in the interior of , a hyperplane passing through is ca…