Take a linear minion \({{M}}\)  and two digraphs \(\mathbf {X}\)  (the instance) and \(\mathbf {A}\)  (the template). The relaxation corresponding to \({{M}}\)  outputs \(\textsc {Yes}\)  if \(\mathbf {X}\rightarrow \mathbb {F}_{{{M}}}(\mathbf {A})\)  and \(\textsc {No}\)  otherwise.In [1]}, this relaxation was described as the “minion test” associated with \({{M}}\) .
For certain linear minions, the problem of deciding whether \(\mathbf {X}\rightarrow \mathbb {F}_{{{M}}}(\mathbf {A})\)  can be solved in polynomial time (in the size of the input \(\mathbf {X}\) ) for any \(\mathbf {A}\) . In particular, this is the case for the linear minions \({{Q}_{\operatorname{conv}}}\)  and \({{Z}_{\operatorname{aff}}}\)  from Example REF , which, as shown in [2]},
correspond to the polynomial-time relaxations \(\operatorname{BLP}\)  and \(\operatorname{AIP}\) , respectively.
