Summary
This paper looks at a puzzle about graphs, which are like networks of dots and lines. The puzzle is about finding a special group of dots that touches every big tightly connected group called cliques. The authors show that figuring out if such a group can be big is very hard in a technical sense, meaning no fast shortcuts are likely to exist. This helps us understand the limits of solving these kinds of network problems.
What this means in practice
- •For graph algorithm designers: Avoid seeking efficient solutions for large minimal clique transversals given size constraints due to proven computational hardness.
- •For complex networks analysts: Recognize that finding large minimal vertex sets touching maximal cliques is computationally intractable, guiding approach choices.
A theory result. No direct application yet.
Authors
Pascal J. Gollin, Tesshu Hanaka, Ekkehard Köhler, Martin Milanič, Yushi Uno
Abstract
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$.