While this submission is a draft, it cannot be used by other submissions.

Proof of `Structural Parameters of the Conflict Graph` (1st statement)

groundedproofs/Lax117284Proofs/Theorem4_ClientsReduction.lean · lax-117284

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The reduction is the map that sends the word of an instance with nn clients, mm days and parameter kk to the word of the integer program of Theorem 21 of the source (zListzList): one variable per pair of a type of day (a conflict relation on the clients) and a set of clients, which says how many days of that type serve exactly that set, one slack variable per client, one constraint per type fixing the number of days of the type, and one per client saying the days it is not served on are at most m−km - k; 2(n2+n)+n2 ^ (n² + n) + n variables in all, a function of nn alone. When k>mk > m and there is a client the answer is nono outright, and the map sends the word to the fixed infeasible program 0⋅x=10 · x = 1. The program is computed by a word RAM program that reads the word, tests these two conditions, builds the word of the integer program in an array by the same program as fptbyClientsfpt_byClients and prints it; without a client it prints the program 1⋅x=m1 · x = m directly, which is the integer program of the instance and whose cost does not depend on mm. Its cost is 24∣x∣24 |x| plus a polynomial in the size of the integer program times ∣x∣|x|, which is within c⋅g(n)⋅(∣x∣+1)cc · g(n) · (|x| + 1)^c; its values are bounded by the lengths and largest entries of the word and of its image, which fit into the word length by the fitting conditions on both. Correctness is the equivalence of the integer program with the existence of a kk-fair schedule (zListfeasibleiffzList_feasible_iff), which holds when k≤mk ≤ m or there is no client.