Clique-Width and Parity Games

OBDRŽÁLEK, Jan. Clique-Width and Parity Games. In Computer Science Logic 2007, proceedings. Berlin: Springer-Verlag, 2007, s. 54-68. ISBN 978-3-540-74914-1.

Základní údaje

Originální název

Clique-Width and Parity Games

Název česky

Kliková šířka a paritní hry

Autoři

OBDRŽÁLEK, Jan (203 Česká republika, garant)

Vydání

Berlin, Computer Science Logic 2007, proceedings, od s. 54-68, 15 s. 2007

Nakladatel

Springer-Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Kód RIV

RIV/00216224:14330/07:00022579

Organizační jednotka

Fakulta informatiky

ISBN

978-3-540-74914-1

UT WoS

000250338100007

Klíčová slova anglicky

parity games; mu-calculus; clique-width

Štítky

clique-width, mu-calculus, parity games

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

The question of the exact complexity of solving parity games is one of the major open problems in system verification, as it is equivalent to the problem of model-checking the modal $\mu$-calculus. The known upper bound is NP$\cap$co-NP, but no polynomial algorithm is known. It was shown that on tree-like graphs (of bounded tree-width and DAG-width) a polynomial-time algorithm does exist. Here we present a polynomial-time algorithm for parity games on graphs of bounded clique-width (class of graphs containing e.g. complete bipartite graphs and cliques), thus completing the picture. This also extends the tree-width result, as graphs of bounded tree-width are a subclass of graphs of bounded clique-width. The algorithm works in a different way to the tree-width case and relies heavily on an interesting structural property of parity games.

Česky

Otázka přesné složitosti řešení paritních her je jedním hlavních otevřených problémů ve verifikaci systémů, neboť je ekvivaletním problému ověřování modelu pro modální mu-kalkul. Známá horní hranice je NP a co-NP, ale není znám žádný polynomiální algoritmus. Bylo ukázáno, že na grafech podobných stromům (grafy s omezenou stromovou šířkou a DAG-šířkou) takový algoritmus existuje. Zde předkládáme polynomiální algoritmus pro paritní hry na grafech s omezenou klikovou šířkou (třída grafů obsahující například úplné bipartitiní grafy a kliky), čímž doplňujeme obrázek dané oblasti. Tento výsledek také rozšiřuje výsledek pro stromovou šířku, neboť grafy s omezenou stromovou šířkou mají i omezenou klikovou šířku. Algoritmus pracuje odlišně od svého protějšku pro omezenou stromovou šířku a značně využívá zajímavé vlastnosti paritních her.

---

Návaznosti

1M0545, projekt VaV

Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky