Lemma 4.15 — a Hamiltonian cycle gives a TRVB solution of R_k(G)
ProvedTRVB.PlanarNPC.lemma_4_15complexity-theorygraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , let be a planar non-alternating directed graph (no loops, no repeated arcs) with every in- and out-degree equal to , let be any vertex and . If is a Hamiltonian cycle of , then the corresponding candidate solution is a solution of the TRVB instance : its vertices are breakable and breaking them leaves a tree.
Differences from the source:
- reading: R_k's input: a planar non-alternating graph G whose in- and out-degrees all equal 2 → hypothesis IsP43Instance A: arcs on Fin n, no loop, no repeated arc, every in- and out-degree 2, planar non-alternating; reason: Definition 4.8's input class, with 'graph' read as a directed graph without loops or repeated arcs as in Problem 4.3
- generalization: pick any specific vertex v̂ of G → the statement holds for every choice vhat : Fin n; reason: specializes to whichever v̂ the algorithm picks
- encoding: (u1, v), (u2, v) the edges into v, (v, w1), (v, w2) the edges out of v; M built, then m(v̂) removed and two edges added → in-arcs and out-arcs taken in arc-list order; rk lists M′'s edges directly (at v̂: two edges m(f1)–m(f2) and k−3+1 edges m(e1)–m(e2)); m(v) for v ≠ v̂ has index v or v−1, m(A[i]) has index n−1+i; reason: the order of u1/u2 and w1/w2 does not change the multigraph; the listed edges are exactly M′'s
- encoding: breaking vertices; the resulting multigraph is a tree → breakEnds re-attaches each edge end at a broken vertex to its own new vertex; IsTreeMG = nonempty, connected by walks, and no nonempty closed walk with pairwise distinct edges; reason: the paper's operation on edge ends (a loop at a broken vertex becomes an edge between two new vertices); a loop and two parallel edges are cycles; the empty multigraph is not a tree
- encoding: Hamiltonian cycle → IsHamCycle: a nonempty vertex set and a set C of arcs with exactly one C-arc out of and one into every vertex, every vertex reaching every vertex along C; IsHamiltonian asserts existence of such a cycle; reason: the standard notion; on one vertex it is a loop, on two vertices a pair of opposite arcs
Preamble
import Definitions.Def_TRVB_PlanarNPC_Rk set_option autoImplicit false
Formal statement
namespace TRVB.PlanarNPC
/-- Lemma 4.15 (p. 16): breaking `m(e)` for the arcs `e` off a Hamiltonian cycle solves `M′`. -/
theorem lemma_4_15 (k : ℕ) (hk : 4 ≤ k) (n : ℕ) (A : List (Fin n × Fin n))
(hA : IsP43Instance A) (vhat : Fin n) (C : Finset (Fin A.length)) (hC : IsHamCycle A C) :
IsSolution (rk k n A vhat)
((Finset.univ.filter (fun i => i ∉ C)).image (rkArcVertex k n A vhat)) := by sorry
end TRVB.PlanarNPC
Source
Demaine & Rudoy, Tree-Residue Vertex-Breaking: a new tool for proving hardness, arXiv:1706.07900v3 (3 May 2018; SWAT 2018, doi:10.4230/LIPIcs.SWAT.2018.32), Lemma 4.15, p. 16 (PDF p. 16). Verbatim: 'Lemma 4.15. Suppose Rk outputs M′ on input G and there exists a Hamiltonian cycle in G. Then the corresponding candidate solution of the TRVB instance M′ is a solution.' PDF SHA-256: d5f076af211e597d517c4365b4401ca0a6341590adb0a62be78489b9e737fcd7.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.