Preprint
Oct 2026
W[1]-Hardness of Upper Clique Transversal
A clique transversal of a graph is a set of vertices intersecting every maximal clique. We prove that deciding whether a graph has an inclusion-wise minimal clique transversal of size at least $k$ is W[1]-hard when parameterized by $k$.
Pascal Gollin, Tesshu Hanaka, Ekkehard Köhler et al.
· 0 citations