![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
Source : ScholeXplorer
IsRelatedTo ARXIV 1412.0799 Source : ScholeXplorer IsRelatedTo DOI 10.1007/978-3-319-15579-1_12 Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.jcss.2016.05.009 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1412.0799
|