Parity-Game Reduction by Winning-Cycles

• Item type: SIG Technical Reports(1)
• 公開日: 2021-03-10
• タイトル: Parity-Game Reduction by Winning-Cycles
• タイトル / 言語: en
• タイトル: Parity-Game Reduction by Winning-Cycles
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Computer and Network Engineering, Graduate School of Informatics and Engineering, the University of Electro-Communications
• 著者所属: Department of Computer and Network Engineering, Graduate School of Informatics and Engineering, the University of Electro-Communications
• 著者所属: Department of Computer and Network Engineering, Graduate School of Informatics and Engineering, the University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer and Network Engineering, Graduate School of Informatics and Engineering, the University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer and Network Engineering, Graduate School of Informatics and Engineering, the University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer and Network Engineering, Graduate School of Informatics and Engineering, the University of Electro-Communications
• 著者名: Ryota, Tsukatani; Remy, Belmonte; Hiro, Ito
• 著者名(英): Ryota, Tsukatani; Remy, Belmonte; Hiro, Ito
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Parity games are games that are played on directed graphs, where each vertex is labeled with a natural number. The vertices consist of two disjoint subset V0 and V1. Two players P0 and P1 move the token along the edges of graph, starting from the given initial vertex. If the token is on a vertex in V0, then P0 moves the token along one of the out-going edges from the vertex; otherwise, P1 does. If a player cannot move the token, he/she loses. Otherwise, the winner is determined by the maximum labeled number appearing infinitely often: if the number is even, P0 wins; otherwise P1 does. Deciding the winner in parity games belongs to NP and coNP, and it is open if it can be solved in polynomial-time. In this report, we introduce notions of forcing-cycles and winning-cycles, and give a polynomial-time algorithm for finding them. Moreover we show an algorithm to reduce a parity game by removing a winning-cycle if exists. By adapting this method, some parity games can be solved, or reduced to proper subgames in polynomial-time.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Parity games are games that are played on directed graphs, where each vertex is labeled with a natural number. The vertices consist of two disjoint subset V0 and V1. Two players P0 and P1 move the token along the edges of graph, starting from the given initial vertex. If the token is on a vertex in V0, then P0 moves the token along one of the out-going edges from the vertex; otherwise, P1 does. If a player cannot move the token, he/she loses. Otherwise, the winner is determined by the maximum labeled number appearing infinitely often: if the number is even, P0 wins; otherwise P1 does. Deciding the winner in parity games belongs to NP and coNP, and it is open if it can be solved in polynomial-time. In this report, we introduce notions of forcing-cycles and winning-cycles, and give a polynomial-time algorithm for finding them. Moreover we show an algorithm to reduce a parity game by removing a winning-cycle if exists. By adapting this method, some parity games can be solved, or reduced to proper subgames in polynomial-time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-182, 号 8, p. 1-6, 発行日 2021-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会