Hall's Condition for Partial Latin Squares

2011/07/13 by Hilton, A. J. W., Vaughan, E. R.
#05B15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1107.2639

Abstract

Hall's Condition is a necessary condition for a partial latin square to be completable. Hilton and Johnson showed that for a partial latin square whose filled cells form a rectangle, Hall's Condition is equivalent to Ryser's Condition, which is a necessary and sufficient condition for completability. We give what could be regarded as an extension of Ryser's Theorem, by showing that for a partial latin square whose filled cells form a rectangle, where there is at most one empty cell in each column of the rectangle, Hall's Condition is a necessary and sufficient condition for completability. It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard.

Related

• Completing Partial Latin Squares - Alternative Proof
• An analogue of Ryser's Theorem for partial Sudoku squares
• Completing partial Latin squares with two filled rows and three filled columns
• Completions of epsilon-dense partial Latin squares
• Another proof of Cruse's theorem and a new necessary condition for completion of partial Latin squares (Part 3.)