Skip to Main content Skip to Navigation
Journal articles

Parameterized complexity of synchronization and road coloring

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196846
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2015 - 3:17:06 PM
Last modification on : Tuesday, December 7, 2021 - 3:33:14 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:08:57 AM

File

dmtcs-17-1-18.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Vojtěch Vorel, Adam Roman. Parameterized complexity of synchronization and road coloring. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (1), pp.283--305. ⟨10.46298/dmtcs.2103⟩. ⟨hal-01196846⟩

Share

Metrics

Record views

51

Files downloads

704