×

Parameterized algorithms for parity games. (English) Zbl 1465.68112

Italiano, F. (ed.) et al., Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24–28, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9235, 336-347 (2015).
Summary: Determining the winner of a Parity Game is a major problem in computational complexity with a number of applications in verification. In a parameterized complexity setting, the problem has often been considered with parameters such as (directed versions of) treewidth or clique-width, by applying dynamic programming techniques.
In this paper, we adopt a parameterized approach which is more inspired by well-known (non-parameterized) algorithms for this problem. We consider a number of natural parameterizations, such as by Directed Feedback Vertex Set, Distance to Tournament, and Modular Width. We show that, for these parameters, it is possible to obtain recursive parameterized algorithms which are simpler, faster and only require polynomial space. We complement these results with some algorithmic lower bounds which, among others, rule out a possible avenue for improving the best-known sub-exponential time algorithm for parity games.
For the entire collection see [Zbl 1318.68024].

MSC:

68Q27 Parameterized complexity, tractability and kernelization
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Berwanger, D.; Dawar, A.; Hunter, P.; Kreutzer, S.; Obdržálek, J., The dag-width of directed graphs, J. Comb. Theo. Ser. B, 102, 4, 900-923 (2012) · Zbl 1246.05065 · doi:10.1016/j.jctb.2012.04.004
[2] Berwanger, D.; Grädel, E.; Kaiser, L.; Rabinovich, R., Entanglement and the complexity of directed graphs, Theor. Comput. Sci., 463, 2-25 (2012) · Zbl 1256.05086 · doi:10.1016/j.tcs.2012.07.010
[3] Bjorklund, H., Sandberg, S., Vorobyov, S.: On fixed-parameter complexity of infinite games. In: Sere, K., Waldén, M. (eds.) The Nordic Workshop on Programming Theory (NWPT 2003), number 34 in Åbo Akademi, Reports on Computer Science and Mathematics, pp. 29-31. Citeseer (2003)
[4] Björklund, H.; Sandberg, S.; Vorobyov, SG, Memoryless determinacy of parity and mean payoff games: a simple proof, Theor. Comput. Sci., 310, 1-3, 365-378 (2004) · Zbl 1098.91027 · doi:10.1016/S0304-3975(03)00427-4
[5] Björklund, H.; Vorobyov, SG, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, Discrete Appl. Math., 155, 2, 210-229 (2007) · Zbl 1176.68087 · doi:10.1016/j.dam.2006.04.029
[6] Bojanczyk, M., Dittmann, C., Kreutzer, S.: Decomposition theorems and model-checking for the modal \(\mu \)-calculus. In: Henzinger, T.A., Miller, D. (eds.) Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS 2014, Vienna, Austria, July 14-18, 2014, p. 17. ACM (2014) · Zbl 1394.68222
[7] Browne, A.; Clarke, EM; Jha, S.; Long, DE; Marrero, WR, An improved algorithm for the evaluation of fixpoint expressions, Theor. Comput. Sci., 178, 1-2, 237-255 (1997) · Zbl 0901.68118 · doi:10.1016/S0304-3975(96)00228-9
[8] Chatterjee, K.; Henzinger, TA, A survey of stochastic \(\omega \)-regular games, J. Comput. Syst. Sci., 78, 2, 394-413 (2012) · Zbl 1237.91036 · doi:10.1016/j.jcss.2011.05.002
[9] Condon, A., The complexity of stochastic games, Inf. Comput., 96, 2, 203-224 (1992) · Zbl 0756.90103 · doi:10.1016/0890-5401(92)90048-K
[10] Dittmann, C., Kreutzer, S., Tomescu, A.I.: Graph operations on parity games and polynomial-time algorithms. arXiv preprint (2012). arXiv:1208.1640 · Zbl 1334.05088
[11] Emerson, EA; Jutla, CS, The complexity of tree automata and logics of programs, SIAM J. Comput., 29, 1, 132-158 (1999) · Zbl 0937.68074 · doi:10.1137/S0097539793304741
[12] Emerson, EA; Jutla, CS; Sistla, AP, On model checking for the \(\mu \)-calculus and its fragments, Theor. Comput. Sci., 258, 1-2, 491-522 (2001) · Zbl 0973.68120 · doi:10.1016/S0304-3975(00)00034-7
[13] Fomin, FV; Liedloff, M.; Montealegre, P.; Todinca, I.; Ravi, R.; Gørtz, IL, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Algorithm Theory - SWAT 2014, 182-193 (2014), Heidelberg: Springer, Heidelberg · Zbl 1386.68068 · doi:10.1007/978-3-319-08404-6_16
[14] Gajarský, J.; Lampis, M.; Ordyniak, S.; Gutin, G.; Szeider, S., Parameterized algorithms for modular-width, Parameterized and Exact Computation, 163-176 (2013), Heidelberg: Springer, Heidelberg · Zbl 1406.68080 · doi:10.1007/978-3-319-03898-8_15
[15] Grädel, E.; Thomas, W.; Wilke, T., Automata, Logics, and Infinite Games: A Guide to Current Research (2002), Heidelberg: Springer, Heidelberg · Zbl 1011.00037
[16] Hunter, P.; Kreutzer, S., Digraph measures: kelly decompositions, games, and orderings, Theor. Comput. Sci., 399, 3, 206-219 (2008) · Zbl 1152.91015 · doi:10.1016/j.tcs.2008.02.038
[17] Jurdzinski, M., Deciding the winner in parity games is in UP cap co-up, Inf. Process. Lett., 68, 3, 119-124 (1998) · Zbl 1338.68109 · doi:10.1016/S0020-0190(98)00150-1
[18] Jurdziński, M.; Reichel, H.; Tison, S., Small progress measures for solving parity games, STACS 2000, 290-301 (2000), Heidelberg: Springer, Heidelberg · Zbl 0962.68111 · doi:10.1007/3-540-46541-3_24
[19] Jurdzinski, M.; Paterson, M.; Zwick, U., A deterministic subexponential algorithm for solving parity games, SIAM J. Comput., 38, 4, 1519-1532 (2008) · Zbl 1173.91326 · doi:10.1137/070686652
[20] Küsters, R.; Grädel, E.; Thomas, W.; Wilke, T., Memoryless determinacy of parity games, Automata Logics, and Infinite Games, 95-106 (2002), Heidelberg: Springer, Heidelberg · Zbl 1021.91501 · doi:10.1007/3-540-36387-4_6
[21] McNaughton, R., Infinite games played on finite graphs, Ann. Pure Appl. Logic, 65, 2, 149-184 (1993) · Zbl 0798.90151 · doi:10.1016/0168-0072(93)90036-D
[22] Obdržálek, J.; Hunt, WA Jr; Somenzi, F., Fast mu-calculus model checking when tree-width is bounded, Computer Aided Verification, 80-92 (2003), Heidelberg: Springer, Heidelberg · Zbl 1278.68188 · doi:10.1007/978-3-540-45069-6_7
[23] Obdržálek, J.; Duparc, J.; Henzinger, TA, Clique-width and parity games, Computer Science Logic, 54-68 (2007), Heidelberg: Springer, Heidelberg · Zbl 1179.68090 · doi:10.1007/978-3-540-74915-8_8
[24] Schewe, S.; Arvind, V.; Prasad, S., Solving parity games in big steps, FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 449-460 (2007), Heidelberg: Springer, Heidelberg · Zbl 1135.68480 · doi:10.1007/978-3-540-77050-3_37
[25] Zielonka, W., Infinite games on finitely coloured graphs with applications to automata on infinite trees, Theor. Comput. Sci., 200, 1-2, 135-183 (1998) · Zbl 0915.68120 · doi:10.1016/S0304-3975(98)00009-7
[26] Zwick, U.; Paterson, M., The complexity of mean payoff games on graphs, Theor. Comput. Sci., 158, 1-2, 343-359 (1996) · Zbl 0871.68138 · doi:10.1016/0304-3975(95)00188-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.