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
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_5_NP_Complete_Problems.VertexCover.ComplementMachine.PairStream.Runtime

VERTEX-COVER complement machine: canonical vertex-pair stream

The semantic layer identifies the reused general-CLIQUE positional-pair generator with the exact normalized-pair sequence used by the complement map. The range-certificate layer supplies its canonical [0, ..., |V| - 1] input directly from the graph encoding with a fixed polynomial-time TM2. Their composition computes the exact canonical pair stream from the original graph.