Skip to content
  1. CLRS-Lean
  2. Chapter 34. NP-Completeness
  3. 34.5. NP-Complete Problems
  4. 34.5. VERTEX-COVER
  5. 34.5. Complement-Machine Components
  6. 34.5. VERTEX-COVER complement machine: canonical vertex-pair stream
  7. 34.5. VERTEX-COVER pair stream: graph-to-range-certificate machine
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_5_NP_Complete_Problems.VertexCover.ComplementMachine.PairStream.RangeCertificate.Runtime

VERTEX-COVER pair stream: graph-to-range-certificate machine

A fixed polynomial-time TM2 extracts the unary vertex bound from a canonical graph and emits the exact certificate [0, ..., |V| - 1] consumed by the reused general-CLIQUE pair generator.