Jakub Gajarský

Michael Lampis

Kazuhisa Makino

Valia Mitsou

Sebastian Ordyniak

Parameterized Algorithms for Parity Games

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 bestknown sub-exponential time algorithm for parity games.

Introduction

A Parity Game is an infinite two-player game played on a parity game arena by the two players Even and Odd. A parity game arena is a sinkless directed graph, where every vertex is controlled by exactly one of the two players and is addionally assigned a priority (an integer value). Initially, a token is placed on some vertex of the graph (the starting vertex) and at each step of the game the player that controls the vertex that currently contains the token has to move the token along a directed edge to any outneighbor of that vertex. This leads to an infinite path, which is won by the player that corresponds to the parity of the highest priority occuring infinitely often on that path. Given such a parity game arena and a starting vertex v, the problem is to decide which of the two players has a winning strategy on the given arena if the token is initially placed on v.

Although a parity game may, at first glance, seem like an odd kind of game to play, the problem of deciding the winner of a parity game is extremely wellstudied. One of the reasons is that solving parity games captures the complexity of model-checking for the modal µ-calculus, which has a large number of applications in software verification (see e.g. [START_REF] Grädel | Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar[END_REF][START_REF] Emerson | On model checking for the µ-calculus and its fragments[END_REF][START_REF] Chatterjee | A survey of stochastic ω-regular games[END_REF]). Despite extensive efforts by the community, it is still a major open question whether there exists a polynomial-time algorithm for this problem [START_REF] Jurdzinski | Small progress measures for solving parity games[END_REF][START_REF] Björklund | A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games[END_REF][START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF][START_REF] Emerson | The complexity of tree automata and logics of programs[END_REF].

In addition to their wealth of practical applications, parity games are also especially interesting from a complexity-theoretic point of view because of their intriguing complexity status. Despite not being known to be in P, deciding parity games in known to be in NP∩coNP [START_REF] Emerson | On model checking for the µ-calculus and its fragments[END_REF], and in fact even in UP∩coUP [START_REF] Jurdzinski | Deciding the winner in parity games is in UP \cap co-up[END_REF]. The former of these two inclusions follows directly from the (non-trivial) fact that optimal strategies are known to be positional (or memoryless) [START_REF] Küsters | Memoryless determinacy of parity games[END_REF] and the fact that single-player parity games are in P. Parity games are also known to be reducible to (and therefore "easier" than) a number of other natural classes of games, including mean payoff games (which admit a pseudo-polynomial time algorithm) [START_REF] Zwick | The complexity of mean payoff games on graphs[END_REF] and simple stochastic games [START_REF] Condon | The complexity of stochastic games[END_REF]. Thus, in a sense, deciding the winner of a parity game is a problem that seems to lie only slightly out of reach of current algorithmic techniques, and could perhaps be solvable in polynomial time. However, the best currently known time upper bound is (roughly) n

√ n [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF].

Since, despite all this effort, it is still not clear if a polynomial-time algorithm for parity games is possible, several more recent works have attempted to tackle this problem from a parameterized complexity perspective. Perhaps the most natural parameter for this problem is the maximum priority p. Although this problem is known to be in XP, i.e., solvable in polynomial-time for fixed p, (by a classical O(n p )algorithm due to McNaughton [START_REF] Mcnaughton | Infinite games played on finite graphs[END_REF], later improved to O(n p/3 ) [START_REF] Browne | An improved algorithm for the evaluation of fixpoint expressions[END_REF][START_REF] Jurdzinski | Small progress measures for solving parity games[END_REF][START_REF] Schewe | Solving parity games in big steps[END_REF]), it is unclear if this parameterization could be in FPT, i.e., solvable in time O * (f (p)) 1 for some function f of p, though this question has been explicitly considered [START_REF] Bjorklund | On fixed-parameter complexity of infinite games[END_REF].

A direction which has been much more fruitful is to add a second parameter to the problem, usually some structural graph parameter of the input graph. Here, several non-trivial algorithmic results are known. For digraphs whose underlying graph has treewidth k the problem is solvable in time (roughly) p O(k) [START_REF] Obdržálek | Fast mu-calculus model checking when tree-width is bounded[END_REF], while a similar running time is achievable if k is the (directed) cliquewidth of the input digraph [START_REF] Obdržálek | Clique-width and parity games[END_REF]. For several directed variations of the notion of treewidth, such as entanglement, DAG-width and kelly-width, algorithms running in n O(k) time are known [START_REF] Berwanger | Entanglement and the complexity of directed graphs[END_REF][START_REF] Berwanger | The dag-width of directed graphs[END_REF][START_REF] Hunter | Digraph measures: Kelly decompositions, games, and orderings[END_REF]. More recently, an algorithm running in f (p, k)n O (1) time for these measures was given in [START_REF] Bojanczyk | Decomposition theorems and model-checking for the modal µ-calculus[END_REF], for some computable function f . Thanks to the above results we now know that parity games are FPT for the most standard structural graph parameters, if parameterized by both k and the maximum priority p. It is however, worthy of note that, to the best of our knowledge, this problem is not known to be FPT when the number of priorities is not part of the parameter for any non-trivial graph width. Furthermore, all the above algorithms, which use somewhat complicated dynamic programming techniques, also require space exponential in k. Can this be improved? Our contribution: This paper provides a number of algorithms for various natural structural parameterizations of parity games. More specifically, we show the following results:

• There exists an algorithm running in time O * 4 k p log k when k is any of the following parameters: the size of the graph's directed feedback vertex set, the number of vertices controlled by one of the two players, or the number of vertices whose deletion makes the graph a tournament.

• There exists an algorithm running in time

O * k O( √ k)
when k is the modular width of the input graph.

Conceptually, the main contribution of this paper is in repurposing the ideas of the classical algorithm of McNaughton [START_REF] Mcnaughton | Infinite games played on finite graphs[END_REF] (and its sub-exponential time variation by Jurdzinski, Paterson and Zwick [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]) in the parameterized complexity setting. By avoiding the dynamic programming paradigm, we are able to give a number of very simple to implement, recursive algorithms. Notably, all the algorithms of this paper run in polynomial space.

Our first set of algorithmic results introduces the notion of a dominion hitter. Informally, a dominion is a confined area of the graph where one player has a winning strategy. The algorithmic importance of dominions was recognized in [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF], where the algorithm begins by exhaustively looking for a small dominion in the graph, before running the simple recursive algorithm of [START_REF] Mcnaughton | Infinite games played on finite graphs[END_REF]. We give a parameterized counterpart of this idea which can be applied whenever we can find a small set of vertices that intersects all dominions. We then also provide three natural example parameterizations where this is the case, showing that this may be an idea of further interest.

We then consider graphs of modular width k. Modular width is a graph parameter that has recently attracted attention in the parameterized complexity community as a more restricted alternative to clique-width [START_REF] Fomin | Algorithms parameterized by vertex cover and modular width, through potential maximal cliques[END_REF][START_REF] Gajarský | Parameterized algorithms for modular-width[END_REF]. We show that, in this more restricted case, the O * p k complexity of the algorithm for clique-width can be improved to a running time that is FPT parameterized only by k, with a sub-exponential parameter dependence. The core algorithmic idea again combines the recursive algorithm of McNaughton, with a judicious search for dominions.

We complement these algorithms with a couple of hardness results. First, as mentioned, one of the key steps in the sub-exponential algorithm of [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF] (and in most of our algorithms) consists of exhaustively searching the graph for a dominion. In [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF] searching for a dominion of size k is done by checking all sets of k vertices. We give a reduction from Multi-Colored Clique showing that this is likely optimal, thus ruling out one possible avenue for improving the algorithm of [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]. Furthermore, in order to demonstrate that the parameterizations we consider are non-trivial, we give a reduction showing that Rabin games (a more general class of infinite games) remain hard for many of the cases of this paper.

Definitions and Preliminaries

Parity Games, Dominions and Attractors

In a parity game the input is a sinkless directed graph G(V, E), where V is partitioned into two sets V 0 , V 1 , a priority function Pr : V → N, and a starting vertex v ∈ V . Throughout the paper we use n to denote |V | and p to denote the maximum priority given to any vertex of G max{Pr(u) : u ∈ V }. We also use N + (u) (respectively N -(u)) to denote the set of out-neighbors (in-neighbors) of the vertex u.

In this game there are two players, player 0 (the even player) and player 1 (the odd player), controlling the vertices of V 0 and V 1 respectively. A token is initially placed on the starting vertex v and, in each turn, the player who controls the vertex that currently contains the token selects one of its outneighbors and moves the token there (an out-neighbor always exists, since the graph has no sinks). The play then goes on to the next round and continues infinitely. Player 0 is the winner of a play if and only if the vertex that has maximum priority out of all the vertices that appear infinitely often in the play has even priority; otherwise, player 1 is the winner. A player has a winning strategy from a starting vertex v, if she has a way to construct a winning play when the game starts from v no matter how the opponent plays. For more information on parity games see for example [START_REF] Grädel | Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar[END_REF].

