Parameterized Algorithms for Parity Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00081184" target="_blank" >RIV/00216224:14330/15:00081184 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-662-48054-0_28" target="_blank" >http://dx.doi.org/10.1007/978-3-662-48054-0_28</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-48054-0_28" target="_blank" >10.1007/978-3-662-48054-0_28</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Algorithms for Parity Games

Popis výsledku v původním jazyce

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 versionsof) 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.

Název v anglickém jazyce

Parameterized Algorithms for Parity Games

Popis výsledku anglicky

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 versionsof) 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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

MFCS 2015, LNCS 9235

ISBN

9783662480533

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

336-347

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Milano

Datum konání akce

1. 1. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000371027300028