The RegularGcc Matrix Constraint

Ronald de Haan¹, Nina Narodytska², and Toby Walsh²

¹Technische Universität Wien, Austria
dehaan.ronald@gmail.com

²NICTA and University of NSW, Sydney, Australia
nina.narodytska@nicta.com.au
toby.walsh@nicta.com.au

Abstract. We study propagation of a global constraint that ensures that each row of a matrix of decision variables satisfies a Regular constraint, and each column satisfies a Gcc constraint. On the negative side, we prove that propagation is NP-hard even under some strong restrictions (e.g. just 2 values, just 4 states in the automaton, just 5 columns to the matrix, or restricting to limited classes of automata). We also prove that propagation is W[2]-hard when the problem is parameterized by the number of rows in the matrix. On the positive side, we identify several cases where propagation is fixed parameter tractable.

LNAI 7691, p. 206 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012