Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Near-Optimal Asymmetric Binary Matrix Partitions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Parameterized Algorithms for Parity Games

verfasst von : Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
Nächstes Kapitel Algorithmic Applications of Tree-Cut Width
Fußnoten
1
As usual in parameterized complexity the \(O^*\!\!\left( f(k)\right) \)-notation, for some function f of the parameter k, means that there is an algorithm running in time \(O(f(k)n^{O(1)})\), where n is the input size of the problem.
 
Literatur
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)MathSciNetCrossRefMATH
2.
Berwanger, D., Grädel, E., Kaiser, L., Rabinovich, R.: Entanglement and the complexity of directed graphs. Theor. Comput. Sci. 463, 2–25 (2012)MathSciNetCrossRefMATH
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, S.G.: Memoryless determinacy of parity and mean payoff games: a simple proof. Theor. Comput. Sci. 310(1–3), 365–378 (2004)MathSciNetCrossRefMATH
5.
Björklund, H., Vorobyov, S.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Appl. Math. 155(2), 210–229 (2007)MathSciNetCrossRefMATH
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)
7.
Browne, A., Clarke, E.M., Jha, S., Long, D.E., Marrero, W.R.: An improved algorithm for the evaluation of fixpoint expressions. Theor. Comput. Sci. 178(1–2), 237–255 (1997)MathSciNetCrossRefMATH
8.
Chatterjee, K., Henzinger, T.A.: A survey of stochastic \(\omega \)-regular games. J. Comput. Syst. Sci. 78(2), 394–413 (2012)MathSciNetCrossRefMATH
9.
10.
Dittmann, C., Kreutzer, S., Tomescu, A.I.: Graph operations on parity games and polynomial-time algorithms. arXiv preprint (2012). arXiv:​1208.​1640
11.
12.
Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model checking for the \(\mu \)-calculus and its fragments. Theor. Comput. Sci. 258(1–2), 491–522 (2001)MathSciNetCrossRefMATH
13.
Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 182–193. Springer, Heidelberg (2014) CrossRef
14.
Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163–176. Springer, Heidelberg (2013) CrossRef
15.
Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. LNCS, vol. 2500. Springer, Heidelberg (2002) MATH
16.
Hunter, P., Kreutzer, S.: Digraph measures: kelly decompositions, games, and orderings. Theor. Comput. Sci. 399(3), 206–219 (2008)MathSciNetCrossRefMATH
17.
Jurdzinski, M.: Deciding the winner in parity games is in UP cap co-up. Inf. Process. Lett. 68(3), 119–124 (1998)MathSciNetCrossRef
18.
Jurdziński, M.: Small progress measures for solving parity games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 290–301. Springer, Heidelberg (2000) CrossRef
19.
Jurdzinski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. SIAM J. Comput. 38(4), 1519–1532 (2008)MathSciNetCrossRefMATH
20.
Küsters, R.: Memoryless determinacy of parity games. In: Grädel, E., Thomas, W., Wilke, T. (eds.) Automata Logics, and Infinite Games. LNCS, vol. 2500, pp. 95–106. Springer, Heidelberg (2002)CrossRef
21.
22.
Obdržálek, J.: Fast mu-calculus model checking when tree-width is bounded. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 80–92. Springer, Heidelberg (2003) CrossRef
23.
Obdržálek, J.: Clique-width and parity games. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 54–68. Springer, Heidelberg (2007) CrossRef
24.
Schewe, S.: Solving parity games in big steps. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 449–460. Springer, Heidelberg (2007) CrossRef
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)MathSciNetCrossRefMATH
26.
Metadaten
Titel
Parameterized Algorithms for Parity Games
verfasst von
Jakub Gajarský
Michael Lampis
Kazuhisa Makino
Valia Mitsou
Sebastian Ordyniak
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48054-0_28