A Comparative Analysis of Backbone Algorithms for Configurable Software Systems Authors: Luis Cambelo, Ruben Heradio, Jose M. Horcas, Dictino Chaos, David Fernandez-Amoros Venue: SoSyM (Software and Systems Modeling), Springer Nature This repository provides the dataset utilized in the paper "A Comparative Analysis of Backbone Algorithms for Configurable Software Systems." The paper offers the first comprehensive empirical evaluation of backbone computation algorithms applied to formulas derived from real-world variability models (VMs). Additionally, the repository contains the R code used for dataset analysis. Dataset (/dataset) The dataset contains 2,371 DIMACS CNF files representing feature models from multiple domains.t processing | File Format All files use the DIMACS CNF format: c Comments mapping feature names to variable indices c Feature "WiFi" corresponds to variable 42 p cnf 1 -2 3 0 -1 2 0 ... Header: p cnf Comments: Lines starting with c provide feature-to-variable mappings Clauses: Space-separated literals (positive/negative integers) ending with 0 Naming Convention Files follow the pattern: {domain}-{system_name}-{source_citation}.dimacs Examples: security-CVE-VarelaVaca2020-2002-2436.dimacs (309 variables, 13,929 clauses) automotive-automotive01-Kowal2016.dimacs (2,513 variables, 10,300 clauses) finance-bank-AlHajjaji2019.dimacs (176 variables, 280 clauses) systems_software-linux-She2010.dimacs (6,888 variables, 343,944 clauses) Results (/results) CSV Files 1. backbone_time.csv (1,287,453 rows) Raw execution time measurements for all solver runs. Columns: model: Feature model identifier config_id: Configuration identifier (C01-C21) solver: Solver name (IPASIRBones_MiniSat, IPASIRBones_CaDiCaL, MiniBones, CadiBack) chunk_size: k parameter for MiniBones configurations (NA for non-MiniBones) seconds: Execution time Note: Contains multiple runs per (model, config, chunk_size) combination for statistical reliability. 2. models_info.csv (2,371 rows) Feature model characteristics—one row per dataset model. Columns: model: Feature model identifier num_variables: Number of Boolean variables num_clauses: Total number of clauses num_clauses_with_more_than_two_literals: Clauses with >2 literals median_clause_size: Median literals per clause mad_clause_size: Median absolute deviation of clause size num_core: Number of core features (always selected) num_dead: Number of dead features (never selected) num_backbone: Total backbone variables (core + dead) 3. command_arguments.csv (20 rows) Solver configuration specifications. Columns: config_id: Configuration identifier (C01-C21) solver: Solver executable name command_arguments: Command-line arguments used Key Configurations: C01: IPASIRBones with MiniSat (Alg. 1 — naive iterative) C02-C07: IPASIRBones / MiniBones / CadiBack variants (Alg. 2/3 — iterative with solution filtering) C08-C14: MiniBones / CadiBack variants (Alg. 4 — chunked all-in) C15-C20: MiniBones / CadiBack variants (Alg. 5 — chunked all-out / core-based) C21: EDUCIBone (Alg. 2/3 with COV, WHIT, and 2LEN filtering) 4. median_time_and_models_tb.csv (429,143 rows) Pre-computed median aggregations for faster analysis. Purpose: Combines median execution times with model characteristics, grouped by (model, config_id, chunk_size). Auto-generated by the analysis pipeline and cached for subsequent runs. Figures Directory (/results/figures) 1,284 high-resolution PNG files (600-700 DPI) organized into several categories: Pairwise Configuration Comparisons (1,261 files) Format: pair_plot_C{i}_C{j}__best_ks{_small_models|_large_models}.png Content: Scatter plots showing percentage time reduction vs. number of variables Wilcoxon signed-rank test statistics (p-values, effect sizes) Three variants: all models, small models (≤1,000 vars), large models (>1,000 vars) Example: pair_plot_C01_C08__best_ks.png compares IPASIRBones_MiniSat (C01) against MiniBones with optimal k (C08). K Parameter Analysis (16 files) best_k_vs_num_vars_C{id}.png: Correlation between optimal k and model size (variables) best_k_vs_num_clauses_C{id}.png: Correlation between optimal k and clause count chunk_size_density_C{id}.png: Distribution of best k values Insight: These plots demonstrate the difficulty of selecting optimal k parameters a priori. Configuration Performance Rankings (2 files) best_confs__small_models.png: Win percentage for configurations on small models best_confs__large_models.png: Win percentage for configurations on large models Shows which configurations achieve the fastest execution time most frequently. Dataset Characterization (1 file) nclauses_vs_nvars.png: Scatter plot of variables vs. clauses with marginal density plots Visualizes the size distribution and relationship between model dimensions. Time-K Relationship Examples (4 files) time_vs_k_C{id}_{model_examples}.png: Execution time as a function of k for selected models Demonstrates how performance varies with the k parameter on specific instances. Replicating the Analysis Prerequisites R: Version 3.6 or higher Packages: Auto-installed by the script tidyverse, hrbrthemes, scales, patchwork, ggpubr, ggExtra, pgirmess Running the Analysis cd /mnt/backbone/zenodo/analysis_code Rscript main.R Analysis Workflow The main.R script executes the following steps: Load Dependencies (imports_and_constants.R) Installs missing packages automatically Sets plotting theme and constants Sources analysis modules Load and Aggregate Data (read_data.R) Reads raw CSV files from ../results/ Computes median execution times grouped by (model, config_id, chunk_size) Caches results to median_time_and_models_tb.csv Generate MiniBones Variants (minibones_ks.R) Best-k: Optimal k per model (C08, C09, C11, C12, C14, C15, C17, C18) Median-k: Median of best k values across models Default k=100: Standard MiniBones configuration Statistical Analysis (get_inferential_stats.R) Wilcoxon signed-rank tests for pairwise comparisons Kruskal-Wallis tests with post-hoc analysis for multiple configurations Effect size calculations Generate Visualizations (get_plots.R) 1,261 pairwise comparison plots (all models, small, large) K parameter correlation and density plots Configuration ranking charts Dataset characterization plots Expected Outputs Figures: All 1,284 PNG files regenerated in results/figures/ Console Output: Statistical summaries (xtable format for LaTeX) Cache File: Updated results/median_time_and_models_tb.csv Repository Structure /mnt/backbone/zenodo/ ├── README.md # This file ├── dataset/ # 2,371 DIMACS feature models │ ├── automotive-automotive01-Kowal2016.dimacs │ ├── security-CVE-VarelaVaca2020-2002-2436.dimacs │ ├── systems_software-linux-She2010.dimacs │ ├── finance-bank-AlHajjaji2019.dimacs │ └── ... ├── results/ # Analysis outputs │ ├── backbone_time.csv # Raw execution times (1.2M rows) │ ├── models_info.csv # Model characteristics (2,371 rows) │ ├── command_arguments.csv # Configuration specs (20 rows) │ ├── median_time_and_models_tb.csv # Cached aggregations (429K rows) │ └── figures/ # 1,284 analysis plots (PNG, 600-700 DPI) │ ├── pair_plot_C01_C02__best_ks.png │ ├── pair_plot_C01_C02__best_ks_small_models.png │ ├── best_k_vs_num_vars_C08.png │ ├── best_confs__small_models.png │ ├── nclauses_vs_nvars.png │ └── ... └── analysis_code/ # R analysis pipeline ├── main.R # Master script ├── imports_and_constants.R # Dependencies and setup ├── read_data.R # Data loading/caching ├── get_plots.R # Visualization functions ├── get_inferential_stats.R # Statistical tests ├── minibones_ks.R # K parameter analysis └── CLAUDE.md # Developer documentation Research Questions and Findings The paper investigates 8 research questions: Q1: Are formulas obtained from VMs different from those used in SAT competitions? Yes, they are. VM formulas are structurally distinct: they have fewer variables (median 356 vs. 13,408), many more clauses per variable (39.84 vs. 5.46 clauses/variable ratio), and much simpler clauses — about 98% of clauses contain at most two literals, compared to 61% with more than two literals in SAT competition formulas. Q2: Is Alg. 2/3 faster than Alg. 1? Yes, it is. Alg. 2/3 (iterative with solution filtering) is consistently faster than Alg. 1 (naive iterative) across the entire dataset, with a statistically significant difference and large effect size. Q3: Are there faster algorithms than Alg. 1 or Alg. 2/3? Yes, there are. Alg. 2/3 is the fastest for formulas with 1,000 or fewer variables. For formulas with more than 1,000 variables, Alg. 5 (chunked core-based) demonstrates superior performance. With optimal chunk size k, Alg. 5 can achieve runtime reductions exceeding 50%. CadiBack's adaptive k selection provides the best practical performance for large formulas. Q4: Is it possible to infer the optimal k for Algs. 4 and 5? No, it is not. The optimal k varies unpredictably across formulas and shows only weak correlation with the number of variables or clauses (Spearman's rho < 0.2). Neither the number of variables nor the number of clauses are effective predictors. The distribution of optimal k values is too scattered for centrality measures (like the median) to improve over default settings. Q5: Does UC injection influence performance? No, it does not. Injecting backbone literals as unit clauses showed no influence (neither positive nor negative) across all tested algorithm and configuration pairs. Q6: Does TIP influence performance? Yes, it does, but only when combined with RL filtering in Alg. 2/3. In all other cases, TIP has no measurable effect. Q7: Does literal filtering with RLs influence performance? No, it does not. Filtering with rotatable literals showed no influence (neither positive nor negative) across all algorithm configurations. Q8: Does combined filtering (COV, WHIT, 2LEN) influence performance? Yes, it does, but quite negatively. The combined application of COV, WHIT, and 2LEN has a statistically significant and substantial negative effect on Alg. 2/3 performance. Citation If you use this dataset or analysis in your research, please cite: Luis Cambelo, Ruben Heradio, Jose M. Horcas, Dictino Chaos, David Fernandez-Amoros. "A Comparative Analysis of Backbone Algorithms for Configurable Software Systems." Software and Systems Modeling (SoSyM), Springer Nature, 2025. Funding This work is funded by FEDER/Spanish Ministry of Science, Innovation and Universities (MCIN)/Agencia Estatal de Investigacion (AEI) under grant COSY (PID2022-142043NB-I00). License MIT Contact Luis Cambelo — Universidad Nacional de Educacion a Distancia (UNED) — lcambelo1@alumno.uned.es Ruben Heradio — Universidad Nacional de Educacion a Distancia (UNED) — rheradio@issi.uned.es Jose M. Horcas — Universidad de Malaga — horcas@uma.es Dictino Chaos — Universidad Nacional de Educacion a Distancia (UNED) — dchaos@dia.uned.es David Fernandez-Amoros — Universidad Nacional de Educacion a Distancia (UNED) — david@issi.uned.es