@techreport{oai:ipsj.ixsq.nii.ac.jp:00210289,
 author = {Ryota, Tsukatani and Remy, Belmonte and Hiro, Ito and Ryota, Tsukatani and Remy, Belmonte and Hiro, Ito},
 issue = {8},
 month = {Mar},
 note = {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., 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.},
 title = {Parity-Game Reduction by Winning-Cycles},
 year = {2021}
}