2024/08/15 by Abu-Khzam, Faisal N., Isenmann, Lucas
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2408.08418
The s-club cluster vertex deletion number of a graph, or sccvd, is the minimum number of vertices whose deletion results in a disjoint union of s-clubs, or graphs whose diameter is bounded above by s. We launch a study of several domination problems on diameter-two graphs, or 2-clubs, and study their parameterized complexity with respect to the 2ccvd number as main parameter. We further propose to explore the class of problems that become solvable in sub-exponential time when the running time is independent of some input parameter. Hardness of problems for this class depends on the Exponential-Time Hypothesis. We give examples of problems that are in the proposed class and problems that are hard for it.