We use W i (G), for i ∈ {0, 1} to denote the winning region of player i in the game graph G, that is, the set of vertices from which player i has a winning strategy (and we will simply write W i if G is clear from the context). It is a well-known (but non-trivial) fact that each player has a memory-less positional strategy, i.e a strategy where decisions depend on the current position of the token and not on the history, that allows her to win all the vertices of her winning region [START_REF] Björklund | Memoryless determinacy of parity and mean payoff games: a simple proof[END_REF][START_REF] Emerson | On model checking for the µ-calculus and its fragments[END_REF][START_REF] Küsters | Memoryless determinacy of parity games[END_REF]. We will make use of the following basic fact:

Fact 1. For all i ∈ {0, 1} and all vertices v ∈ V i we have v ∈ W i if and only if N + (v) ∩ W i = ∅.
Let us now formally define two notions that will be crucial throughout this paper: dominions and attractors. Definition 1. A set of vertices D ⊆ V is an i-dominion, for some i ∈ {0, 1} if the following hold:

1. There are no arcs from D ∩ V 1-i to V \ D and every vertex of D ∩ V i has an out-neighbor in D.

2. Player i has a winning strategy for all starting vertices in the parity game on the induced subgraph G[D].

Informally, an i-dominion is a region of the graph where player i can force the token to remain, and by doing so she manages to win the game. It is not hard to see that W i (G) is always an i-dominion, but smaller i-dominions could also exist. Definition 2. An i-attractor of a set of vertices S, for some i ∈ {0, 1}, denoted attr i (S), is the smallest superset of S that satisfies the following:

1. There are no arcs from V i \ attr i (S) to attr i (S).

2. Every vertex of V 1-i \ attr i (S) has an out-neighbor outside of attr i (S).

Intuitively, an i-attractor of a set S is a region inside which player i can force the token to eventually enter S (this should obviously include S itself).

It is not hard to see that an i-attractor can be calculated in polynomial time by iteratively adding vertices to S, as dictated by the above specifications. One of the reasons that we are interested in attractors is that they allow us to simplify the game once we identify some part of one player's winning region, thanks to the following fact, which is e.g. shown in [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]Lemma 4.5].

Fact 2. If, for some i ∈ {0, 1} and S ⊆ V , we have S ⊆ W i , then W i (G) = attr i (S) ∪ W i (G \ attr i (S)).

We will often make use of the fact that an attractor for one player cannot expand into the region of a dominion controlled by the opponent. Lemma 1. For i ∈ {0, 1} let D be an i-dominion and S ⊆ V be a set of vertices such that S ∩ D = ∅. Then attr 1-i (S) ∩ D = ∅.

Proof. Consider the iterative process that adds vertices to S to build attr 1-i (S). No vertex of D can be the first to be added to the attractor in this process: vertices of D ∩ V i have an out-neighbor in D and vertices of D ∩ V 1-i have all their out-neighbors in D.

Finally, let us point out that a dominion that is completely controlled by a single player can be found (and by Fact 2 removed from the graph) in polynomial time. We will therefore always assume that in all the graphs we consider, no player can win without at some point passing the token to her opponent. Fact 3. If there exists a dominion D such that D ⊆ V i for some i ∈ {0, 1}, then such a dominion can be found in polynomial time.

Attractor-based Algorithms

We give here a short descriptive sketch of the attractor-based algorithms of [START_REF] Mcnaughton | Infinite games played on finite graphs[END_REF][START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]. One of the main approaches for solving parity games is the attractorbased approach often referred to as McNaughton's algorithm [START_REF] Mcnaughton | Infinite games played on finite graphs[END_REF][START_REF] Zielonka | Infinite games on finitely coloured graphs with applications to automata on infinite trees[END_REF]. We sketch here the algorithm, which has served as the starting point of many subsequent improvements, as well as most of the algorithms of this paper. The first step in McNaughton's algorithm is to locate the set of vertices S that have maximum priority p in the input graph. Let i := p mod 2. One then calculates the set A := attr i (S). We now recursively call the algorithm on the graph G \ A, that is, the graph obtained by deleting the vertices of A. This allows us to calculate the winning regions of G \ A.

There are now two cases. If player i wins from every vertex of this new graph, then she has a strategy to win from every vertex of G. To see this, observe that when the token enters A player i can follow a strategy that leads the token to S, therefore, if the token enters A infinitely often in a play, the maximum priority will be p, which is winning for i. If the token does not enter A infinitely often then play is eventually restricted to G \ A where player i wins everywhere. So, in this case we are done. If, on the other hand, player 1 -i wins some vertices of

G \ A then W 1-i (G \ A), which is a (1 -i)-dominion in G \ A, is also a (1 -i)-dominion in G.
Therefore, we can use Fact 2 to simplify the graph. We then recursively solve the remaining game. Proof. Let T (n, p) denote the worst-case running time of the algorithm. Then T (n, p) ≤ T (n -1, p -1) + T (n -1, p) + n O (1) , since in the first recursive call the maximum priority has been decreased and in the second call (if it is made) we have deleted at least one vertex. Solving this recurrence gives the claimed bound.

Perhaps one of the most notable improvements building upon McNaughton's algorithm is the deterministic sub-exponential algorithm of Jurdzinski, Paterson and Zwick [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF] (before their work the only sub-exponential algorithms known for this problem were randomized LP-based algorithms [START_REF] Björklund | A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games[END_REF]). Let us also sketch this approach, which we extend in this paper. The idea is to precede the running of McNaughton's algorithm by a pre-processing step, which looks for a "small" dominion in the input graph. The pre-processing is done by brute force, trying out all sets of size at most c, where c is a parameter to be optimized later (in section 5 we argue that this brute force step cannot be improved). If such a dominion is found, it can be removed from the graph using Fact 2. Otherwise, we know that if McNaughton's algorithm makes a second recursive call, a dominion of size at least c will have been removed from the graph. Judiciously selecting c to balance the two steps gives a sub-exponential running time. Proof. We select c to be

√ n. Then, if T (n) is the worst-case running time on n vertices, we have T (n) ≤ n c c c + T (n -1) + T (n -c).

Strong Dominion Hitters

In this section we introduce the notion of a dominion hitter and show several (parameterized) algorithmic applications. The ideas presented here are heavily inspired by the sub-exponential algorithm of [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF], which looks for small dominions in the input graph. Here we will be interested in the intersection of the located dominion with a special set that intersects all dominions. We give two straight-forward applications of this idea (for parameters directed feedback vertex set and number of vertices of one player) and a slightly more involved one (for parameter distance from tournament). Before moving forward, let us give some useful definitions.

Definition 3. A set S ⊆ V is a dominion hitter if for every (non self-controlled) dominion D of G we have S ∩ D = ∅. A set S ⊆ V is a strong dominion hitter if, for every V ⊆ V for which G[V ] is a game, S ∩ V is a dominion hitter in G[V ].
Let us explain the intuition behind the definition of strong dominion hitters. First, by Fact 3 we can remove self-controlled dominions in polynomial time from G and all of its subgames. Now, if G contains a strong dominion hitter S with |S| = k then McNaughton's algorithm will run in time O * n k , since the second recursive call will always delete at least one vertex of S (in fact the running time can also be upper-bounded by O * p k , since the first recursive call decreases p).

Our strategy in this section will be to improve upon McNaughton's algorithm significantly by following a strategy similar to that of [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]. Suppose we are given a strong dominion hitter S. First, we look for a dominion that has a small intersection with S. As we will argue, this can be done by solving parity games (recursively) on a much simpler graph where a large part of S has been deleted. If such a dominion is found, it can be removed from the graph. If that fails, then every dominion must have a large intersection with S, therefore we know that McNaughton's algorithm's second recursive call will be on a graph where much of S has been deleted. Proper balancing allows us to obtain a running time of O * p log k 4 k (Lemma 2). Let us now describe exactly how dominion hitters can be exploited. Lemma 2. There is an algorithm which, given a parity game instance G(V, E) and a strong dominion hitter S with |S| = k decides the problem in O * p log k 4 k time.

Proof. The algorithm proceeds as follows: first, for every S ⊂ S with |S | = s, where s is a parameter to be fixed later, we will try to find a dominion D such that D ∩ S ⊆ S . For i ∈ {0, 1} we will describe how to find such an i-dominion, if it exists.

Let A := attr 1-i (S \ S ). We solve parity games on the graph G \ A by recursively calling this algorithm. Now, we claim that W i (G \ A) (if non-empty) is an i-dominion in G. To see this, observe that, by definition, the game restricted to W i (G \ A) is a win for i, and vertices of V 1-i ∩ W i (G \ A) have no outgoing edges to A, by the definition of attractors, or W 1-i (G \ A), by Fact 1. On the other hand, we claim that if an i-dominion D exists in G such that D ∩ S ⊆ S then D ⊆ W i (G \ A). This follows from Lemma 1. Thus, we can conclude whether an i-dominion with the requested intersection with S exists (and find it if it does) by solving parity games on a graph where at least |S \ S | ≥ k -s vertices of S have been deleted. If a dominion is found, we can remove it from the graph using Fact 2.

