arXiv preprint ·
W[1]-Hardness of Upper Clique Transversal
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs
New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids
Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.