Skip to main content

is_strong_backdoor_to_2sat

Function is_strong_backdoor_to_2sat 

Source
pub fn is_strong_backdoor_to_2sat(
    clauses: &[Vec<Lit>],
    num_vars: usize,
    backdoor: &[usize],
) -> bool
Expand description

Verify U is a strong backdoor to 2-SAT by enumeration: every one of the 2^{|U|} assignments to U yields a residual of width ≤ 2. Bounded to |U| ≤ 24 (the enumeration guard).