mds $D$ compute the set $\Omega$ of weight functions to check \[alg:xp\_algorithm-line:compute\_omega\] compute $t_{\omega}=\sum_{v\in D}{\omega}(v)$ \[alg:xp\_algorithm-line:compute\_t\] compute an arbitrary $S\in\mathcal{S}_{\omega}(x)$ \[alg:xp\_algorithm-line:compute\_S\] \[alg:xp\_algorithm-line:sum1\] **next** ${\omega}$ \[alg:xp\_algorithm-line:sum2\] **next** ${\omega}$ return $({\omega},t_{\omega})$ return **NO**

Let $(P_1,\ldots,P_s)$ be the partition of $V$ into pseudo classes (note that $s\leq k$, otherwise $G$ is not $k$-equidominating). We define an equivalence relation on the set of weight functions as follows: $${\omega}_1 \sim {\omega}_2 :\Longleftrightarrow \forall j \in [s] ~ \forall i \in [k]\colon  |{\omega}_1^{-1}(i)\cap P_j|=|{\omega}_2^{-1}(i)\cap P_j|\,.$$ In simple terms two weight functions are equivalent if they assign each weight to the same number of vertices within every pseudo class. It is easy to verify that either all functions of an equivalence class are $k$-equidominating functions or none. That means we only have to check one representative per equivalence class.

Following Corollary \[cor:differentpseudodifferentweights\] it is a necessary condition for every equidominating function that elements of different pseudo classes have different weights. Let $(v_1,\ldots,v_n)$ be an fixed ordering of $V$ in which vertices of the same pseudo class appear sequentially. We define $\Omega$ to be the set of all weight functions ${\omega}\colon V \rightarrow [k]$ for which the weights also appear consecutively in the weight vector $({\omega}(v_1),\ldots,{\omega}(v_n))\in [k]^n$ and 