Parity Games on Temporal Graphs

Austin, Pete ORCID: 0000-0003-0238-8662, Bose, Sougata ORCID: 0000-0003-3662-3915 and Totzke, Patrick ORCID: 0000-0001-5274-8190 (2024) Parity Games on Temporal Graphs. In: Lecture Notes in Computer Science. Lecture Notes in Computer Science, 14574 . Springer Nature Switzerland, pp. 79-98. ISBN 9783031572272

PDF 978-3-031-57228-9_5.pdf - Other Download (555kB) | Preview

Abstract

<jats:title>Abstract</jats:title><jats:p>Temporal graphs are a popular modelling mechanism for dynamic complex systems that extend ordinary graphs with discrete time. Simply put, time progresses one unit per step and the availability of edges can change with time.</jats:p><jats:p>We consider the complexity of solving<jats:inline-formula><jats:alternatives><jats:tex-math>$$\omega $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ω</mml:mi></mml:math></jats:alternatives></jats:inline-formula>-regular games played on temporal graphs where the edge availability is ultimately periodic and fixed a priori.</jats:p><jats:p>We show that solving parity games on temporal graphs is decidable in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{PSPACE}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>PSPACE</mml:mi></mml:math></jats:alternatives></jats:inline-formula>, only assuming the edge predicate itself is in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{PSPACE}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>PSPACE</mml:mi></mml:math></jats:alternatives></jats:inline-formula>. A matching lower bound already holds for what we call<jats:italic>punctual</jats:italic>reachability games on static graphs, where one player wants to reach the target at a given, binary encoded, point in time. We further study syntactic restrictions that imply more efficient procedures. In particular, if the edge predicate is in and is monotonically increasing for one player and decreasing for the other, then the complexity of solving games is only polynomially increased compared to static graphs.</jats:p>

Item Type:	Book Section
Uncontrolled Keywords:	46 Information and Computing Sciences
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	01 May 2024 08:16
Last Modified:	06 Dec 2024 12:48
DOI:	10.1007/978-3-031-57228-9_5
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3180692