The automated analysis of feature models (FM) is based on SAT, BDD, and CSP - known NP-complete problems. Therefore, the analysis could have an exponential worst-case execution time. However, for many practical relevant analysis cases, state-of-the-art (SOTA) analysis tools quite successfully master the problem of exponential worst-case execution time based on heuristics. So far, however, very little is known about the structure of FMs that cause the cases in which the execution time (hardness) for analyzing a given FM increases unpredictably for SOTA analysis tools. In this paper, we propose to use width measures from graph theory to characterize the structural complexity of FMs as a basis for an estimation of the hardness of analysis operations on FMs with SOTA analysis tools. We present an experiment that we use to analyze the reasonability of graph width measures as metric for the structural complexity of FMs and the hardness of FM analysis. Such a complexity metric can be used as a basis for a unified method to systematically improve SOTA analysis tools.

The formalization of variability models (e.g. feature models) is a prerequisite for the automated analysis of these models. The efficient execution of the analysis operations depends on the selection of well-suited solver implementations. Regarding feature models, on the one hand, the formalization with Boolean expressions enables the use of SAT or BDD solvers. On the other hand, feature models can be transformed into a Constraint-Satisfaction Problem (CSP) in order to use CSP solvers for validation. This paper presents a performance comparison regarding nine contemporary high-performance solvers, three for each base problem structure (BDD, CSP, and SAT). Four operations on 90 feature models are run on each solver. The results will in turn clear the way for new improvements regarding the automatic verification of software product lines, since the efficient execution of analysis operations is essential to such automatic verification approaches.