The NP-completeness of Completing Partial anti-symmetric Latin squares

摘要

This paper shows that deciding whether a partial anti-symmetric Latin square can be completed is NP complete. It imitates the proof of J.Colbourn [2] and exhibits a polynomial reduction from the known NP-complete problem which is called edge-colouring problem of regular graph.