Lemma 3.3 — all induced list subinstances in deterministic time
OpenKColoringFaster.ListBootstrap.Supplement.lemma_3_3Fix a finite palette . There is a deterministic algorithm that, given a list-coloring instance on vertices with for every vertex, determines simultaneously, for every , whether the induced subinstance (with the lists restricted to ) is list colorable, in time
The output is the full table of the answers, one per subset , in the fixed order in which subset has index .
This is the list-coloring extension of the result of Björklund, Husfeldt, Kaski and Koivisto that all -colorable induced subgraphs are found in time. In the paper it is the subroutine of the binary-list interpolation algorithm of Theorem 4.4.
Formalization Note The program and polynomials may depend on (the palette is fixed first) but not on the instance. "Time " means a coin-free run of cost at most with registers of at most bits, the input bit size.
Differences from the source:
- reading: "one can determine … in O*(2^{|V(G)|}) time" (randomness not mentioned) → a deterministic algorithm; reason: the statement names no randomness, its proof is deterministic and Theorem 4.4 uses it deterministically; this is the stronger reading
- encoding: "determine simultaneously, for every X ⊆ V(G)" → the output is the 0/1 table indexed by the binary code of X; reason: a fixed output format for the same information
- encoding: O*(·) running time → one coin-free program of the integer RAM with cost at most ⌈p(σ)·2^n⌉ and registers of at most q(σ) bits; reason: unit cost with polynomially bounded registers equals bit cost up to polynomial factors
- encoding: colors of an abstract palette P → P a finite set of natural numbers; reason: any finite palette is numbered
- encoding: vertex set V(G) → Fin n; reason: any n-vertex graph is relabeled by 0, …, n − 1
- generalization: nonempty lists → lists may be empty; reason: a vertex with an empty list makes exactly the subsets containing it uncolorable, and the source's instances are included
import Mathlib import Definitions.Def_KColoringFaster_ListBootstrap_Instances import Definitions.Def_KColoringFaster_ListBootstrap_Supplement_DetTime open Classical
namespace KColoringFaster.ListBootstrap.Supplement
open KColoringFaster.ListBootstrap
/-- Lemma 3.3, p. 9 (All induced list subinstances). Fix a palette `P`. One deterministic algorithm
computes, for a list instance on `G` with all lists contained in `P`, the whole table of which
induced subinstances `G[X]`, `X ⊆ V(G)`, are list colorable, in time `O*(2^{|V(G)|})`. -/
theorem lemma_3_3 (P : Finset ℕ) :
DetComputes encList (OverPalette P) (fun I out => out = encSubsetTable I)
(fun I => (2 : ℝ) ^ I.n) := by sorry
end KColoringFaster.ListBootstrap.Supplement