Space Complexity of Graph Domination Games

V nalogi obravnavamo dominacijske igre na grah, njihove različice in igralno dominacijsko število, ki je število potez v poteku dominacijske igre, v kateri oba igralca igrata optimalno. Ukvarjamo se s prostorsko zahtev- nostjo izračuna igralnega dominacijskega števila. Pokažemo, da je igralno dominacijsko število možno izračunati z algoritmom, ki ima linearno pro- storsko zahtevnost, kar pomeni, da je problem v razredu PSPACE. Končno dokažemo, da je problem dominacijskih iger na grah PSPACE-poln za pre- vedbe v polinomskem času. To storimo s sklicevanjem na PSPACE-polnost problema zmagovalca igre na izjavnih formulah v konjuktivni obliki brez ne- gacij (POS-CNF).We consider domination games on graphs, their variants and the game domination number, which is the number of moves made in a graph domi- nation game assuming both players play optimally. We deal with the space complexity the game domination number. We show that the game domina- tion number can be calculated with an algorithm that runs in linear space complexity, which means that the problem is in PSPACE. Finally, we prove that the domination game on graphs problem is PSPACE-complete under polynomial time reductions. We do that using the PSPACE-completeness of the game problem on propositional formulas in conjunctive normal form without negations (POS-CNF)