Graph operations on parity games and polynomial-time algorithms

详细信息    查看全文

• 作者：Christoph Dittmann^a ; ^{christoph.dittmann@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Stephan Kreutzer^a ; ^{stephan.kreutzer@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Alexandru I. Tomescu^b ; ¹ ; ^{tomescu@cs.helsinki.fi" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Parity games ; Graph theory ; Directed graphs ; Tournaments ; Graph operations ; Graph algorithms
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：8 February 2016
• 年：2016
• 卷：614
• 期：Complete
• 页码：97-108
• 全文大小：474 K

文摘

In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable before.