Theorem 2.8, (⇐) — a completion gives a vertex cover
ProvedCallCountPOPBR.theorem_2_8_backwardaddition-sequencescomputational-complexitynp-completenessp2o-gran-per-chapterp2o-plan-paperp2o-v1recursion
Let be a simple graph on vertices with edges and let . If is a yes-instance of POPBR, then has a vertex cover of size at most .
This is the soundness 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 completion gives a cover.** 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.7:
"Now choose, for every free node F with V(F) ≠ ∅, a vertex φ(F) ∈ V(F) and let C = {φ(F)}; then
|C| ≤ K. For every edge e, Claim 3 gives a free node F with ∅ ≠ V(F) ⊆ e, so φ(F) ∈ e ∩ C. Hence
C is a vertex cover of size at most K."
For every simple graph with at least one edge and every `1 ≤ K ≤ n − 1`, if `I(G, K)` is a
yes-instance then `G` has a vertex cover of size at most `K`. -/
theorem theorem_2_8_backward (G : NPGraph.Graph) (K : ℕ) (hG : NPGraph.IsSimple G)
(hm : 1 ≤ numEdges G) (hK : 1 ≤ K) (hKn : K + 1 ≤ G.order) :
(reductionInstance G K).IsYes → HasVertexCover G K := 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.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.