# Backbone

$LaTeX: \{j : x_j = 1 \mbox{ for all } x \in X^* \},$
where $LaTeX: x$ is a vector of binary variables in the IP formulation and $LaTeX: X^*$ is usually the optimality region, although it could allow some ball around the objective value. Some results suggest that the difficulty of an NP-hard problem can be further analyzed by the size of itsbackbone.