If no dominion (of either player) is found in the first phase, since S is a dominion hitter we know that any dominion includes at least s vertices of S. We now essentially follow McNaughton's approach: remove an attractor of the maximum priority vertices, solve the remaining graph recursively and, if necessary, remove the discovered winning region and solve the remainder recursively.

Let us analyze the running time of the above procedure. Suppose that T (n, p, k) is the worst-case running time for a graph with n vertices, maximum priority p and a strong dominion hitter of size k. The first phase requires time at most 2 k s [T (n, p, s) + O(n a )] (removing a dominion takes polynomial time O(n a )). If a dominion D is found, we solve recursively an instance where we have removed an attractor of D in time T (n, p, k -1) + O(n a ). If no dominion is found, we first make a recursive call that takes time T (n, p -1, k) + O(n a ) since the maximum priority is decreased and then a recursive call that takes time at most T (n, p, k -s) + O(n a ). Removing self-controlled dominions takes polynomial time O(n b ). So, overall we have

T (n, p, k) ≤ 2 k s [T (n, p, s) + O(n a )] + max{T (n, p, k -1), T (n, p -1, k) + T (n, p, k -s)} + O(n a + n b )
Observe that the algorithm we have described generalizes the algorithm of [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]: in the worst case k = n (the dominion hitter is all the vertices) and we can select s = √ n to obtain essentially the same running time. However, here we want to leverage the fact that we may have a small dominion hitter. We will set s = k/2 and prove inductively that T (n, p, k) ≤ 4 k p log k O(n c ), where c > max{a, b} is a constant.

For p, k > 4, and sufficiently large n:

(a) 2 k k 2 [T (n, p, k/2) + O(n a )] + T (n, p, k -1) + O(n a + n b ) ≤ 2 k 4 k 2 p log k 2 O(n c ) + 4 k-1 p log k O(n c ) + 2 k O(n a + n b ) ≤ 1 p + 1 4 + 2 k O(n a + n b ) 4 k p log k O(n c ) 4 k p log k O(n c ) ≤ 4 k p log k O(n c ). (b) 2 k k 2 [T (n, p, k/2) + O(n a )] + T (n, p -1, k) + T (n, p, k/2) + O(n a + n b ) ≤ 2 k T (n, p, k/2) + T (n, p -1, k) + 2 k O(n a + n b ) ≤ 2 k 4 k 2 p log k 2 O(n c ) + 4 k (p -1) log k O(n c ) + 2 k O(n a + n b ) ≤ 1 p + p -1 p log k + 2 k O(n a + n b ) 4 k p log k O(n c ) 4 k p log k O(n c ) ≤ 4 k p log k O(n c ).

Direct applications

Let us first consider two direct applications of the idea of strong dominion hitters. One is the parameterization of the problem where the parameter is the directed feedback vertex set S of the graph, i.e. a set of vertices whose removal makes the graph a DAG. Since every dominion should contain a directed cycle, S is clearly a strong dominion hitter. Application of Lemma 2 is straightforward.

Theorem 3. Given an instance of parity games G(V, E) and a directed feedback vertex set S, |S| ≤ k of G, there exists an algorithm which decides the problem in time O * p log k 4 k .

Another example is the parameterization of the problem where the parameter k is equal to |V 1 |, the number of vertices controlled by one of the players. Because of Fact 3, V 1 is a strong dominion hitter. Once again Lemma 2 can be applied directly.

Theorem 4. There exists an algorithm which given an instance of parity games

G(V, E) such that |V 1 | = k decides the problem in time O * 4 k p log k .

More involved case

Now we will see how we can apply the idea of strong dominion hitters to a less straightforward case, where the graph is almost a tournament (a tournament is a directed graph having at least one arc between every pair of vertices).

Once again, due to Fact 3, G is free of i-controlled i-dominions (we call these dominions happy). In fact, this implies something even stronger: that no happy dominion exists in any subgame of G. Then all i-dominions in G shall have an unhappy vertex, i.e. a vertex controlled by player (1 -i). The next fact shall prove useful.

Fact 4. Let v 0 ∈ V 0 ∩ W 1 and v 1 ∈ V 1 ∩ W 0 be unhappy vertices. Then v 0 and v 1 are not neighbors.
Proof. (v 0 , v 1 ) ∈ E, otherwise the even player would have had a way to escape from v 0 to W 0 . With similar reasoning (v 1 , v 0 ) ∈ E.

We first need to establish that parity games on tournaments can be solved in polynomial time, using the above observation. In fact, we can show that in tournaments, after we remove happy dominions, one player wins all the vertices. The fact that parity games are polynomially decidable on tournaments was already shown in [START_REF] Dittmann | Graph operations on parity games and polynomial-time algorithms[END_REF], but a proof is included here for the sake of completeness.

We then study the parameterization where the parameter is the vertexdeletion distance of the graph from being a tournament. In this case, the graph is basically a tournament plus a set S of at most k additional vertices which might be missing arcs (this case is more general than the case of a tournament missing a set of k edges).

The algorithm is similar to Lemma 2. If S happens to be a dominion hitter the procedure reduces S by at least k 2 either during the preprocessing or during the second recursive call of McNaughton's algorithm. If S is not a dominion hitter, then the dominion found after removing attr i (p) might not intersect S. In this case however, we argue that the (1 -i)-attractor of the winning region W 1-i (G \ attr i (p)) of the smaller graph should absorb all vertices of V 1-i \ S, leaving an instance where player (1 -i) has vertices only in S (up to k vertices). We can then use Theorem 4. The algorithmic results of this section are thus summarized in the following two theorems.

Theorem 5. Parity games on tournaments can be solved in polynomial time.

Proof. Given a tournament T , we use Fact 3 to obtain a tournament G(V, E) with no happy dominions.

We will first prove that in G all vertices are won by one player, that is either W 0 or W 1 of G is empty. Suppose that W 0 , W 1 are both non-empty. Then, by Fact 4 there would be two unhappy vertices which would not be connected. This is a contradiction because G is a tournament.

What we need to figure out is which of the two players wins. This can be done once again by running McNaughton's algorithm, though we show that in the case of tournaments we don't need the second recursive call. Indeed, suppose we have removed attr i (p) of the maximum priority p and solved the remaining game G (V , E ). This too is a tournament, so one player should win the whole graph. If player i wins everything in G , then this is clearly the case for G. If player 1 -i wins everything in G , then V is an (1 -i)-dominion of G and by the observation that all vertices are won by one player this makes player (1 -i) the winner in the rest of G.

All that remains is to find a strategy for player (1 -i) in attr i (p) = V \ V . We know that player (1 -i) should be winning the whole graph, so any vertex belonging in V i ∩ V should not be able to escape to attr i (p) (we know that there exists at least one such vertex, call it u). That means that all vertices in attr i (p) ∩ V 1-i should have at least one edge towards V (say to u). So the strategy for player 1 -i is to send the token to u. Theorem 6. Given a graph G(V, E) on n vertices and a set S ⊆ V with |S| ≤ k such that G\S is a tournament, parity games can be solved in time O * p log k 4 k .

Proof. Again, we first pre-process the graph to obtain graph G(V, E) with no happy dominions. G should also have a set S of at most k vertices the removal of which leaves a tournament.

We proceed in a similar way as in Lemma 2. First, for i ∈ {0, 1}, for all S ⊂ S of size |S | ≤ k 2 we try to find a dominion D ∩ S = ∅. If such a dominion exists we remove it from the graph using Fact 2 and solve a smaller instance. Otherwise we know that every dominion either uses at least k 2 vertices from S or it has an empty intersection with S.

In the latter case, we run McNaughton's algorithm: remove A = attr i (p) and potentially find a winning region W 1-i (G \ A) with at least one unhappy vertex

v i ∈ W 1-i (G \ A) ∩ V i . • If W 1-i (G \ A) ∩ S = ∅,
this case should be similar to Lemma 2.

• If W 1-i (G \ A) ∩ S = ∅,
observe that all vertices in A \ S should have v i as an out-neighbor, otherwise v i would belong in A. Furthermore, by Fact 4, all unhappy vertices of W i (G \ A) should belong to S. Thus, when we compute A = attr 1-i (W 1-i (G \ A)), all vertices of player (1 -i) but those in S will be absorbed, so G \ A should be a graph where player (1 -i) controls possibly only vertices from S. We shall then proceed similarly to Theorem 4.

The complexity of this algorithm is similar to that of Lemma 2. If we call A(n, p, k) the worst-case running time for a graph with n vertices, maximum priority p and a set of k vertices missing arcs and O(n a ) the complexity of removing a dominion, the first phase again requires time at most 2 k

2 k k 2 [A(n, p, k/2) + O(n a )] + A(n, p -1, k) + 4 k p log k O(n c ) + O(n a ) ≤ 2 k 4 k 2 p log k 2 +1 O(n d ) + 4 k (p -1) log k+1 O(n d ) + 4 k p log k O(n c ) + 2 k O(n a ) ≤ 4 k p log k O(n d ) + p -1 p log k+1 4 k (p -1) log k+1 O(n d ) + 2 k O(n a ) ≤ 1 p + p -1 p log k+1 + 2 k O(n a ) 4 k p log k+1 O(n c ) 4 k p log k+1 O(n d ) ≤ 4 k p log k+1 O(n d ).
This concludes the proof.

