Discrete Mathematics & Theoretical Computer Science, Vol 17, No 1 (2015)

Font Size:  Small  Medium  Large

Parameterized Complexity of Synchronization and Road Coloring

Vojtěch Vorel, Adam Roman

Abstract


First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.

Full Text: PDF PostScript