A connected graph has a ( k , ℓ ) -cover if each of its edges is contained in at least ℓ cliques of order k . Motivated by recent advances in extremal combinatorics and the literature on edge modification problems, we study the algorithmic version of the ( k , ℓ ) -cover problem. Given a connected graph G , the ( k , ℓ ) -cover problem is to identify the smallest subset of non-edges of G such that their addition to G results in a graph with a ( k , ℓ ) -cover. For every constant k ≥ 3 , we show that the ( k , 1 ) -cover problem is NP -complete for general graphs. Moreover, we show that for every constant k ≥ 3 , the ( k , 1 ) -cover problem admits no polynomial-time constant-factor approximation algorithm unless P = NP . However, we show that the ( 3 , 1 ) -cover problem can be solved in polynomial time when the input graph is chordal. For the class of trees and general values of k , we show that the ( k , 1 ) -cover problem is NP -hard even for spiders. However, we show that for every k ≥ 4 , the ( 3 , k − 2 ) -cover and the ( k , 1 ) -cover problems are constant-factor approximable when the input graph is a tree.

Particle swarm optimization (PSO) has been adapted to solve multi-objective optimization problems. However, these PSO-based multi-objective optimization algorithms typically face difficulties when the number of decision variables is increased and the problems turn into large-scale multi-objective problems (LSMOPs). This paper presents a decision space scalability analysis of five PSO-based multi-objective optimization algorithms, namely optimized multi-objective particle swarm op-timization (OMOPSO), speed-constrained multi-objective particle swarm optimization (SMPSO), multi-objective particle swarm optimization with multiple search strategies (MMOPSO), multi-guide particle swarm optimization (MGPSO), and competitive mechanism-based multi-objective particle swarm optimization (CMOPSO) for 24, 50, 100, 500 and 1000 dimensions (decision variables) to see how well each one of the algorithms scales as the number of decision variables is increased. The results indicate that, with an increase in the number of decision variables, MMOPSO and SMPSO had the best scalability, each dominating specific functions. Moreover, despite MGPSO's competitive performance on the 24-dimensional functions, it showed the worst overall scalability together with CMOPSO.