Modular Width and Graphs with k Modules

The main result of this section is an FPT algorithm which solves parity games on graphs with small modular width. In fact, the algorithm we present is able to handle the more general case of strongly connected graphs whose vertex set can be partitioned into k > 1 modules. For such graphs, we are able to obtain a sub-exponential FPT algorithm, even for unbounded p (that is, parameterized just by k), and from this we can then obtain the same result for modular width.

Recall that a set of vertices M of a directed graph G(V, E) is a module if for any two vertices u, v ∈ M we have

N + (u) \ M = N + (v) \ M and N -(u) \ M = N -(v) \ M , that
is, all vertices of M have the same in-and out-neighbors outside of M . Let us begin this section by presenting an algorithm that decides parity games on G in time O * 4 k . We then give an improved version with sub-exponential running time.

Exponential FPT algorithm

Suppose that we are given a strongly connected graph G(V, E), along with a partition of V into k > 1 non-empty modules M 1 , . . . M k . We will call these the graph's basic modules.

On a high level, the strategy we will follow is again a variation of Mc-Naughton's algorithm. This algorithm makes two recursive calls, each on a graph obtained from G by removing an attractor of some set. If the removed set contains all of M j ∩ V i for some j ∈ {1, . . . , k}, i ∈ {0, 1} then we can intuitively think that we are making a lot of progress: such recursive calls cannot have a depth of more than 2k before we are able to solve the problem (this is where the O * 4 k running time comes from). Thus, our high-level strategy is to avoid branching in cases where the removed set does not simplify the graph in this way.

Let us begin by arguing that the algorithm's second recursive call always makes significant progress in the sense described above. In the remainder we assume, as in the previous section, that the graph has been simplified using Fact 3, so each player must at some point pass the token to her opponent to avoid losing. We now need a helpful lemma. Lemma 3. Let M be a non-sink module of G and suppose that W i ∩ M = ∅. Then, V i ∩ M ⊆ W i . Furthermore, there exists a vertex v ∈ W i \ M such that there is an edge from M to v.

Proof. Let M ⊆ V \ M be the set of vertices that have an incoming edge from M (and, therefore, have incoming edges from all vertices of M , since M is a module). By assumption, M = ∅.

If M ∩ W i = ∅ then we are done, because all vertices of V i ∩ M have an out-neighbor in W i , so they must also belong in W i by Fact 1.

Let us then show that it cannot be the case that M ∩ W i = ∅. In that case we have M ⊆ W 1-i . Observe now that M ∩ V 1-i ⊆ W 1-i by Fact 1 and the fact that M is non-empty. Any winning play for player i starting from a vertex u ∈ M must eventually visit either M ∩ V 1-i (because player i does not control a winning cycle) or M . However, both of these sets are subsets of W 1-i , which is a contradiction.

An informal way to interpret Lemma 3 is that, if a player wins some vertex of a module, then she must be winning all the vertices she controls in that module. We now have the following: Corollary 1. Let D be an i-dominion, for some i ∈ {0, 1} and M a non-sink module such that

D ∩ M = ∅. Then attr i (D) ⊇ M ∩ V i .
Proof. Similarly to the proof of Lemma 3, if the graph contains no trivial cycles (which it does not, thanks to Fact 3) then D cannot be contained in M .

We now know that the second recursive call of McNaughton's algorithm will always remove all the vertices owned by one of the two players in one of the basic modules. What remains is to deal with the first recursive call, where we remove an attractor of the maximum priority vertices. In this case we cannot guarantee that the removal of the attractor will necessarily produce a much simpler graph. However, we will argue that, if the graph is not simplified, the removed vertices were "irrelevant": their presence does not change the winning status of any other vertex. We will then be able to calculate their winning status without making the second recursive call using Lemma 3. The key idea is contained in the following lemma. Lemma 4. Let p be the maximum priority in G, v be a vertex with priority p and i := p mod 2. Let A := attr i ({v}). Suppose that A ⊆ M j for some basic non-sink module M j and that if A contains a vertex controlled by some player, then M j \ A also contains a vertex controlled by that player. Then we have

W i (G) \ A = W i (G \ A). Proof. Observe that for any u ∈ W 1-i (G \ A) we also have u ∈ W 1-i (G), by standard properties of attractors. Contrapositively, u ∈ W i (G) \ A implies that u ∈ W i (G \ A).
Therefore, it suffices to show that for all u ∈ W i (G \ A) we have u ∈ W i (G). In other words, we need to describe a strategy for player i which wins in G at least the same vertices i can win in G \ A.

We will say that a vertex u ∈ G\A is problematic if u ∈ W i (G\A)∩W 1-i (G), that is, u is a counterexample to the lemma. If a problematic vertex u exists, then there must exist a problematic vertex that has an edge to A in G. To see this, consider a play starting from u where player i uses her optimal strategy for G \ A. If player 1 -i is using her optimal strategy in G, then the token must eventually leave W i (G \ A) (otherwise player i would win). This can only be done through a vertex of V 1-i , since player i is following a strategy that keeps the token in W i (G \ A). Such vertices have no edges to W 1-i (G \ A), therefore the only way out is through A.

Suppose then that u is a problematic vertex that has an edge to A. Therefore, u ∈ V 1-i , otherwise u would be in the attractor. Suppose that u ∈ M j . It must then be the case that M j \ A ⊆ W i (G \ A), by Fact 1, since u has edges to all of M j . If, on the other hand, u ∈ M j then for any u ∈ M j that has an incoming edge from M j we have u ∈ W i (G \ A). This again implies that

M j \ A ⊆ W i (G \ A), using Lemma 3.
So, if there exists a problematic vertex u then player i is winning all of M j \A in G \ A. If v ∈ V i then player i can follow the following strategy in G: for vertices of G \ A follow an optimal strategy for G \ A, for vertices of A \ {v} follow a strategy that leads the token to v, and from v push the token to a vertex of V \ M j that belongs in W i (G \ A) (such a vertex exists by Lemma 3). If the token enters A infinitely often player i wins, otherwise the last time the token leaves A it is trapped in W i (G \ A), where player i wins. Thus, no problematic vertex can exist in this case.

Finally, suppose that v ∈ V 1-i . By the conditions of the lemma there exists a vertex w ∈ V 1-i ∩ (M j \ A). As before, if there exists a problematic vertex, player i wins all of M j \ A, including w, in G \ A. Therefore, player i wins (in G \ A) every vertex w ∈ M j that has an incoming edge from M j . Player i now follows the same strategy as in the previous paragraph. Observe that once again, if the token visits A infinitely often the maximum priority is p, otherwise, when the token leaves v it will go to a vertex that player i wins in G \ A.

We are now ready to put everything together to obtain the promised algorithm.

Theorem 7. Consider a parity game on a strongly connected graph G(V, E) where V is partitioned into k > 1 non-empty modules. There exists an algorithm that decides the winning regions of the two players and their winning strategies from these regions in time O * 4 k .

Proof. We will run a version of McNaughton's algorithm, so at each step we will be looking at a subgraph of G. The measure of progress for our algorithm will be the number of pairs i, j for i ∈ {0, 1} and j ∈ {1, . . . , k} such that V i ∩M j = ∅ in the current graph. Initially the measure has value at most 2k and we want to prove that any non-trivial recursive step decreases its value.

We want to maintain the following invariant: for each basic module M j of the original graph, in any considered subgraph the vertices of M j which remain form a module which is either controlled by a single player or has some outgoing edge. The invariant is initially satisfied, since the graph is strongly connected, therefore all modules have outgoing edges.

Let us argue that, as long as we produce the considered subgraphs by removing attractors, the invariant will always hold. Indeed, suppose that at some point in the algorithm's execution one of the basic modules M j has lost all its outgoing arcs. That means that we removed an attractor that contained a vertex v such that all vertices of M j were pointing to v. Thus, for some i ∈ {0, 1} all vertices of V i ∩ M j must have also been placed in the same attractor as v.

The algorithm is now the following: first, suppose that there exists a module M j without outgoing edges. We solve the problem on G[M j ]; this can be done in polynomial time since all its vertices belong to one player. We can now simplify G using Fact 2. We then continue with the remainder of the graph.

So the interesting case is when all basic modules have outgoing edges. Now we do the following: first locate a vertex v with maximum priority p, and let i := p mod 2. Let A := attr i ({v}). If A fulfills the requirements of Lemma 4 then we solve the problem on G \ A recursively. We then know the winning status of all vertices of G \ A in G, since by Lemma 4 this does not change when we put the attractor back. We can also infer the winning status of vertices of A: if u ∈ A ∩ V l for l ∈ {0, 1} then there exists a vertex u ∈ (M j \ A) ∩ V l and we know the winning status of u . By Lemma 3 u has the same winner. Thus, in this case we are done.

