Even if bigram features are dependent on x, it is still possible to compute better bounds if several features are mutually exclusive, as discussed in (Esposito and Radicioni, 2009).
most of the exact algorithms, including ours, do not require such a manual effort.