The \(\operatorname{BA}\)  hierarchy we consider in this work consists in applying the \(\operatorname{BA}\)  relaxation of [1]} to progressively larger portions of the instances, in the same spirit as the \(\operatorname{BLP}\)  and \(\operatorname{AIP}\)  hierarchies. Equivalently, the \(\operatorname{BA}\)  hierarchy can be described as follows: Its \(k\) -th level, applied to two digraphs \(\mathbf {X}\)  and \(\mathbf {A}\) , outputs \(\textsc {Yes}\)  if and only if \((i)\)  the \(k\) -th level of both \(\operatorname{BLP}\)  and \(\operatorname{AIP}\)  outputs \(\textsc {Yes}\)  when applied to \(\mathbf {X}\)  and \(\mathbf {A}\) , and \((ii)\)  the two solutions they provide satisfy the refinement condition. In this case, we write \(\operatorname{BA}^k(\mathbf {X},\mathbf {A})=\textsc {Yes}\) . Given two digraphs \(\mathbf {A},\mathbf {B}\)  such that \(\mathbf {A}\rightarrow \mathbf {B}\) , we say that the \(k\) -th level of \(\operatorname{BA}\)  solves \(\operatorname{PCSP}(\mathbf {A},\mathbf {B})\)  if, for any instance \(\mathbf {X}\) , \(\operatorname{BA}^k(\mathbf {X},\mathbf {A})=\textsc {Yes}\)  implies \(\mathbf {X}\rightarrow \mathbf {B}\) .