Finally, if A does not fulfill the requirements of Lemma 4 then we solve (recursively) the problem on G \ A and then proceed as in McNaughton's algorithm. That is, we know that W 1-i (G \ A) is a (1 -i)-dominion in G, so we use Fact 2 to remove it and solve recursively in the rest of the graph. We will argue that in both of these cases the graph we recurse on is simpler.

If A does not fulfill the requirements of Lemma 4, then we have two cases: In the first case, A contains some vertex u of another module M j . If u ∈ V i then A contains all vertices of M j ∩ V i (which was non-empty) so the complexity measure is reduced. If u ∈ V 1-i then A must contain all of M j , so again the complexity measure is reduced. In the second case, A contains all of the vertices of M j controlled by some player, so deleting A eliminates V l ∩ M j for some l ∈ {0, 1}. So, the graph obtained after removing A is simpler.

For the second recursive call, observe that if we know the winning status of a vertex u, we know the winning status of all vertices which are in the same module and controlled by the same player as u (by Lemma 3). So we can assume that for the second recursive call we remove a region that contains all of V i ∩ M j for some i, j.

We are now ready to conclude that the running time of the recursive algorithm we have described is O * 4 k . To see this, note that if the algorithm makes two recursive calls, each is on a graph where we have just removed all of V i ∩ M j for some i, j. Suppose that we started with a graph where all modules have outgoing edges. Then, after a depth of at most 2k -1 operations where V i ∩ M j is removed for some i, j, we have a graph that contains a module M j without outgoing edges. Furthermore, by the stated invariant, this module is controlled by a single player and can be solved in polynomial time.

It's now easy to apply the above algorithm to the case of modular width.

Corollary 2. There exists a O * 4 k algorithm that decides parity games on graphs with modular width k.

Proof. Recall that a graph has modular width k if it is K 1 or it can be partitioned into at most k modules such that each module induces a graph with modular width k. This recursive structure is usually described by a tree, called a modular decomposition, which can be calculated in linear time [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF].

If the input graph is strongly connected then we can invoke Theorem 7. Otherwise, we find a strongly connected component without outgoing edges. This part of the graph also has modular width k, so we can apply to it Theorem 7 and, after calculating its winning regions, remove them from the original graph and repeat.

Sub-exponential FPT algorithm

Let us now present an improved version of the algorithm of Theorem 7. The idea is inspired by the improved version of McNaughton's algorithm from [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]: we will first look for a dominion that is confined inside at most √ k of the k basic modules. If such a dominion is found we can simplify the graph. Otherwise, we know that the second recursive call (when made) will touch at least √ k dominions, thus making significant progress.

Theorem 8. Consider a parity game on a strongly connected graph G(V, E) where V is partitioned into k > 1 non-empty modules. There exists an algorithm that decides the winning regions of the two players and their winning strategies from these regions in time k O( √ k) n O (1) .

Proof. We use the same invariant and the same measure of progress as in the proof of Theorem 7. The difference now is the following: suppose that each of the (remaining) basic modules has outgoing edges. Also, suppose that we know that removing that attractor of the maximum priority does not make progress (otherwise we handle this case as in Theorem 7 with a single recursive call). Now, before doing anything else we attempt to find a dominion that touches a small number of these modules. Specifically, for each set S ⊆ {1, . . . , k} such that |S| ≤ √ k we want to see if the current graph contains a dominion confined in ∪ j∈S M j . To see if such an i-dominion exists, for some i ∈ {0, 1}, we remove a (1 -i)-attractor of the set ∪ j ∈S M j and recursively solve the remaining graph using Theorem 7. The complexity of this step is dominated by trying all sets S, and is therefore k O( √ k) . If the above step finds a dominion, we remove it from the graph using Fact 2 and repeat the process. Otherwise, we run an iteration of McNaughton's algorithm, knowing that the second recursive call (if made) will touch at least √ k modules. The complexity is therefore given by the recurrence

T (n, k) ≤ k O( √ k) + T (n, k -1) + T (n, k - √ k)
. This is the same recurrence as in Theorem 2.

Corollary 3. There exists a k O( √ k) n O (1) algorithm that decides parity games on graphs with modular width k.

Hardness Results

Finding Dominions

In this section we consider the parameterized complexity of the following problem: given an instance of parity games, does there exist a dominion consisting of at most k vertices? This problem arises very naturally in the course of examining the sub-exponential time algorithm given in [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF]. The first step of this algorithm is to look for a "small" dominion, that is, a dominion that has size k, where k is a parameter to be optimized. The approach proposed in [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF] is simply to try out all n k sets of vertices of size k and solve parity games on the resulting subgraph. Since solving parity games in a graph with k vertices can be done in time sub-exponential in k, the n k factor dominates the running time of this process. It is therefore natural to ask whether this can be sped up, which in turn would imply that a different value should be chosen for k to get the best worst-case bound on the algorithm. One could plausibly hope to try improving the running time to something like 2 √ n (from n √ n ) using such an approach.

Unfortunately, Theorem 9 establishes that improving significantly upon this brute force method is likely to be very hard. In particular, we give a parameterized reduction from Multi-Colored Clique, showing that finding a dominion of size at most k cannot be done in time n o( √ k) (under standard assumptions). Theorem 9. There is no algorithm which, given an instance of parity games decides if there exists a dominion on at most k vertices in time n o( √ k) , unless the ETH fails.

Proof. We will use the results given in [START_REF] Chen | On the computational hardness based on linear fpt-reductions[END_REF][START_REF] Chen | Strong computational lower bounds via parameterized complexity[END_REF], which show that Multi-Colored Clique cannot be solved in time O(n o(k) ) under ETH, by giving a quadratic fpt-reduction, i.e., the parameter of the constructed instance is quatratic in the parameter of the originial instance, from Multi-Colored Clique.

The reduction is from Multi-Colored Clique: we are given a graph G(V, E) with V partitioned into k independent sets and are asked if there exists a clique of size k. We construct a directed graph G (V , E ). We set

V = V ∪ E ∪ {1, . . . , k} ∪ {(i, j) | 1 ≤ i < j ≤ k}.
In other words, we create a vertex for each vertex and for each edge of the original graph, as well as a vertex for each color and each pair of colors.

We then add a directed edge from each vertex i, for i ∈ {1, . . . , k} to each vertex u that has color i in G. Similarly, for each (i, j) with 1 ≤ i < j ≤ k we add edges from (i, j) to the vertex representing (u, v) ∈ E where u, v have colors i, j in G respectively. For each vertex representing (u, v) ∈ E we add edges to the vertices representing u, v ∈ V . Finally, for each u ∈ V and for each (u, v) ∈ E we add edges from the vertices representing u and (u, v) to all i ∈ {1, . . . , k} and all (i, j), 1 ≤ i < j ≤ k. All vertices are given priority 1. Player 1 controls vertices i and (i, j) and player 0 the vertices corresponding to V ∪ E.

Of course, it is clear that player 1 wins everywhere in this game, since all priorities are odd. The question is if she can trap player 0 in a small dominion. We argue that there exists a dominion of size at most 2(k + k

2 ) if and only if G has a k-clique. The theorem then follows.

Suppose that G has a k-clique. Then the dominion for player 1 contains all her vertices, as well as the vertices corresponding to vertices and edges of the clique.

For the converse direction, suppose that player 1 has some dominion D in G . It must contain some vertices of player 0, therefore it must contain all vertices of player 1. For player 1 to construct a dominion she must select an out-neighbor of each vertex she controls, and since these vertices have disjoint out-neighborhoods a dominion of the presribed size can only exist if she selects exactly one out-neighbor for each of her vertices. This selection corresponds to a selection of k vertices and k 2 edges in the original graph. If one of the selected edges is incident on an unselected vertex in G, then D is not a dominion because player 0 could escape through the vertex representing that edge in G .

Rabin Games

A Rabin game is another type of infinite game played on a graph, which in some sense generalizes parity games. In this section we present a simple reduction which shows that the algorithmic results we have obtained for parity games are unlikely to be extendible to Rabin games. Viewed another way, this reduction shows that the restricted graph classes we have considered are still quite nontrivial.

First, let us define a Rabin game. We are again given a directed graph G(V, E), where V is partitioned into V 0 and V 1 , the vertices controlled by each player. In addition, we are given a set of k pairs (I i , F i ) ⊆ V × V . The winning condition is the following: Player 0 wins if there exists an i ∈ {1, . . . , k} such that the token visits I i infinitely often but only visits the vertices of F i a finite number of times. Otherwise, Player 1 wins.

Let us note that it is not hard to see that this game generalizes parity games. Given an instance of parity games with maximum priority p we can set I i = Pr -1 (2i) and F i = ∪ j≥i Pr -1 (2j + 1) for each i ≤ p/2. In fact, a more complicated reduction in the opposite direction is possible: it is known that parity games parameterized by the maximum priority p are FPT-equivalent to Rabin games parameterized by the number of winning conditions k [START_REF] Bjorklund | On fixed-parameter complexity of infinite games[END_REF]. Nevertheless, this reduction requires super-polynomial time to run. In the context of polynomial time solvability the two problems are quite different. While parity games are in NP∩coNP, Rabin games are NP-complete.

