The NP-hard 2-C_(LUB) problem is, given an undirected graph G = (V, E) and a positive integer e, to decide whether there is a vertex set of size at least e that induces a subgraph of diameter at most two. We make progress towards a systematic classification of the complexity of 2-C_(LUB) with respect to structural parameterizations of the input graph. Specifically, we show NP-hardness of 2-C_(LUB) on graphs that become bipartite by deleting one vertex, on graphs that can be covered by three cliques, and on graphs with domination number two and diameter three. Moreover, we present an algorithm that solves 2-C_(LUB) in |V|~(f(k)) time, where k is the so-called h-index of the input graph. By showing W[1]-hardness for this parameter, we provide evidence that the above algorithm cannot be improved to a fixed-parameter algorithm. This also implies W[1]-hardness with respect to the degeneracy of the input graph. Finally, we show that 2-C_(LUB) is fixed-parameter tractable with respect to "distance to co-cluster graphs" and "distance to cluster graphs".
展开▼
