Polynomial-Time Solution of Unique Latin Square Completion via Prime Debt Graphs and Exhaustive Cascade

Read full text Summarise with VIRAT
Authors: Teixeira, Joao
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We prove that any N ×N Latin square completion in-stance with a unique solution (M =1) can be solved in O(N 11) timewithout backtracking. The proof combines three tools. House poly-nomials encode row and column constraints so that candidate setsat each cell are the common roots of two polynomials; a parallelprime encoding gives the same sets via divisibility. The surplus ofcandidates beyond the correct value creates alternating cycles ineach house’s bipartite matching graph—locally feasible reassign-ments. Under M =1, the Cavenagh–Wanless trade impossibilitytheorem prevents these local alternatives from forming a globalLatin trade. This tension is captured by the prime debt graph,a DAG that traces the displacement from any wrong candidateto a terminal house violation. A three-layer composed operator(house-consistency closure, rectangle enumeration, single-variableconditioning) detects every such violation, guaranteeing that eachapplication eliminates wrong candidates.

Fields of Study & Subjects

Constraint Satisfaction and Optimization Advanced Graph Theory Research Advanced Combinatorial Mathematics

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
25 March 2026
Language
EN
Document type
Preprint