Our reduction is from Multi-Colored Clique. It is essentially a simple tweak of known reductions for parity games (see e.g. the reduction in [START_REF] Bjorklund | On fixed-parameter complexity of infinite games[END_REF]). The new feature is that we are careful that the graph produced has some very restricted structure. Below, we will say that a vertex is non-trivial if its outdegree is more than 1.

Theorem 10. There is a polynomial-time reduction from Multi-Colored Clique to Rabin games which produces an instance G(V, E) with the following properties:

• G can be turned into a DAG by deleting one vertex.

• G has modular width 2k + 1.

• Player 0 controls k non-trivial vertices.

• Player 1 controls 1 non-trivial vertex.

Proof. Recall that Rabin games, unlike parity games, are not symmetric. If Player 0 has a winning strategy, she also has a positional winning strategy. However, the same is not true for Player 1, who may have a winning strategy that alternates the out-going arc selected from a vertex between rounds [START_REF] Bjorklund | On fixed-parameter complexity of infinite games[END_REF].

Let G (V , E ) be an instance of Multi-Colored Clique. We construct an instance of Rabin games as follows. First, V = V ∪ {1, . . . , k} ∪ {s}. We have arcs (s, i) for all i ∈ {1, . . . , k}. For each i ∈ {1, . . . , k} we also have all arcs from the vertex i to all vertices of V with color i. Finally, all vertices of V have an out-going arc to s. Vertex s is controlled by Player 1, while vertices i ∈ {1, . . . , k} are controlled by Player 0. The remaining vertices have out-degree 1, so their owner is irrelevant.

Let us also define the winning conditions. For each u ∈ V we define I u = {u} and F u = V \ N (u), that is, for each vertex u of the original graph Player 0 can win by visiting u infinitely often, provided she refrains from visiting its non-neighbors.

It is not hard to see that the graph satisfies the claimed properties. Let us therefore establish correctness. First, suppose there exists a multi-colored clique of size k in the original graph. Player 0 has the following positional strategy: for each vertex i she selects the outgoing arc that leads to the vertex of the clique. Then, for any strategy of Player 1, some vertex of V will be visited infinitely often without visiting any of its non-neighbors.

Conversely, suppose that Player 0 has a winning strategy, which must be positional. Consider the vertices of V which are the heads of the out-going arcs selected in this strategy. We argue that they must be a clique. For contradiction, suppose that two of them u, v are not connected, and they have colors i 1 , i 2 . Then Player 1 would be able to counter the strategy of Player 0 by alternating his moves as follows: each time the token arrives at s it is pushed either to i 1 or to i 2 . In this case, the only vertices visited infinitely often would be {s, i 1 , i 2 , u, v}, which would mean that Player 1 wins.

Theorem 1 .

 1 [START_REF] Mcnaughton | Infinite games played on finite graphs[END_REF] McNaughton's algorithm solves parity games in time O * (n p ).

Theorem 2 .

 2 [START_REF] Jurdzinski | A deterministic subexponential algorithm for solving parity games[END_REF] The algorithm of Jurdzinski, Paterson and Zwick solves parity games in time n O( √ n) .

k 2 [k k 2 [

 22 A(n, p, k/2) + O(n a )]. If we find a dominion D intersecting S, we solve recursively in time A(n, p, k -1) + O(n a ) an instance where at least one element of S is removed. If no dominion is found, then the first recursive call takes time A(n, p -1, k) + O(n a ). After that, either S is reduced by k 2 and the second recursive call takes time A(n, p, k/2) + O(n a ), or one of the players is left with no more than k vertices, which by Theorem 4 shall take time 4 k p log k O(n c ) to solve. So, overall we have: A(n, p, k) ≤ 2 A(n, p, k/2) + O(n a )] + max{A(n, p, k -1), A(n, p -1, k) + max{A(n, p, k/2), 4 k p log k O(n c )}} + O(n a ) This recursive function can be proven inductively to be ≤ 4 k p log k+1 O(n d ) for sufficiently large values of n, p, k, d. Most computations are similar to Lemma 2 and perhaps what remains is to prove the following part of the inductive step: For p, k > 4, d ≥ c and sufficiently large n:

As usual in parameterized complexity the O * (f (k))-notation, for some function f of the parameter k, means that there is an algorithm running in time O(f (k)n O[START_REF] Berwanger | The dag-width of directed graphs[END_REF] ), where n is the input size of the problem.

Acknowledgements

We would like to thank Danupon Nanongkai for suggesting this problem and for our useful discussions.

* Supported by the research centre Institute for Theoretical Computer Science (CE-ITI), project P202/12/G061 † Supported by ERC Starting Grant PARAMTIGHT (No. 280152) ‡ Supported by Employment of Newly Graduated Doctors of Science for Scientific Excellence (CZ.1.07/2.3.00/30.0009).


T Luft

G Lamé

J Ponn

J Stal-Le Cardinal

A Business Model Canvas for IDecide -How to Design a New Decision Making App?

Keywords: decision making, computer-aided decision making process, business model canvas, app, innovation process Value Proposition Customer Relationships Customer Segments Channels Cost Structure Revenue Streams

As products become increasingly complex, product developers have to make decisions effectively and efficiently. Therefore, the long term goal of the SIG DM is to develop an iDecide App. This app should support developers in complex decision making situations during the development process.

The aim of this paper is to describe possible business models for an iDecide App with the Business Model Canvas. Some business models and one industrial case study for an iDecide App are described. This should initiate an in-depth discussion on a detailed business model for an iDecide App.

Introduction

As products become increasingly complex and have to be developed in shorter development cycles, product developers have to make decisions effectively and efficiently [START_REF] Luft | A methodical approach to model and map interconnected decision making situations and their consequences[END_REF]. Decisions are made throughout the development and are crucial for the complete product lifecycle. They are taken in different situations in which multiple conflicting and complementing criteria must be considered. In this context, methods and tools can be used for making appropriate decisions. They shall primarily help to manage the cognitive workload of decision makers [START_REF] Roy | Decision science or decision-aid science?[END_REF]) and improve human decision making in a context in which rising information and requirements on products have to be considered.

Challenges in decision making

In general, decisions can be taken either consciously or unconsciously. The consciously made decisions can be further differentiated into purely intuitive decisions, improvised decisions and methodically supported decisions. With increasing importance and scope of the decision, a methodological support of the decision situation and the corresponding decision making process (e.g. for the objectification) is important. By using systematic evaluation methods, an objective basis for decision making can be [START_REF] Luft | A Business Model Canvas for iDecide -How to Design a New Decision Making App?[END_REF]. "A Business Model Canvas for iDecide -How to Design a New Decision Making App?" In Proceedings of DESIGN 2016. Cavtat, Dubrovnik, Croatia. 2 designed to minimize the risks of wrong decisions. This is especially relevant for decisions in the product development process, as wrong decisions often lead to very high subsequent costs. [START_REF] Ehrlenspiel | Integrierte Produktentwicklung: Denkabläufe, Methodeneinsatz, Zusammenarbeit[END_REF] state that decisions during product development can have far reaching consequences. While some decision situations are easy because their respective consequences can be identified with precision, other decision situations are characterised by complex steps and consequences which are difficult to predict [START_REF] Jupp | Dimensions of Decision Situations in Complex Product Development[END_REF]) [START_REF] Luft | A methodical approach to model and map interconnected decision making situations and their consequences[END_REF]. The basic principle is that with increasing complexity consequences are getting harder to anticipate and this leads to the need to support decision making processes methodically [START_REF] Bennet | The Decision-Making Process for Complex Situations in a Complex Environment[END_REF]) and with computer assistance (e.g. an app).

Therefore, a decision maker needs not only to make decisions serving his own goals, but to take into consideration the effects a decision has on further steps in the development of the product or on its later use. A "Rubik's cube" represents a good abstraction of this situation. The aim of gaining homogenous colours on each side of the cube represents a complex goal while the single sides of the cube represent several sub-goals that have to be solved in order to complete the overall task. The process of evaluating which side to twist in which direction as well as the actual twist represents one decision making process. Thereby, one side of the cube represents the perspective of one decision maker, while the other sides represent perspectives of other decision makers. To recognize the decision perspectives of other stakeholders, the regarded decision maker has to turn the cube to take a look onto the other sides. A remarkable fact is that one side of the cube can be homogenous while the others are still heterogeneous. Consequently, optimizing the own sub-goal (one homogenous side) does not necessarily lead to a solution of the overall goal (all sides are homogenous). Therefore, the consequences resulting from a twist of the cube have to be examined in regard to the other sides of the cube as well, as all sides are interconnected [START_REF] Luft | A methodical approach to model and map interconnected decision making situations and their consequences[END_REF].

