A Timecop's Work Is Harder Than You Think
| Autor: | Morawietz, Nils, Rehs, Carolin, Weller, Mathias |
|---|---|
| Přispěvatelé: | Phillips-Universität Marburg, Heinrich Heine Universität Düsseldorf = Heinrich Heine University [Düsseldorf], Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Centre National de la Recherche Scientifique (CNRS), Philipps Universität Marburg = Philipps University of Marburg |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
060201 languages & linguistics
Theory of computation → Dynamic graph algorithms [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 06 humanities and the arts 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice edge-periodic temporal graphs cops and robbers Parameterized Algorithmics tally-intersection 0602 languages and literature 0202 electrical engineering electronic engineering information engineering Theory of computation → Parameterized complexity and exact algorithms 020201 artificial intelligence & image processing congruence satisfyability |
| Zdroj: | 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Aug 2020, Prague, Czech Republic. pp.71:1--71:14, ⟨10.4230/LIPIcs.MFCS.2020.71⟩ |
| Popis: | International audience; We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (a) whether there is some common index at which all given periodic, binary sequences are 0, and (b) whether a single cop can catch a single robber on an edge-periodic temporal graph. We further present results for various parameterizations of both problems and show that hardness not only applies in general, but also for highly limited instances. As one main result we show that even if the graph has a size-2 vertex cover and is acyclic in each time step, the cop and robber game on periodic, temporal graphs is NP-hard and W[1]-hard when parameterized by the size of the underlying input graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|