weight functions that differ only by switched weights for two vertices of one pseudo class, can be handled as the same. This leads to equivalence classes of weight functions. Further, we reduce the running time from a brute force algorithm by classifying subsets of vertices. It does not matter, for example, which vertex of a clique class is in an mds. Then, we have to check only one subset per class for being an mds.

For a given $k\in{\ensuremath{\mathbb{N}}}$ it is decidable if a graph $G=(V,E)$ with $|V|=n$ and $|E|=m$ is $k$-equidominating or not in time $\mathcal{O}\left(nm^2 + n^kk^k + n^{2k+2}k^{-k-1} + k^{3k+3}\right)$ and a $k$-equidominating structure is computed in this time. Further, for $t\in{\ensuremath{\mathbb{N}}}$ the same algorithm can be used to decide if $G$ is target-$t$ equidominating.

We first discuss how the algorithm works and calculate its running time afterward. There are $k^n$ different weight functions from $V$ to $[k]$ we would have to test and $2^n$ potential mds. As we will see, we can reduce both numbers using the pseudo classes.

determine pseudo classes $P_1,\ldots P_s$ by computing the twin partition and identifying clique bundles and stable set bundles via Algorithm \[alg:adjacentmdsexchangeable\] \[alg:xp\_algorithm-line:pseudoclasses\] return **NO** compute an arbitrary 