When transferring the model of the Rubik's cube to a development process, the cube is representing the task of developing a complex product, which has to be modified and defined more closely. While a Rubik's cube works relatively simple and follows clear rules, a cube representing the development of a complex product would have numerous sides, while rules, if they are possible to define at all, are far more complicated. In a development environment, layers can be twisted due to outside forces that cannot be controlled (e.g. environmental changes). A twist cannot always be reversed and effects of twists sometimes occur with time delay [START_REF] Luft | A methodical approach to model and map interconnected decision making situations and their consequences[END_REF]. Moreover, the perspectives of other involved decision makers cannot always be viewed as they might be unknown. The fulfilment of one sub-goal can negatively influence a later goal (Luft et al. 2013c), sometimes due to a lack of knowledge about these goals. While some goals can be fulfilled without negative side-effects onto following goals, others bear consequences that have to be regarded. The challenge is to identify these potentially critical situations. Once identified, the decision situations need to be structured and analysed to understand how negative consequences can be controlled and reduced (Luft et al. 2013c).

A widespread example of the problem is the timewise difference of determination of costs and their actual occurrence. Hence, thoughtful decision making is especially important during product planning and development (compare Luft et al. 2013b), due to the fact that in average seventy percent of all costs are determined during these phases of the products lifecycle. Decision making is supposed to be done faster while being exposed to a rising degree of complexity. This complexity can be managed by distributing tasks among an increasing number of decision makers who are experts in their domain. [START_REF] Luft | A Business Model Canvas for iDecide -How to Design a New Decision Making App?[END_REF]. "A Business Model Canvas for iDecide -How to Design a New Decision Making App?" In Proceedings of DESIGN 2016. Cavtat, Dubrovnik, Croatia. 3 While these tasks represent the stated sub-goals (sides of the Rubik's cube), another problem occurs. In many cases, sub-goals affect and contradict each other. The problem that can be derived is that the apportioned sub-goals can potentially contradict each other and trigger unwanted consequences that might remain unnoticed until they appear.

Objectives of the Special Interest Group Decision Making and this paper

In order to reach the overall goal, mutually influencing aspects have to be considered and adjusted. Thus, to meet the technical requirements for a product (i.e. engineering perspective), for example, the most exclusive materials and production processes can be used to reach technical sub-goals. However, this contradicts another sub-goal that usually has to be met from an economical perspective. The product has to be produced and sold by obtaining a certain profit margin. In case of this example, the product might get too expensive to be sold. As a result, the developed product fulfilled the technical sub-goals but it did not reached the economical sub-goals and therefore the overall goal of the company is not achieved.

That is the reason why the authors have elaborated during the past Special Interest Group Decision Making (SIG DM) workshops the methodological and conceptual foundation for a systematic and interdisciplinary decision making process (section 2). It turned out that the task of the decision making needs to be supported not only methodologically but also through the use of IT tools (e.g. more data and information has to be collected and analyzed) (see Luft et. al. 2013a). Therefore, the long term goal of the authors is to develop an iDecide App for a computer-aided evaluation and decision making process. This app should support product developers in complex decision making situations (see [START_REF] Luft | A methodical approach to model and map interconnected decision making situations and their consequences[END_REF] regarding the aforementioned challenges (section 1.1) during the development process.

The aim of this paper is to describe some possible use cases and business models for an iDecide App with the help of the Business Model Canvas (BMC). The BMC is a method for elaboration and discussion of business models. Some BMCs for an iDecide App have been developed during the last SIG DM workshop. After a short description of some backgrounds and the presentation of the BMC (section 3), some preliminary results and case studies are described (section 4). This should initiate an in-depth discussion on a detailed business model and application area for an iDecide App for decision making in (engineering) design practice.

Background information on past workshops 2.1. Context of the project

The SIG DM regularly organizes workshops during conferences endorsed by the Design Society. In these workshops, presentations by researchers alternate with group work and discussions on topics related to decision making in design. The topics in the past four years have been the following:

 At DESIGN 2012, two workshops took place respectively on scientific decision making approaches and on types of decision making and their connection.

 This discussion continued during the workshop in Paris (March 2013) with a focus on uncertainty in decision-making and validation of decision-making approaches.

4

 At ICED 2013, the subject of interdependencies between strategic and operational design decisions was tackled, as well as the characterization of decision making situations.

 At DESIGN 2014, design methods to reduce decision complexity have been discussed in detail.

The emphasis was also on creativity methods and specific criteria to evaluate results.

The workshop, which is described in in this paper, took place during ICED 2015 in Milano. After methodological issues debated in the previous workshops, the workshop in Milano was more actionoriented. It stems from two facts. First, that decision making is a universal issue. Secondly, that mobile apps are nowadays a common and practical way to implement a wide range of tools. Market analysis form Gartner forecasts 268 billion app downloads in 2017. Some decision making apps are already available, with names such as Choicemap, Decision Buddy and Best Decision. However, the backstage mechanism in these apps, which weighs options or suggests favourable choices, is usually not clearly laid out. Therefore, it is difficult to evaluate these apps scientifically.

Consequently, during the workshop, participants were proposed to work on an app for decision making: the iDecide App. The idea was to start from scratch: a name, and a very broad requirement "an app for decision-making". The aim of the project is twofold. The first objective is on the actual product of the workshop: to come up with an actual concept for an app and to show how scientific knowledge on decision making can be implemented in a practical, user-friendly, universal tool. Besides this objective, there was also great interest in the process: to study the way participants build their proposition as a design project. A design method was provided: the BMC. The use of BMC for early design stages was evaluated after the workshop by the authors.

Processes and workshop done

In practice, the workshop was organized in the three-hour slot for SIG meetings of ICED 2015. Twelve people participated in the SIG DM workshop. There were four organizers, who intervened as little as possible in the work of the teams (only to precise or reformulate some tasks). The workshop was organized in three parts: an introductory part and two group works each with a presentation and short discussion at the end.

The introductory session lasted 30 minutes. In this first part, the organizers and the participants presented themselves. The objectives of the workshop were explained. Finally, the BMC was presented. At the end of the presentation of the BMC, the participants were asked a few questions to guide their work. The questions and tasks were exactly the following:  Who will be or could be the users of the iDecide App?  Examples of decisions which could / should be made with the iDecide App!  Needs and requirements regarding the iDecide App!  Collection of information about existing decision making process models!  Collection of ideas regarding new decision making processes!  Key and crucial steps within the decision making process! Then, participants were split in three groups of four people. Each group worked on a BMC template to provide a first concept of an iDecide App for 30 minutes. Then, they presented their proposition to the whole class (60 minutes). In this first part, groups filled the nine dimensions of the BMC. Pictures of 5 the three different BMC were taken for documentation and analysis purposes. In the third part, groups focused on the core of the BMC, the value proposition. They were not given specific instructions or format. They worked freely for 50 minutes, and 20 minutes were necessary to present the results of the three groups. Here again pictures were taken to record the proposition of each group.

Business Model Canvas and Decision Making

Presentation of the Business Model Canvas

In 2010, Alexander Osterwalder presented the Business Model Canvas, a new method which aimed at helping start-ups to find their business model as fast as possible. It is simply composed of nine boxes organised in a logical way in which hypothesis are laid down [START_REF] Osterwalder | Business model generation: a handbook for visionaries, game changers, and challengers[END_REF].

The job is then to "go out of the building", as Steve Blank says (2013), and find out if these hypothesis are valid or not. The start-up can then easily adjust, change and pivot around its business model until it finds a product/market fit.

The Business Model Canvas, presented in figure 1, is centred around its principal box, the Value Proposition (VP), in which is described the problem to be solved, the customer needs satisfied and the value delivered to the customers. The right part of the Business Model Canvas concerns the customers.

On the far right, the Customers Segments are described, the most important customers targeted by the VP. Then, between the Customers Segments and the VP is the Customer Relationships box. For a start-up, the different steps are: includes what the customer wishes to accomplish, independently of the product or service. Those jobs can be functional, social or emotional. On the circle top left, his "Gains" are listed: why the customer wants those jobs to be done, what is he looking for, dreaming about. On the bottom, his "Pains" are described: why his experience of having these jobs done is not going smoothly, the difficulties, fears or risks he encounters. On the left part of the VP triangle, the "Products & Services" are described: what do they do? On the top, the "Gains Creators" present savings that make the customer happy or outcomes that the customer expects or that go beyond his expectations. On the bottom, the "Pain Relievers" present how the products & services eliminate risks the customer fears or put an end to difficulties the customer encounters.

First concepts for the iDecide App

The following section describes some concepts for an iDecide App. These concepts emerged during and after the past SIG DM workshop. In section 4.1, the rough business model for the iDecide App is presented by using the BMC. The next section explains the general possible functionality or the 7 procedure of the iDecide App (section 4.2). Thereafter, we present two industrial use cases for an iDecide App. The first use case sums up the concept decision regarding an electric car (section 4.3) and the second use case explains the concept decision regarding a motor (section 4.4).

The Business Model Canvas for the iDecide App

Within the workshop, three groups worked on the development of a BMC. The BMC has been used to analyse an iDecide App that will be developed in the future. The following Figure 4 shows how this analysis could look like. In the case of the iDecide App, the value proposition is generated through channels (e.g. websites, app stores) and should help the customers to ask appropriate questions, make the best suited decision or even find the right decision making model. Therefore, within the BMC there could be easily described new or existing business models. This description is used as a basis for decision making processes.

As it could be seen in the business model, the iDecide App should mainly be designed for employees in the industrial sector. Especially for project managers and design engineers within a product development process. The app should help with decision making processes in the product or service design development, so for example the project leader could use it to communicate with his team and it could help to assess the different options and even to analyse the final results.

Procedure of the iDecide App

Furthermore, in the workshop there came up ideas how the app could work based on decision making models and processes (compare Figure 4). After defining the decision making task, the evaluation team must be set up. An advantage of the app is that the members of the team do not have to stay at the same time at the same place. Instead, they could communicate and share their information by using the iDecide App. For instance, if the project leader has to make a decision on a new product to be developed, it is possible to define the task in the app and send it to the related evaluator. In addition, the app has to give the possibility to define options and criteria for the decision making process. For this, the BMC is used as a basis. The BMC includes information regarding different channels or customer segments, which are defined by the team. In the next step, the team has to evaluate the various options with regard to the previously defined criteria. In the last step, the project team has to analyse and interpret the results. Subsequently, the project leader or the team members have to decide and have to choose one option. The picture (Figure 4) shows the process how the app could probably work.

Industrial Use Case: Concept Decision Electric Car

The following BMC of the business case "development of an electric car" (Figure 5), which has been created after the workshop, could be the basis of for a decision making process. The task could be the decision between selling the technology and protecting the technology and selling the final product. This concerns the BMC-box "revenue streams". First, the task has to be defined. Two alternative strategies of revenue streams are generally possible: the selling the technology and the protecting the technology and selling the final product.

The next step is the definition of an evaluation team that discusses the two different options regarding several criteria that have to be defined before. These steps could be done without a meeting of the involved persons. The team can communicate and share information by using the iDecide App. The evaluation criteria could be, for example, expected costs, risks, revenue or even market penetration (Figure 6). The iDecide App supports the team in this step by providing a structured platform for communicating, analysing and presenting different options and criteria, for example, in a chart.

The assessment of the different options could be done with a numerical scale or even a pairwise comparison. The iDecide App supports this step by suggesting proper evaluation methods. In this case, the evaluation is done with a numerical scale from 1 to 10, while 1 means "low" and 10 means "high" (see Figure 7). The final step is the analysis and interpretation of this evaluation chart. This process can be run automatically by the iDecide App. Subsequently, the iDecide App presents the analysed data in a graph or another form that could be easily interpreted by decision makers (Figure 7). In this case, the decision would be made for protecting the technology because only the costs were assessed worse in comparison to selling the technology. The example shows how the iDecide App could support a team in a decision making process. Indeed, the iDecide App takes not the final decision regarding the options considered.

Industrial Use Case: Concept Decision for Motor

The possible application of the iDecide App is now illustrated in an exemplary industrial use case. A company providing products, systems and solutions for construction professionals has started a development project for a new rotary hammer. This rotary hammer is one of many products featuring an electric platform drive. Typical challenges regarding this kind of development setup especially concerning portfolio decision making processes are described in [START_REF] Ponn | Portfolio Management for Electric Drives in Powertools at Hilti: Challenges and Solution Approaches[END_REF]. 11 At a certain phase in the project, a concept decision for the motor is needed. The project leader initiates the decision making process by sending a list of relevant decision criteria via the app to the rest of the members of the core team (marketing, development, testing and supply). There are six criteria: performance, robustness, size, weight, cost and availability. Each team member is asked to nominate the three most important criteria from the list. By adding up all points a weighting of the decision criteria can be calculated by the app.

Three different motor concepts are regarded as options in the scope of this decision.

 Concept 1 is based on an existing motor technology that is characterized by its low cost. The technology is used in many other products and is readily available.

 Concept 2 is also based on an existing motor technology. However the motor is a bit more compact and has less weight compared to concept 1 at a slightly higher cost. Some adaptation efforts are necessary, therefore a certain development time is required.

 Concept 3 is based on a new motor technology. It features a significantly higher performance and robustness at higher cost. Due to its novelty, major development efforts are necessary to bring the technology to serial maturity.

The assessment of the considered concepts is carried out by rating each concept (1-4 points for each concept and criterion, whereas 1 means that the criterion is fulfilled poorly and 4 means that the criterion is fulfilled well). The project leader sends messages via the iDecide App to certain team members, which are able to conduct the rating due to their field of expertise in the project. The testing engineer delivers the values for the criteria performance and robustness, based on relevant tests. The development engineer delivers the rating for size and weight. The supply manager gives an estimation on cost and lead time. The iDecide App leads the team through the process and combines all data into a summary of the assessment.

Finally, the team comes together to discuss the results and draw a conclusion. The team recommends pursuing concept 3 further because it provides the highest level of differentiation (high performance to weight and high robustness). The higher cost and long development time are judged as acceptable. DESIGN 2016. Cavtat, Dubrovnik, Croatia. 12 This use case gives an impression how an iDecide App might support a development team in the decision making process. Major benefits are:

 Reduction of complexity: with the help of the App the process is broken down into "digestible" steps. The App guides the team through the process. Results can be displayed in a clearly arranged format that serves as common basis for the discussion in the team.

 Increase of efficiency: the App helps to reduce the required effort. The workflow of the decision process is embedded in the app. The collection of data is triggered by messages to the relevant team members. The input from each team member is collected and processed in an efficient way.

 Increase of motivation: the App creates an interactive process with a certain "fun aspect" that increases the motivation of the team members to participate in the process.

Conclusion

Contribution and conclusion

Finally, the authors and the participants of the last SIG DM workshop concluded, that an iDecide App is one valuable and user-friendly tool for a systematic and computer-aided support of decision making tasks during product development. Consequently, the long-term goal of the authors is the development of an iDecide App for a computer-aided evaluation and decision making process. This app should support product developers and managers in complex decision making situations (cf. [START_REF] Luft | A methodical approach to model and map interconnected decision making situations and their consequences[END_REF]. The main advantages of an iDecide App are the reduction of the complexity, an increase of the efficiency, transparency and objectivity as well as a higher motivation of the user.

Limits and future work

Some business models for such an iDecide App are described with the help of the BMC method in this paper. We have shown that the BMC is very appropriate for the early steps of the development of the first concepts for an app. However, these concepts need to be further developed and redefined. Thereby, we will also include the current state of the art in the field of expert systems and application of artificial intelligence in decision making processes. In addition, it is also very important to get feedback from industry representatives and potential users. This allows conceptualizing the app right from the start for the needs and requirements of future decision makers. The authors and interested researchers will be working in the future on these tasks.

Figure 1

 1 Figure 1 Business Model Canvas from Osterwalder & Pigneur (2010)3.2. Proposition of a Business Model Canvas for a new application helping decision makingIn 2014,[START_REF] Osterwalder | Value proposition design: how to create products and services customers want, Strategyzer series[END_REF] presented the VP Canvas to help start-ups build their VP, which can be the hardest part of the Business Model Canvas. It is composed of a circle representing the customer (on the right of figure2) and of a triangle (on the left), which represent the VP, each of them are divided in three parts. The field "Customer Jobs" includes what the customer wishes to accomplish, independently of the product or service. Those jobs can be functional, social or emotional. On the circle top left, his "Gains" are listed: why the customer wants those jobs to be done, what is he looking for, dreaming about. On the bottom, his "Pains" are described: why his experience of having these jobs done is not going smoothly, the difficulties, fears or risks he encounters. On the left part of the VP triangle, the "Products & Services" are described: what do they do? On the top, the "Gains Creators" present savings that make the customer happy or outcomes that the customer expects or that go beyond his expectations. On the bottom, the "Pain Relievers" present how the products & services eliminate risks the customer fears or put an end to difficulties the customer encounters.

Figure 2

 2 Figure 2 Value Proposition Canvas from Osterwalder et al. (2014)

FigureFigure 4

 4 Figure 3 Brief BMC for a generic iDecide App

Figure 5

 5 Figure 5 First results from a group for a concept decision regarding an electric car

Figure 6 Figure 7

 67 Figure 6 Different criteria and options

Figure 8

 8 Figure 8 Use case motor concept decision: task, team and criteria

Figure 9

 9 Figure 9 Use case motor concept decision: options and assessment

  [START_REF] Luft | A Business Model Canvas for iDecide -How to Design a New Decision Making App?[END_REF]. "A Business Model Canvas for iDecide -How to Design a New Decision Making App?" In Proceedings ofDESIGN 2016. Cavtat, Dubrovnik, Croatia.

  [START_REF] Luft | A Business Model Canvas for iDecide -How to Design a New Decision Making App?[END_REF]. "A Business Model Canvas for iDecide -How to Design a New Decision Making App?" In Proceedings ofDESIGN 2016. Cavtat, Dubrovnik, Croatia.

  [START_REF] Luft | A Business Model Canvas for iDecide -How to Design a New Decision Making App?[END_REF]. "A Business Model Canvas for iDecide -How to Design a New Decision Making App?" In Proceedings ofDESIGN 2016. Cavtat, Dubrovnik, Croatia.

Acknowledgements

The authors would like to thank all the participants of the SIG DM workshop at ICED 2015 in Milano.