Graph operations on parity games and polynomial-time algorithms

Christoph Dittmann, Stephan Kreutzer, Alexandru Ioan Tomescu

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable before.
Original languageEnglish
JournalTheoretical Computer Science
Volume614
Pages (from-to)97-108
Number of pages12
ISSN0304-3975
DOIs
Publication statusPublished - 8 Feb 2016
MoE publication typeA1 Journal article-refereed

Fields of Science

  • 113 Computer and information sciences

Cite this

Dittmann, Christoph ; Kreutzer, Stephan ; Tomescu, Alexandru Ioan. / Graph operations on parity games and polynomial-time algorithms. In: Theoretical Computer Science. 2016 ; Vol. 614. pp. 97-108.
@article{c17fd7baeef64142b53ad98a5ae07a9c,
title = "Graph operations on parity games and polynomial-time algorithms",
abstract = "In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable before.",
keywords = "113 Computer and information sciences",
author = "Christoph Dittmann and Stephan Kreutzer and Tomescu, {Alexandru Ioan}",
year = "2016",
month = "2",
day = "8",
doi = "10.1016/j.tcs.2015.11.044",
language = "English",
volume = "614",
pages = "97--108",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier Scientific Publ. Co",

}

Graph operations on parity games and polynomial-time algorithms. / Dittmann, Christoph; Kreutzer, Stephan; Tomescu, Alexandru Ioan.

In: Theoretical Computer Science, Vol. 614, 08.02.2016, p. 97-108.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Graph operations on parity games and polynomial-time algorithms

AU - Dittmann, Christoph

AU - Kreutzer, Stephan

AU - Tomescu, Alexandru Ioan

PY - 2016/2/8

Y1 - 2016/2/8

N2 - In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable before.

AB - In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable before.

KW - 113 Computer and information sciences

UR - http://arxiv.org/abs/1208.1640

U2 - 10.1016/j.tcs.2015.11.044

DO - 10.1016/j.tcs.2015.11.044

M3 - Article

VL - 614

SP - 97

EP - 108

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -