NP Optimization Lab v9 Full — Eight Reductions + Exact Search

NP Optimization Lab v9 Full<br>Eight NP views + Brute Force / Branch & Bound — reductions, search, certificates

Rand 3vRand 4vRand 5vRand 6vRand 8v

CNF syntax: clauses joined by ∧ or &, literals joined by ∨ or |, negation ¬ or !. Maximum 20 variables.

SAT Decision<br>MaxSAT Optimization

Brute Force<br>Branch & Bound

Λ STRUCTURAL LOAD

SOLUTION COMPRESSION

SOLUTION-SPACE PHASE

Λ·P ≤ C = ln(10)

⏯ Step<br>▶ Auto<br>⏹ Stop<br>↺ Reset

SEARCH TREE — ● visited × pruned ● incumbent ● optimum

VISITED NODES

EVALUATED ASSIGN.

PRUNED ASSIGN.

INCUMBENT

BRUTE FORCE<br>complete assignments evaluated

BRANCH & BOUND<br>complete assignments evaluated

① MaxSAT / SAT

VARIABLES

CLAUSES — green: SAT, amber: OPEN, red: DEAD

Exact reduction. Create one vertex for every literal occurrence. Join vertices from different clauses unless they are contradictory. One true literal chosen from each currently satisfied clause forms a clique; the same vertices form an independent set in the complement; all remaining vertices form a vertex cover. Thus OPTMaxSAT = ω(G) = α(Ḡ), and τ(Ḡ) = |V| − OPTMaxSAT.

② Clique③ Independent Set④ Vertex Cover⑤ 3-Coloring⑥ Hamiltonian Cycle⑦ Subset Sum⑧ Knapsack

② MAX CLIQUE

③ MAX INDEPENDENT SET

④ MIN VERTEX COVER

⑤ VERTEX 3-COLORING

T colorF colorB color

⑥ DIRECTED HAMILTONIAN CYCLE

⑦ EXACT SUBSET SUM

Variable items choose T/F once. Clause slack items complete every satisfied clause digit to the exact target; an unsatisfied clause cannot reach the target.

⑧ 0/1 KNAPSACK

Subset Sum → Knapsack: every item has weight = value, capacity = target T, required value = T. Feasibility forces exact equality.

Full chain. ①–④ share exact MaxSAT objective identities. ⑤ uses the standard T/F/B clause gadget for 3-CNF. ⑥ displays the directed variable-chain Hamiltonian certificate induced by the current assignment. ⑦–⑧ use an exact no-carry digit encoding with clause slack items.