Theorem 2.8, (⇒) — a vertex cover gives a completion
ProvedCallCountPOPBR.theorem_2_8_forwardaddition-sequencescomputational-complexitynp-completenessp2o-gran-per-chapterp2o-plan-paperp2o-v1recursion
Let be a simple graph on vertices with edges and let . If has a vertex cover of size at most , then is a yes-instance of POPBR.
This is the completeness half of the reduction.
Differences from the source:
- encoding: V = {1, …, n} and a_v = sv → vertices 0, …, n − 1 of NPGraph.Graph with a_v = s(v + 1); reason: the published graph type numbers vertices from 0; the exponents are the same numbers s, 2s, …, ns
Preamble
import Definitions.Def_CallCountPOPBR_reductionInstance import Definitions.Def_CallCountPOPBR_Instance_IsYes import Definitions.Def_CallCountPOPBR_HasVertexCover set_option autoImplicit false
Formal statement
namespace CallCountPOPBR
/-- **Theorem 2.8, (⇒): a cover gives a completion.** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), proof of Theorem 2.8, (⇒), p.6:
"Let C ⊆ V be a vertex cover with |C| ≤ K (so C ≠ ∅ as E ≠ ∅). The chain block is realised by
E_d = 1 + 1 and E = 2 · E_previous. For k = 1, …, K pick v_k ∈ C (repeating vertices if
|C| < K) and set the k-th free node to F_k = 2^{a_{v_k}} + 2^{a_z}, a sum of two chain values. For
an edge e = {i, j} choose an endpoint v ∈ C ∩ e and let w be the other endpoint; then
T_e = F_v + 2^{a_w} with F_v a free node and 2^{a_w} a chain value."
For every simple graph with at least one edge and every `1 ≤ K ≤ n − 1`, if `G` has a vertex
cover of size at most `K` then `I(G, K)` is a yes-instance. -/
theorem theorem_2_8_forward (G : NPGraph.Graph) (K : ℕ) (hG : NPGraph.IsSimple G)
(hm : 1 ≤ numEdges G) (hK : 1 ≤ K) (hKn : K + 1 ≤ G.order) :
HasVertexCover G K → (reductionInstance G K).IsYes := by sorry
end CallCountPOPBR
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884dd262e4297079b8d2f7adb5deec1b329582779ed16decf34adae2411), proof of Theorem 2.8, (⇒), p.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.