On the complexity of the \(k\)-independence number and the \(h\)-diameter of a graph. (English) Zbl 07853385
Summary: The \(k\)-independence number of a graph, which extends the
classical independence number, is the maximum size of a set of vertices at pairwise distance greater than \(k\). The associated decision problem is known to be NP-complete for general graphs, and it is also known to remain NP-complete for regular bipartite graphs when \(k\in\{2,3,4\}\) and for planar bipartite graphs of maximum degree 3 for all \(k\ge 2\). We continue this line of research by showing that the problem remains NP-complete
when considering several other graph classes. Moreover, we establish a new connection between the \(k\)-independence number and the \(h\)-diameter, which is a natural generalization of the graph diameter. Finally, we use this new link to show the (parametrized) complexity of the decision problem associated to computing the \(h\)-diameter.
MSC:
05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
68Q27 | Parameterized complexity, tractability and kernelization |