hide
Free keywords:
Clique relaxation; s-Club; NP-hard problem; Problem kernel; Polynomial-time preprocessing; Branching algorithm
Abstract:
Finding subgraphs of small diameter in undirected graphs has been seemingly unexplored from a parameterized complexity perspective. We perform the first parameterized complexity study on the corresponding NP-hard s-Club problem. We consider two parameters: the solution size and its dual.