An Efficient Algorithm for Combining Verification and Validation Methods

An adequate combination of verification and validation (V&V) methods is important to improve software quality control throughout the development process and to reduce costs. However, to find an appropriate set of V&V methods that properly addresses the desired quality characteristics of a given project is a NP-hard problem. In this paper, we present a novel approach that combines V&V methods efficiently in order to properly cover a set of quality characteristics. We modelled the problem using a bipartite graph to represent the relationships between V&V methods and quality characteristics. Then we interpreted our problem as the Set Cover problem. Although Set Cover is considered hard to be solved, through the theoretical framework of Parameterized Complexity we propose an FPT-Algorithm (fixed-parameter tractable algorithm) that effectively solves the problem, considering the number of quality characteristics to be covered as a fixed parameter. We conclude that the proposed algorithm enables combining V&V methods in a scalable and efficient way, representing a valuable contribution to the community.