Parameterized Complexity of Synchronization and Road Coloring
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10319646" target="_blank" >RIV/00216208:11320/15:10319646 - isvavai.cz</a>
Result on the web
<a href="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2685" target="_blank" >http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2685</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Parameterized Complexity of Synchronization and Road Coloring
Original language description
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 unlessthe 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 ofstates, 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-10799S" target="_blank" >GA14-10799S: Hybercubic, graph and hypergraph structures</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discrete Mathematics and Theoretical Computer Science
ISSN
1462-7264
e-ISSN
—
Volume of the periodical
17
Issue of the periodical within the volume
1
Country of publishing house
FR - FRANCE
Number of pages
23
Pages from-to
283-305
UT code for WoS article
000365862100002
EID of the result in the Scopus database
2-s2.0-84928378825