$v_{2}=i\frac{\tilde{\lambda}_{2}}{X}$, $v_{4}=-iY$, and
$w_{1}=Y\frac{\tilde{\lambda}_{1}}{X}$,
$w_{2}=Y\frac{\tilde{\lambda}_{2}}{X}$, $w_{4}=1$. We use these eigenvectors
to construct the Unitary matrix U to diagonalize the mixing matrix M’ by
unitary transformation. The constructed Unitary matrix is given as follows:

$\scriptsize{\bf
U}=\left(\begin{array}[]{cccc}-\frac{1}{d_{1}}\sqrt{1-\xi_{1}^{2}}\rm{\cal{N}}^{(1)}_{vn}&\hskip
2.84544pt-\frac{1}{d_{2}}\sqrt{1-\xi_{2}^{2}}\rm{\cal{N}}^{(2)}_{vn}&\hskip
2.84544pti(\frac{\xi_{1}}{d_{1}}+\frac{\xi_{2}}{d_{2}})\rm{\cal{N}}^{(3)}_{vn}&0\\\
\frac{v_{1}}{d_{1}}\sqrt{1-\xi_{1}^{2}}\rm{\cal{N}}^{(1)}_{vn}&\hskip
2.84544pt\frac{v_{2}}{d_{2}}\sqrt{1-\xi_{2}^{2}}\rm{\cal{N}}^{(2)}_{vn}&\hskip
2.84544pt-i(\xi_{1}\frac{v_{1}}{d_{1}}+\xi_{2}\frac{v_{2}}{d_{2}}+\xi_{4}\frac{v_{4}}{d_{4}})\rm{\cal{N}}^{(3)}_{vn}&\frac{v_{4}}{d_{4}}\sqrt{1-\xi_{4}^{2}}\rm{\cal{N}}^{(4)}_{vn}\\\
-i\xi_{1}\rm{\cal{N}}^{(1)}_{vn}&\hskip
2.84544pt-i\xi_{2}\rm{\cal{N}}^{(2)}_{vn}&\hskip
2.84544pt\sqrt{1-\xi_{1}^{2}-\xi_{2}^{2}-\xi_{4}^{2}}\rm{\cal{N}}^{(3)}_{vn}&-i\xi_{4}\rm{\cal{N}}^{(4)}_{vn}\\\
\frac{w_{1}}{d_{1}}\sqrt{1-\xi_{1}^{2}}\rm{\cal{N}}^{(1)}_{vn}&\frac{w_{2}}{d_{2}}\sqrt{1-\xi_{2}^{2}}\rm{\cal{N}}^{(2)}_{vn}&\hskip
2.84544pt-i(\xi_{1}\frac{w_{1}}{d_{1}}+\xi_{2}\frac{w_{2}}{d_{2}}+\xi_{4}\frac{w_{4}}{d_{4}})\rm{\cal{N}}^{(3)}_{vn}&\frac{w_{4}}{d_{4}}\sqrt{1-\xi_{4}^{2}}\rm{\cal{N}}^{(4)}_{vn}\end{array}\right)$
(S145)

Variables introduced in (S145) are defined as;
$\xi_{i}=\frac{Lw_{i}}{d_{i}(\lambda_{3}^{0}-\lambda_{i}^{0})}$ ($i$ can take
values 1,2,4). Here, uj, vj ,wj and xj are the components of the $j^{th}$
column vectors of U, and

$\rm{\cal{N}}^{(j)}_{vn}=\frac{1}{\sqrt{[|u_{j}|^{2}+|v_{j}|^{2}+|w_{j}|^{2}+|x_{j}|^{2}]}}$

is the corresponding normalisation constant ($j=1,2,3,4$).

###  14.2 Field equation : Solutions

To get the solution of the coupled equation (S139), we multiply the same by
U-1 , hence:

${\bf{U}}^{-1}\left[\begin{array}[]{c}k^{2}{\bf I}-{\bf
M^{\prime}}\end{array}\right]{\bf{UU}}^{-1}\left(\begin{array}[]{c}A_{\parallel}(k)\\\
A_{\perp}(k)\\\ A_{L}(k)\\\
\phi^{\prime}(k)\end{array}\right)=\left[\begin{array}[]{c}k^{2}{\bf I}-{\bf
M}_{D}\end{array}\right]\left(\begin{array}[]{c}A^{\prime}_{\parallel}(k)\\\
A^{\prime}_{\perp}(k)\\\ A^{\prime}_{L}(k)\\\
\phi^{\prime\prime}(k)\end{array}\right)=0,$ (S146)

$\displaystyle{\bf[C_{A,\phi^{\prime}}]}=\left[\begin{array}[]{c}A_{\parallel}(k)\\\
A_{\perp}(k)\\\ A_{L}(k)\\\ \phi^{\prime}(k)\end{array}\right]={\bf
U}\left[\begin{array}[]{c}A^{\prime}_{\parallel}(k)\\\
A^{\prime}_{\perp}(k)\\\ A^{\prime}_{L}(k)\\\
\phi^{\prime\prime}(k)\end{array}\right].$ (S155)

Following Raffelt , one can write partial of $k_{3}$(Fourier transform) for a
beam propagating in z direction, equation (S155) can further be written
explicitly in the form,

$\left[\begin{array}[]{c}(\omega-i\partial_{z})\mathbf{I}-\left[\begin{array}[]{cccc}\frac{\lambda_{1}}{2\omega}&0&0&0\\\
0&\frac{\lambda_{2}}{2\omega}&0&0\\\ 0&0&\frac{\lambda_{3}}{2\omega}&0\\\
0&0&0&\frac{\lambda_{4}}{2\omega}\end{array}\right]\end{array}\right]\left[\begin{array}[]{c}{A^{\prime}}_{\parallel}(z)\\\
{A^{\prime}}_{\perp}(z)\\\ A^{\prime}_{L}(k)\\\
{\phi^{\prime\prime}}(z)\end{array}\right]=0.$ (S156)

The solutions for the column vector ${\bf[C_{A,\phi^{\prime}}]}$, can be
written in matrix form as was performed in the scalar- photon case with the
introduction of the variables,
$\Omega_{\parallel}=\left(\omega-\frac{\lambda_{1}}{2\omega}\right)$,
$\Omega_{\perp}=\left(\omega-\frac{\lambda_{2}}{2\omega}\right)$
$\Omega_{L}=\left(\omega-\frac{\lambda_{3}}{2\omega}\right)$ and
$\Omega_{\phi^{\prime}}=\left(\omega-\frac{\lambda_{4}}{2\omega}\right)$,

$\left[\begin{matrix}{{A}_{\parallel}(z)}\cr{{A}_{\perp}(z)}\cr{{A}_{L}(z)}\cr{\phi^{\prime}(z)}\end{matrix}\right]={\bf
U}\left[\begin{array}[]{cccc}e^{-i\Omega_{\parallel}z}&0&0&0\\\
0&e^{-i\Omega_{\perp}z}&0&0\\\ 0&0&e^{-i\Omega_{L}z}&0\\\
0&0&0&e^{-i\Omega_{\phi^{\prime}}z}\end{array}\right]{\bf
U}^{-1}\left[\begin{matrix}{{A}_{\parallel}(0)}\cr{{A}_{\perp}(0)}\cr{{A}_{L}(0)}\cr{\phi^{\prime}(0)}\end{matrix}\right].$
(S157)

The elements of the column vector, $\left[{\bf A}(0)\right]$ appearing in
equation (S157), are the initial values whose magnitudes are subject to the
physical conditions considered at z = 0. For the boundary conditions for
pseudoscalar field, the solution of equation (S157) for A∥($\omega,{\bf z}$),
turns out to be:

$\displaystyle A_{\parallel}(\omega,z)$ $\displaystyle=$
$\displaystyle\left(e^{i\Omega_{\parallel}z}{\hat{u}}_{1}{\hat{u}}^{*}_{1}+e^{i\Omega_{\perp}z}{\hat{u}}_{2}{\hat{u}}^{*}_{2}+e^{i\Omega_{L}z}{\hat{u}}_{3}{\hat{u}}^{*}_{3}+e^{i\Omega_{\phi^{\prime}}z}{\hat{u}}_{4}{\hat{u}}^{*}_{4}\right)A_{\parallel}(\omega,0)$
(S158) $\displaystyle+$
$\displaystyle\left(e^{i\Omega_{\parallel}z}{\hat{u}}_{1}{\hat{v}}^{*}_{1}+e^{i\Omega_{\perp}z}{\hat{u}}_{2}{\hat{v}}^{*}_{2}+e^{i\Omega_{L}z}{\hat{u}}_{3}{\hat{v}}^{*}_{3}+e^{i\Omega_{\phi^{\prime}}z}{\hat{u}}_{4}{\hat{v}}^{*}_{4}\right)A_{\perp}(\omega,0)$
$\displaystyle+$
$\displaystyle\left(e^{i\Omega_{\parallel}z}{\hat{u}}_{1}{\hat{w}}^{*}_{1}+e^{i\Omega_{\perp}z}{\hat{u}}_{2}{\hat{w}}^{*}_{2}+e^{i\Omega_{L}z}{\hat{u}}_{3}{\hat{w}}^{*}_{3}+e^{i\Omega_{\phi^{\prime}}z}{\hat{u}}_{4}{\hat{w}}^{*}_{4}\right)A_{L}(\omega,0),$

and the component $A_{\perp}(\omega,z)$ turns out to be,

$\displaystyle A_{\perp}(\omega,z)$ $\displaystyle=$
$\displaystyle\left(e^{i\Omega_{\parallel}z}{\hat{v}}_{1}{\hat{u}}^{*}_{1}+e^{i\Omega_{\perp}z}{\hat{v}}_{2}{\hat{u}}^{*}_{2}+e^{i\Omega_{L}z}{\hat{v}}_{3}{\hat{u}}^{*}_{3}+e^{i\Omega_{\phi^{\prime}}z}{\hat{v}}_{4}{\hat{u}}^{*}_{4}\right)A_{\parallel}(\omega,0)$
(S159) $\displaystyle+$
$\displaystyle\left(e^{i\Omega_{\parallel}z}{\hat{v}}_{1}{\hat{v}}^{*}_{1}+e^{i\Omega_{\perp}z}{\hat{v}}_{2}{\hat{v}}^{*}_{2}+e^{i\Omega_{L}z}{\hat{v}}_{3}{\hat{v}}^{*}_{3}+e^{i\Omega_{\phi^{\prime}}z}{\hat{v}}_{4}{\hat{v}}^{*}_{4}\right)A_{\perp}(\omega,0)$
$\displaystyle+$
$\displaystyle\left(e^{i\Omega_{\parallel}z}{\hat{v}}_{1}{\hat{w}}^{*}_{1}+e^{i\Omega_{\perp}z}{\hat{v}}_{2}{\hat{w}}^{*}_{2}+e^{i\Omega_{L}z}{\hat{v}}_{3}{\hat{w}}^{*}_{3}+e^{i\Omega_{\phi^{\prime}}z}{\hat{v}}_{4}{\hat{w}}^{*}_{4}\right)A_{L}(\omega,0).$

###  14.3  Stokes parameters

For $\phi^{\prime}\gamma$ mixing, the Stokes parameter (I, Q, U and V) is
determined by the set of equations appearing in (71 \- 74) by using (S158) and
(S159). The variables introduced in (71) for the expression for Stokes
parameter I can be expressed as:

$\displaystyle I_{\parallel}$
$\displaystyle=\Big{[}1-4|{\hat{u}}_{1}{\hat{u}}_{2}|\mathbb{V}_{12}sin^{2}\left(\frac{(\Omega_{\parallel}-\Omega_{\perp})z}{2}\right)-4|{\hat{u}}_{2}{\hat{u}}_{3}\mathbb{V}_{23}sin^{2}\left(\frac{(\Omega_{\perp}-\Omega_{L})z}{2}\right)$
$\displaystyle\hskip
22.76228pt-4|{\hat{u}}_{3}{\hat{u}}_{1}|\mathbb{V}_{31}sin^{2}\left(\frac{(\Omega_{L}-\Omega_{\parallel})z}{2}\right)\Big{]}.$
(S160) $\displaystyle I_{\perp}$
$\displaystyle=\Big{[}1-4|{\hat{v}}_{1}{\hat{v}}_{2}|\mathbb{V}_{12}sin^{2}\left(\frac{(\Omega_{\parallel}-\Omega_{\perp})z}{2}\right)-4|{\hat{v}}_{2}{\hat{v}}_{3}|\mathbb{V}_{23}sin^{2}\left(\frac{(\Omega_{\perp}-\Omega_{L})z}{2}\right)$
$\displaystyle\hskip
22.76228pt-|{\hat{v}}_{3}{\hat{v}}_{1}|\mathbb{V}_{31}sin^{2}\left(\frac{(\Omega_{L}-\Omega_{\parallel})z}{2}\right)-4|{\hat{v}}_{3}|^{2}|{\hat{v}}_{4}|^{2}sin^{2}\left(\frac{(\Omega_{L}-\Omega_{\phi^{\prime}})z}{2}\right)$
$\displaystyle\hskip
22.76228pt-4|{\hat{v}}_{4}|^{2}|{\hat{v}}_{1}|^{2}sin^{2}\left(\frac{(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z}{2}\right)-4|{\hat{v}}_{2}|^{2}|{\hat{v}}_{4}|^{2}sin^{2}\left(\frac{(\Omega_{\perp}-\Omega_{\phi^{\prime}})z}{2}\right)\Big{]}.$
(S161) $\displaystyle\hskip 28.45274ptI_{L}$
$\displaystyle=\Big{[}(4|{\hat{w}}_{1}{\hat{w}}_{2}|\mathbb{V}_{12}sin^{2}\left(\frac{{(\Omega_{\parallel}-\Omega_{\perp})z}}{2}\right)+4|{\hat{w}}_{2}{\hat{w}}_{3}|\mathbb{V}_{23}cos^{2}\left(\frac{{(\Omega_{\perp}-\Omega_{L})z}}{2}\right)$
$\displaystyle\hskip
0.0pt+4|{\hat{w}}_{3}{\hat{w}}_{1}|\mathbb{V}_{31}cos^{2}\left(\frac{{(\Omega_{L}-\Omega_{\parallel})z}}{2}\right)+4|{\hat{v}}_{3}{\hat{v}}_{4}||{\hat{w}}_{3}{\hat{w}}_{4}|cos^{2}\left(\frac{{(\Omega_{L}-\Omega_{\phi^{\prime}})z}}{2}\right)$
$\displaystyle\hskip
0.0pt+4|{\hat{v}}_{4}{\hat{v}}_{1}||{\hat{w}}_{4}{\hat{w}}_{1}|sin^{2}\left(\frac{{(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z}}{2}\right)+4|{\hat{v}}_{2}{\hat{v}}_{4}||{\hat{w}}_{2}{\hat{w}}_{4}|sin^{2}\left(\frac{{(\Omega_{\phi^{\prime}}-\Omega_{\perp})z}}{2}\right)\Big{]}.$
(S162) $\displaystyle I_{\parallel\perp}$
$\displaystyle=\Big{[}2(|{\hat{u}}_{2}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|-|{\hat{v}}_{2}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|-|{\hat{u}}_{1}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|+|{\hat{v}}_{1}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|)\;sin({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle+2(|{\hat{u}}_{3}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|-|{\hat{v}}_{3}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|-|{\hat{u}}_{2}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|+|{\hat{v}}_{2}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|)\;sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+2(|{\hat{u}}_{3}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|-|{\hat{v}}_{3}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|-|{\hat{u}}_{1}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|+|{\hat{v}}_{1}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|)\;sin({(\Omega_{\parallel}-\Omega_{L})z})$
$\displaystyle+2|{\hat{v}}_{4}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|)\;sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})-2|{\hat{v}}_{4}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|)\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-2|{\hat{v}}_{4}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|)\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S163) $\displaystyle I_{\parallel L}$
$\displaystyle=\Big{[}2(|{\hat{u}}_{1}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{u}}_{2}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{2}{\hat{w}}_{2}|-|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{1}{\hat{w}}_{1}|)sin({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle-2(|{\hat{u}}_{2}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|+|{\hat{u}}_{3}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{3}{\hat{w}}_{3}|+|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{2}{\hat{w}}_{2}|)sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-2(|{\hat{u}}_{3}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{u}}_{1}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|+|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{1}{\hat{w}}_{1}|+|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{3}{\hat{w}}_{3}|)sin({(\Omega_{\parallel}-\Omega_{L})z})$
$\displaystyle+2|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{4}{\hat{w}}_{4}|)\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})-2|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{4}{\hat{w}}_{4}|)\;sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle+2|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{4}{\hat{w}}_{4}|)\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S164) $\displaystyle I_{\perp L}$
$\displaystyle=\Big{[}2(|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{u}}_{1}{\hat{w}}_{1}|-|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{v}}_{1}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|-|{\hat{v}}_{2}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|$
$\displaystyle+|{\hat{v}}_{3}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{v}}_{4}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|)+2(|{\hat{v}}_{4}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{v}}_{3}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|)\;cos({(\Omega_{L}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-2(|{\hat{v}}_{4}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{1}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|)\;cos({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle-2(|{\hat{v}}_{2}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|+|{\hat{v}}_{4}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|)\;cos({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-2(|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{u}}_{2}{\hat{w}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{1}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|+|{\hat{v}}_{2}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle+2(|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{u}}_{2}{\hat{w}}_{2}|+|{\hat{v}}_{2}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{v}}_{3}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|)cos({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+2(|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{1}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{v}}_{3}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{L})z})\Big{]}.$
(S165)

Also, the variables introduced in expressing the Stokes parameter Q, are
expressed as follows,

$\displaystyle Q_{\parallel}$
$\displaystyle=\Big{[}1-4|{\hat{u}}_{1}{\hat{u}}_{2}|\mathbb{\tilde{V}}_{12}sin^{2}\left(\frac{(\Omega_{\parallel}-\Omega_{\perp})z}{2}\right)-4|{\hat{u}}_{2}{\hat{u}}_{3}\mathbb{\tilde{V}}_{23}sin^{2}\left(\frac{(\Omega_{\perp}-\Omega_{L})z}{2}\right)$
$\displaystyle-4|{\hat{u}}_{3}{\hat{u}}_{1}|(\mathbb{\tilde{V}}_{31})sin^{2}\left(\frac{(\Omega_{L}-\Omega_{\parallel})z}{2}\right)\Big{]}.$
(S166) $\displaystyle Q_{\perp}$
$\displaystyle=\Big{[}1+4|{\hat{v}}_{1}{\hat{v}}_{2}|\mathbb{\tilde{V}}_{12}sin^{2}\left(\frac{(\Omega_{\parallel}-\Omega_{\perp})z}{2}\right)+4|{\hat{v}}_{2}{\hat{v}}_{3}|\mathbb{\tilde{V}}_{23}sin^{2}\left(\frac{(\Omega_{\perp}-\Omega_{L})z}{2}\right)$
$\displaystyle+4|{\hat{v}}_{3}{\hat{v}}_{1}|\mathbb{\tilde{V}}_{31}sin^{2}\left(\frac{(\Omega_{L}-\Omega_{\parallel})z}{2}\right)-4|{\hat{v}}_{3}|^{2}|{\hat{v}}_{4}|^{2}sin^{2}\left(\frac{(\Omega_{L}-\Omega_{\phi^{\prime}})z}{2}\right)$
$\displaystyle-4|{\hat{v}}_{4}|^{2}|{\hat{v}}_{1}|^{2}sin^{2}\left(\frac{(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z}{2}\right)-4|{\hat{v}}_{2}|^{2}|{\hat{v}}_{4}|^{2}sin^{2}\left(\frac{(\Omega_{\perp}-\Omega_{\phi^{\prime}})z}{2}\right)\Big{]}.$
(S167) $\displaystyle Q_{L}$
$\displaystyle=\Big{[}(4|{\hat{w}}_{1}{\hat{w}}_{2}|\mathbb{\tilde{V}}_{12}sin^{2}\left(\frac{{(\Omega_{\parallel}-\Omega_{\perp})z}}{2}\right)+4|{\hat{w}}_{2}{\hat{w}}_{3}|\mathbb{\tilde{V}}_{23}cos^{2}\left(\frac{{(\Omega_{\perp}-\Omega_{L})z}}{2}\right)$
$\displaystyle+4|{\hat{w}}_{3}{\hat{w}}_{1}|\mathbb{\tilde{V}}_{31}cos^{2}\left(\frac{{(\Omega_{L}-\Omega_{\parallel})z}}{2}\right)-4|{\hat{v}}_{3}{\hat{v}}_{4}||{\hat{w}}_{3}{\hat{w}}_{4}|cos^{2}\left(\frac{{(\Omega_{L}-\Omega_{\phi^{\prime}})z}}{2}\right)$
$\displaystyle-4|{\hat{v}}_{4}{\hat{v}}_{1}||{\hat{w}}_{4}{\hat{w}}_{1}|sin^{2}\left(\frac{{(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z}}{2}\right)-4|{\hat{v}}_{2}{\hat{v}}_{4}||{\hat{w}}_{2}{\hat{w}}_{4}|sin^{2}\left(\frac{{(\Omega_{\phi^{\prime}}-\Omega_{\perp})z}}{2}\right)\Big{]}.$
(S168) $\displaystyle Q_{\parallel\perp}$
$\displaystyle=\Big{[}2(|{\hat{u}}_{2}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|+|{\hat{v}}_{2}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|-|{\hat{u}}_{1}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|-|{\hat{v}}_{1}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|)\;sin({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle+2(|{\hat{u}}_{3}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|+|{\hat{v}}_{3}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|-|{\hat{u}}_{2}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|-|{\hat{v}}_{2}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|)\;sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+2(|{\hat{u}}_{3}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|+|{\hat{v}}_{3}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|-|{\hat{u}}_{1}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|-|{\hat{v}}_{1}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|)\;sin({(\Omega_{\parallel}-\Omega_{L})z})$
$\displaystyle+2|{\hat{v}}_{4}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|)\;sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})-2|{\hat{v}}_{4}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|)\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-2|{\hat{v}}_{4}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|)\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S169) $\displaystyle Q_{\parallel L}$
$\displaystyle=\Big{[}2(|{\hat{u}}_{1}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{u}}_{2}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|-|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{2}{\hat{w}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{1}{\hat{w}}_{1}|)sin({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle-2(|{\hat{u}}_{2}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|+|{\hat{u}}_{3}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{2}{\hat{w}}_{2}|)sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-2(|{\hat{u}}_{3}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{u}}_{1}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{1}{\hat{w}}_{1}|-|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{3}{\hat{w}}_{3}|)sin({(\Omega_{\parallel}-\Omega_{L})z})$
$\displaystyle-2|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{4}{\hat{w}}_{4}|)\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})+2|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{4}{\hat{w}}_{4}|)\;sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle-2|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{4}{\hat{w}}_{4}|)\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S170) $\displaystyle Q_{\perp L}$
$\displaystyle=\Big{[}2(|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{u}}_{1}{\hat{w}}_{1}|-|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{u}}_{2}{\hat{w}}_{2}|+|{\hat{v}}_{1}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{2}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|$
$\displaystyle-|{\hat{v}}_{3}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|+|{\hat{v}}_{4}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|)-2(|{\hat{v}}_{4}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{v}}_{3}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|)\;cos({(\Omega_{L}-\Omega_{\phi^{\prime}})z})$
$\displaystyle+2(|{\hat{v}}_{4}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{1}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|)\;cos({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle+2(|{\hat{v}}_{2}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|+|{\hat{v}}_{4}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|)\;cos({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-2(|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{u}}_{2}{\hat{w}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{u}}_{1}{\hat{w}}_{1}|-|{\hat{v}}_{1}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|-|{\hat{v}}_{2}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle+2(|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{v}}_{2}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|+|{\hat{v}}_{3}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|)cos({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+2(|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{u}}_{1}{\hat{w}}_{1}|-|{\hat{v}}_{1}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|+|{\hat{v}}_{3}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{L})z})\Big{]},$
(S171)

where
$\mathbb{V}_{ij}=|{\hat{u}}_{i}{\hat{u}}_{j}|+|{\hat{v}}_{i}{\hat{v}}_{j}|$
and
$\mathbb{\tilde{V}}_{ij}=|{\hat{u}}_{i}{\hat{u}}_{j}|-|{\hat{v}}_{i}{\hat{v}}_{j}|$(
$i$ and $j$ may take value from 1 to 3). In similar way, variables used in the
expression of Stokes parameters U and V, written as:

$\displaystyle U_{\parallel}$
$\displaystyle=2\Big{[}|{\hat{u}}_{1}{\hat{u}}_{2}|(|{\hat{u}}_{1}{\hat{v}}_{2}|-|{\hat{u}}_{2}{\hat{v}}_{1}|)sin\left((\Omega_{\parallel}-\Omega_{\perp})z\right)+|{\hat{u}}_{2}{\hat{u}}_{3}|(|{\hat{u}}_{2}{\hat{v}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{2}|)sin\left((\Omega_{\perp}-\Omega_{L})z\right)$
$\displaystyle+|{\hat{u}}_{3}{\hat{u}}_{1}|(|{\hat{u}}_{3}{\hat{v}}_{1}|-|{\hat{u}}_{1}{\hat{v}}_{3}|)sin\left((\Omega_{L}-\Omega_{\parallel})z\right)\Big{]}.$
(B.13) $\displaystyle U_{\perp}$
$\displaystyle=2\Big{[}|{\hat{v}}_{1}{\hat{v}}_{2}|(|{\hat{u}}_{1}{\hat{v}}_{2}|-|{\hat{u}}_{2}{\hat{v}}_{1}|)sin\left((\Omega_{\parallel}-\Omega_{\perp})z\right)+|{\hat{v}}_{2}{\hat{v}}_{3}|(|{\hat{u}}_{2}{\hat{v}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{2}|)sin\left((\Omega_{\perp}-\Omega_{L})z\right)$
$\displaystyle+|{\hat{v}}_{3}{\hat{v}}_{1}|(|{\hat{u}}_{3}{\hat{v}}_{1}|-|{\hat{u}}_{1}{\hat{v}}_{3}|)sin\left((\Omega_{L}-\Omega_{\parallel})z\right)-|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{4}|^{2}sin\left((\Omega_{\phi^{\prime}}-\Omega_{\parallel})z\right)$
$\displaystyle+|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{4}|^{2}sin((\Omega_{L}-\Omega_{\phi^{\prime}})z)\Big{]}.$
(S172) $\displaystyle U_{L}$
$\displaystyle=2\Big{[}|{\hat{w}}_{1}{\hat{w}}_{2}|(|{\hat{u}}_{1}{\hat{v}}_{2}|-|{\hat{u}}_{2}{\hat{v}}_{1}|)sin\left((\Omega_{\parallel}-\Omega_{\perp})z\right)-|{\hat{w}}_{2}{\hat{w}}_{3}|(|{\hat{u}}_{2}{\hat{v}}_{3}|-|{\hat{u}}_{3}{\hat{v}}_{2}|)sin\left((\Omega_{\perp}-\Omega_{L})z\right)$
$\displaystyle+|{\hat{w}}_{3}{\hat{w}}_{1}|(|{\hat{u}}_{3}{\hat{v}}_{1}|-|{\hat{u}}_{1}{\hat{v}}_{3}|)sin\left((\Omega_{\parallel}-\Omega_{L})z\right)+|{\hat{u}}_{1}{\hat{w}}_{1}||{\hat{v}}_{4}{\hat{w}}_{4}|sin\left((\Omega_{\parallel}-\Omega_{\phi^{\prime}})z\right)$
$\displaystyle+|{\hat{u}}_{2}{\hat{w}}_{2}||{\hat{v}}_{4}{\hat{w}}_{4}|sin\left((\Omega_{\perp}-\Omega_{\phi^{\prime}})z\right)-|{\hat{u}}_{3}{\hat{w}}_{3}||{\hat{v}}_{4}{\hat{w}}_{4}|sin\left((\Omega_{L}-\Omega_{\phi^{\prime}})z\right)\Big{]}.$
(S173) $\displaystyle U_{\parallel\perp}$
$\displaystyle=2\Big{[}(|{\hat{u}}_{1}|^{2}|{\hat{v}}_{2}|^{2}+|{\hat{u}}_{2}|^{2}|{\hat{v}}_{1}|^{2})\;cos({(\Omega_{\parallel}-\Omega_{\perp})z})+(|{\hat{u}}_{2}|^{2}|{\hat{v}}_{3}|^{2}+|{\hat{u}}_{3}|^{2}|{\hat{v}}_{2}|^{2})\;cos({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+(|{\hat{u}}_{3}|^{2}|{\hat{v}}_{1}|^{2}+|{\hat{u}}_{1}|^{2}|{\hat{v}}_{3}|^{2})\;cos({(\Omega_{L}-\Omega_{\parallel})z})+|{\hat{u}}_{1}|^{2}|{\hat{v}}_{4}|^{2}\;cos({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle+|{\hat{u}}_{2}|^{2}|{\hat{v}}_{4}|^{2}\;cos({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})+|{\hat{u}}_{2}|^{2}|{\hat{v}}_{4}|^{2}\;cos({(\Omega_{L}-\Omega_{\phi^{\prime}})z})-2|{\hat{u}}_{1}{\hat{u}}_{2}||{\hat{v}}_{1}{\hat{v}}_{2}|)cos({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle-2|{\hat{u}}_{2}{\hat{u}}_{3}||{\hat{v}}_{2}{\hat{v}}_{3}|)cos({(\Omega_{\perp}-\Omega_{L})z})-2|{\hat{u}}_{3}{\hat{u}}_{1}||{\hat{v}}_{3}{\hat{v}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{L})z})\Big{]}.$
(S174) $\displaystyle U_{\parallel L}$
$\displaystyle=2\Big{[}|{\hat{u}}_{1}{\hat{u}}_{2}|(|{\hat{w}}_{1}{\hat{v}}_{2}|+|{\hat{w}}_{2}{\hat{v}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{\perp})z})+|{\hat{u}}_{2}{\hat{u}}_{3}|(|{\hat{w}}_{2}{\hat{v}}_{3}|-|{\hat{w}}_{3}{\hat{v}}_{2}|)cos({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-|{\hat{u}}_{3}{\hat{u}}_{1}|(|{\hat{w}}_{3}{\hat{v}}_{1}|-|{\hat{w}}_{1}{\hat{v}}_{3}|)cos({(\Omega_{\parallel}-\Omega_{L})z})-(|{\hat{u}}_{1}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|+|{\hat{u}}_{2}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|)\;cos({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle+(|{\hat{u}}_{2}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|-|{\hat{u}}_{3}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|)\;cos({(\Omega_{\perp}-\Omega_{L})z})-(|{\hat{u}}_{3}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|-|{\hat{u}}_{1}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|)\;cos({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-|{\hat{u}}_{1}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}\;cos({(\Omega_{L}-\Omega_{\phi^{\prime}})z})-|{\hat{u}}_{2}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}\;cos({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})-|{\hat{u}}_{3}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}\;cos({(\Omega_{\phi^{\prime}}-\Omega_{L})z})\Big{]}.$
$\displaystyle U_{\perp L}$
$\displaystyle=\Big{[}(|{\hat{v}}_{1}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{v}}_{2}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|)\;sin({(\Omega_{\parallel}-\Omega_{\perp})z})-(|{\hat{v}}_{2}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|+|{\hat{v}}_{3}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|)\;sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-(|{\hat{v}}_{3}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{1}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|)\;sin({(\Omega_{\parallel}-\Omega_{L})z})+|{\hat{u}}_{1}{\hat{w}}_{1}||{\hat{v}}_{4}|^{2}\;sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle-|{\hat{u}}_{2}{\hat{w}}_{2}||{\hat{v}}_{4}|^{2}\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})+|{\hat{u}}_{3}{\hat{w}}_{3}||{\hat{v}}_{4}|^{2}\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-(|{\hat{v}}_{1}{\hat{v}}_{2}|(|{\hat{u}}_{1}{\hat{w}}_{2}|-|{\hat{u}}_{2}{\hat{w}}_{1}|)sin({(\Omega_{\parallel}-\Omega_{\perp})z})+(|{\hat{v}}_{2}{\hat{v}}_{3}|(|{\hat{u}}_{2}{\hat{w}}_{3}|+|{\hat{u}}_{3}{\hat{w}}_{2}|)sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+(|{\hat{v}}_{3}{\hat{v}}_{1}|(|{\hat{u}}_{3}{\hat{w}}_{1}|+|{\hat{u}}_{1}{\hat{w}}_{3}|)sin({(\Omega_{\parallel}-\Omega_{L})z})+|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{4}{\hat{w}}_{4}|sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle-|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{4}{\hat{w}}_{4}|sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{4}{\hat{w}}_{4}|sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S175)

$\displaystyle V_{\parallel}$
$\displaystyle=2\Big{[}|{\hat{u}}_{1}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|+|{\hat{u}}_{2}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|+|{\hat{u}}_{3}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|+|{\hat{u}}_{1}||{\hat{u}}_{2}|(|{\hat{u}}_{1}{\hat{v}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{1}|)cos((\Omega_{\parallel}-\Omega_{\perp})z)$
$\displaystyle+|{\hat{u}}_{2}||{\hat{u}}_{3}|(|{\hat{u}}_{2}{\hat{v}}_{3}|+|{\hat{u}}_{3}{\hat{v}}_{2}|)cos((\Omega_{\perp}-\Omega_{L})z)+|{\hat{u}}_{3}||{\hat{u}}_{1}|(|{\hat{u}}_{3}{\hat{v}}_{1}|+|{\hat{u}}_{1}{\hat{v}}_{3}|)cos((\Omega_{\parallel}-\Omega_{L})z)\Big{]}.$
$\displaystyle V_{\perp}$
$\displaystyle=2\Big{[}|{\hat{v}}_{1}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|+|{\hat{v}}_{2}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|+|{\hat{v}}_{3}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|+|{\hat{v}}_{1}{\hat{v}}_{2}|(|{\hat{u}}_{1}{\hat{v}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{1}|)cos((\Omega_{\parallel}-\Omega_{\perp})z)$
$\displaystyle+|{\hat{v}}_{2}{\hat{v}}_{3}|(|{\hat{u}}_{2}{\hat{v}}_{3}|+|{\hat{u}}_{3}{\hat{v}}_{2}|)cos((\Omega_{\perp}-\Omega_{L})z)+|{\hat{v}}_{3}{\hat{v}}_{1}|(|{\hat{u}}_{3}{\hat{v}}_{1}|+|{\hat{u}}_{1}{\hat{v}}_{3}|)cos((\Omega_{L}-\Omega_{\parallel})z)$
$\displaystyle+|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{4}|^{2}cos\left((\Omega_{\phi^{\prime}}-\Omega_{\parallel})z\right)+|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{4}|^{2}cos((\Omega_{L}-\Omega_{\phi^{\prime}})z)\Big{]}.$
(S176) $\displaystyle V_{L}$
$\displaystyle=2\Big{[}|{\hat{w}}_{1}|^{2}|{\hat{u}}_{1}{\hat{v}}_{1}|+|{\hat{w}}_{2}|^{2}|{\hat{u}}_{2}{\hat{v}}_{2}|+|{\hat{w}}_{3}|^{2}|{\hat{u}}_{3}{\hat{v}}_{3}|+|{\hat{w}}_{1}{\hat{w}}_{2}|(|{\hat{u}}_{1}{\hat{v}}_{2}|+|{\hat{u}}_{2}{\hat{v}}_{1}|)cos((\Omega_{\parallel}-\Omega_{\perp})z)$
$\displaystyle-|{\hat{w}}_{2}{\hat{w}}_{3}|(|{\hat{u}}_{2}{\hat{v}}_{3}|+|{\hat{u}}_{3}{\hat{v}}_{2}|)cos((\Omega_{\perp}-\Omega_{L})z)-|{\hat{w}}_{3}{\hat{w}}_{1}|(|{\hat{u}}_{3}{\hat{v}}_{1}|+|{\hat{u}}_{1}{\hat{v}}_{3}|)cos((\Omega_{L}-\Omega_{\parallel})z)$
$\displaystyle+|{\hat{v}}_{4}{\hat{w}}_{4}|\big{[}|{\hat{u}}_{1}{\hat{w}}_{1}|cos\left((\Omega_{\phi^{\prime}}-\Omega_{\parallel})z\right)+|{\hat{u}}_{2}{\hat{w}}_{2}|cos((\Omega_{\perp}-\Omega_{\phi^{\prime}})z)-|{\hat{u}}_{3}{\hat{w}}_{3}|cos((\Omega_{L}-\Omega_{\phi^{\prime}})z)\big{]}\Big{]}.$
$\displaystyle V_{\parallel\perp}$
$\displaystyle=2\Big{[}(|{\hat{u}}_{2}|^{2}|{\hat{v}}_{1}|^{2}-|{\hat{u}}_{1}|^{2}|{\hat{v}}_{2}|^{2})\;sin({(\Omega_{\parallel}-\Omega_{\perp})z})+(|{\hat{u}}_{3}|^{2}|{\hat{v}}_{2}|^{2}-|{\hat{u}}_{2}|^{2}|{\hat{v}}_{3}|^{2})\;sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle+(|{\hat{u}}_{1}|^{2}|{\hat{v}}_{3}|^{2}-|{\hat{u}}_{3}|^{2}|{\hat{v}}_{1}|^{2})\;sin({(\Omega_{L}-\Omega_{\parallel})z})+|{\hat{u}}_{1}|^{2}|{\hat{v}}_{4}|^{2}\;sin({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle-|{\hat{u}}_{2}|^{2}|{\hat{v}}_{4}|^{2}\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})-|{\hat{u}}_{3}|^{2}|{\hat{v}}_{4}|^{2}\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S177) $\displaystyle V_{\parallel L}$
$\displaystyle=2\Big{[}|{\hat{u}}_{1}{\hat{u}}_{2}|(|{\hat{w}}_{2}{\hat{v}}_{1}|-|{\hat{w}}_{1}{\hat{v}}_{2}|)sin({(\Omega_{\parallel}-\Omega_{\perp})z})-|{\hat{u}}_{2}{\hat{u}}_{3}|(|{\hat{w}}_{3}{\hat{v}}_{2}|+|{\hat{w}}_{2}{\hat{v}}_{3}|)sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-|{\hat{u}}_{3}{\hat{u}}_{1}|(|{\hat{w}}_{1}{\hat{v}}_{3}|+|{\hat{w}}_{3}{\hat{v}}_{1}|)sin({(\Omega_{\parallel}-\Omega_{L})z})-|{\hat{u}}_{1}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|sin({(\Omega_{\parallel}-\Omega_{\phi^{\prime}})z})$
$\displaystyle+|{\hat{u}}_{2}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|\;sin({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})-(|{\hat{u}}_{3}|^{2}|{\hat{v}}_{4}{\hat{w}}_{4}|\;sin({(\Omega_{L}-\Omega_{\phi^{\prime}})z})$
$\displaystyle+(|{\hat{u}}_{1}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|-|{\hat{u}}_{2}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|)\;sin({(\Omega_{\parallel}-\Omega_{\perp})z})-(|{\hat{u}}_{2}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|+|{\hat{u}}_{3}|^{2}|{\hat{v}}_{2}{\hat{w}}_{2}|)\;sin({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-(|{\hat{u}}_{3}|^{2}|{\hat{v}}_{1}{\hat{w}}_{1}|+|{\hat{u}}_{1}|^{2}|{\hat{v}}_{3}{\hat{w}}_{3}|)\;sin({(\Omega_{\parallel}-\Omega_{L})z})\Big{]}.$
(S178) $\displaystyle V_{\perp L}$
$\displaystyle=2\Big{[}2|{\hat{v}}_{3}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|-2|{\hat{v}}_{2}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|-2|{\hat{v}}_{1}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|-(|{\hat{v}}_{2}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|+|{\hat{v}}_{1}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|)\;cos({(\Omega_{\parallel}-\Omega_{\perp})z})$
$\displaystyle-(|{\hat{v}}_{3}|^{2}|{\hat{u}}_{2}{\hat{w}}_{2}|-|{\hat{v}}_{2}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|)\;cos({(\Omega_{\perp}-\Omega_{L})z})+(|{\hat{v}}_{1}|^{2}|{\hat{u}}_{3}{\hat{w}}_{3}|-|{\hat{v}}_{3}|^{2}|{\hat{u}}_{1}{\hat{w}}_{1}|)\;cos({(\Omega_{\parallel}-\Omega_{L})z})$
$\displaystyle-|{\hat{u}}_{1}{\hat{w}}_{1}||{\hat{v}}_{4}|^{2}\;cos({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})-|{\hat{u}}_{2}{\hat{w}}_{2}||{\hat{v}}_{4}|^{2}\;cos({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})+|{\hat{u}}_{3}{\hat{w}}_{3}||{\hat{v}}_{4}|^{2}\;cos({(\Omega_{L}-\Omega_{\phi^{\prime}})z})$
$\displaystyle-(|{\hat{v}}_{1}{\hat{v}}_{2}|(|{\hat{u}}_{1}{\hat{w}}_{2}|+|{\hat{u}}_{2}{\hat{w}}_{1}|)cos({(\Omega_{\parallel}-\Omega_{\perp})z})+(|{\hat{v}}_{2}{\hat{v}}_{3}|(|{\hat{u}}_{2}{\hat{w}}_{3}|-|{\hat{u}}_{3}{\hat{w}}_{2}|)cos({(\Omega_{\perp}-\Omega_{L})z})$
$\displaystyle-(|{\hat{v}}_{3}{\hat{v}}_{1}|(|{\hat{u}}_{3}{\hat{w}}_{1}|-|{\hat{u}}_{1}{\hat{w}}_{3}|)cos({(\Omega_{\parallel}-\Omega_{L})z})-|{\hat{u}}_{1}{\hat{v}}_{1}||{\hat{v}}_{4}{\hat{w}}_{4}|cos({(\Omega_{\phi^{\prime}}-\Omega_{\parallel})z})$
$\displaystyle-|{\hat{u}}_{2}{\hat{v}}_{2}||{\hat{v}}_{4}{\hat{w}}_{4}|cos({(\Omega_{\perp}-\Omega_{\phi^{\prime}})z})-|{\hat{u}}_{3}{\hat{v}}_{3}||{\hat{v}}_{4}{\hat{w}}_{4}|cos({(\Omega_{L}-\Omega_{\phi^{\prime}})z})\Big{]}.$
(S179)

It is worth noting that, due to the appearance of the longitudinal degree of
photon in mixing, the Stokes parameters for this case, augmented with extra
longitudinal components, denoted with suffix L for each of the variables I, Q,
U,V. Primarily, it is due to this reason, that the Lorentz and ${\bf C}{\bf
P}{\bf T}$ symmetry of each degree of freedom (i.e.,
$A_{\parallel},A_{\perp},A_{L},\phi^{\prime}$) – that constitutes every term
in any equation of motion–follows from the same (symmetry) enjoyed by the
interaction vertex (IL) 666 The word symmetries here mean the discrete and
continuous symmetries, internal or space time ( those following from the
actions of the generators of the symmetry group: constituting the set of
orthogonal proper Lorentz transformations (OPLT )) that the associated
dynamical and background-fields respect. That is, the transformation
properties of a vertex, under a set of discrete symmetry transformations, is
decided by the actions of the same, i.e., — on the fields that constitute the
vertex. In other words, under the actions of C, P and T on the background
field ($\bar{F}^{\mu\nu}$), dynamical photons field ($f_{\mu\nu}$) the scalar
field $\phi$ or the pseudoscalar field $\phi^{\prime}$ – that collectively
constitutes the vertex.

##  15 Statistical analysis

###  15.1 Normal distributions from numerical solutions

We have plotted the Stokes parameters in figures [S7-S10] and the ellipticity
angle $\chi_{\phi_{i}}$ and polarization angle $\psi_{\phi_{i}}$ (in radians)
in figures [S11-S12] using the exact numerical solutions obtained by
diagonalizing (59) and (68) exactly for the following system parameters
$m_{\phi}=m_{\phi^{\prime}}=1.0\times 10^{-11}$ GeV-1,
$g_{\phi,\phi^{\prime}\gamma\gamma}=1.0\times 10^{-11}$ GeV-1, B $\sim$ 1012
Gauss, $\omega_{p}=1.0\times 10^{-10}$ GeV, in energy range (1-100) KeV, path
length $z=22.3$ meters, for both eqns.[59] and [68].

Figure S7: Stokes parameter I for $\phi\gamma$ and $\phi^{\prime}\gamma$ .

Figure S8: Stokes parameter Q for $\phi\gamma$ and $\phi^{\prime}\gamma$ .

Figure S9: Stokes parameter U for $\phi\gamma$ and $\phi^{\prime}\gamma$ .

Figure S10: Stokes parameter V for $\phi\gamma$ and $\phi^{\prime}\gamma$ .

Figure S11: Ellipticity angle for $\phi\gamma$ and $\phi^{\prime}\gamma$ .

Figure S12: Polarization angle for $\phi\gamma$ and $\phi^{\prime}\gamma$ .

Figure S13: Plots of degree of linear polarization vs counts. The parameters
for this plots are; $m_{\phi}=m_{\phi^{\prime}}=1.0\times 10^{-11}$ GeV-1,
$g_{\phi,\phi^{\prime}\gamma\gamma}=1.0\times 10^{-11}$ GeV -1, B $\sim$ 1012
Gauss, $\omega_{p}=1.0\times 10^{-10}$ GeV, in energy range (1-100) KeV, path
length $z=22.3$ meters.

The oscillating behaviour of the Stokes parameters and the observables
($\chi_{\phi_{i}}$ and $\psi_{\phi_{i}}$) as a function of energy is evident
from the plots displayed in figures [S7-S12]. None of the current space based
observations confirm the same and we believe the proposed observations would
not be able to detect the same. The chief reason behind this being the space
based detectors are mostly sensitive over an energy band not a line.
So, in the spirit of the analysis of the observational X-ray polarization
data, we divide initially the window of the energy band under consideration
i.e., $1-100$ KeV into $10000$ intervals and evaluated the average of the
parameters ${\bf{I}},{\bf{Q}}$ and ${\bf{U}}$ to get
${\bf\bar{I}},{\bf\bar{Q}}$ and ${\bf\bar{U}}$ and hence the average of degree
of linear polarization ${P_{L\phi_{i}}}$ to get the first set of samples. This
procedure was followed by increasing $N$ to $N^{\prime}$ such that
$N^{\prime}=N+\Delta N$, when $\Delta N=100$. We continued this process until
$N^{\prime}=N+n\Delta N$ when $n=400$. Thus we generated a samples of $401$
data points for ${P}_{L\phi_{i}}$.
These samples were further distributed on frequency distribution plots for
both the systems ($\gamma\phi$, $\gamma\phi^{\prime}$) by choosing the
appropriate bin size along the x-axis. These frequency distributions were
further plotted in fig.[S13] for scalar photon (in the left panel) as well as
pseudoscalar photon (in the right panel) systems.
Assuming the obtained frequency distributions of the samples as normal
distributions, we have estimated the (mean) average value and the variance of
the of the $P_{L\phi_{i}}$ obtained in the energy interval of $1-100$ KeV. The
mean of $P_{L\phi_{i}}$ for $\gamma\phi$ and $\gamma\phi^{\prime}$ system
turns out to be $\mu_{\phi}=0.414$ and $\mu_{\phi^{\prime}}=0.215$ and the
corresponding variance turns out to be $\sigma^{2}_{\phi}=0.275\times 10^{-6}$
and $\sigma^{2}_{\phi^{\prime}}=0.264\times 10^{-5}$ respectively.
Statistically, it means in the one sigma level for $\gamma\phi$ system the
range of $P_{L\phi_{i}}$ lies between $0.414-0.275\times 10^{-6}$ to
$0.414+0.275\times 10^{-6}$ and for $\gamma\phi^{\prime}$ system it is
$0.215+0.264\times 10^{-5}$ to $0.215+0.264\times 10^{-5}$. As can be seen
from the range that with increase in the numbers of dof the range for the
confidence level increases by the factor of 10. The C.L analysis for other
interaction parameters should be performed for designing the detectors for
space borne experiments.

###  15.2 MDP

Many of the astrophysical polarimeters use minimum detectable polarization
(MDP) to define detector efficiency. The probability amplitude of polarization
that has $1\%$ chance of being detected is called MDP. Usually the expression
of the same is given by,

$\displaystyle MDP=\frac{4.29}{\sqrt{N}\mu},$ (S180)

when $\mu$ is the modulation factor that can vary between 0 and 1 and $N$ is
the sample size. Instruments like APEX has $MDP$ is $\sim 1\%$ at $5.2$ KeV
APEX . The $MDP$ in terms of mean $\mu_{\phi_{i}}$ and $\sigma_{\phi_{i}}$ of
the observed data of $P_{L\phi_{i}}$ when background is zero and modulation
factor is one, can be cast as:

$\displaystyle
MDP_{\phi_{i}}=\mu_{\phi_{i}}+\frac{4.29}{\sqrt{2}}\sigma_{\phi_{i}}.$ (S181)

In our case of investigation, we have found that
$MDP_{\phi}>MDP_{\phi^{\prime}}$ for the parameters range under consideration
in this work. Thus in the same parameter space the increase in the number of
degrees of freedom of the system, the detectability of $P_{L\phi_{i}}$ seems
to be reduced. This information should be considered while searching for ALPs
in compact star models using observed data.


11institutetext: Department of Mathematics, Indian Institute of Science
Education and Research Pune, Pune, India
11email<EMAIL_ADDRESS>22institutetext: School of
Computing Science, University of Glasgow, Glasgow, UK 22email:
<EMAIL_ADDRESS>

# Complexity results for the Pilot Assignment problem in Cell-Free Massive
MIMO

Shruthi Prusty (✉) 11 0009-0003-4157-2427 Sofiat Olaosebikan 22
0000-0002-8003-7887

###### Abstract

Wireless communication is enabling billions of people to connect to each other
and the internet, transforming every sector of the economy, and building the
foundations for powerful new technologies that hold great promise to improve
lives at an unprecedented rate and scale. The rapid increase in the number of
devices and the associated demands for higher data rates and broader network
coverage fuels the need for more robust wireless technologies. The key
technology identified to address this problem is referred to as Cell-Free
Massive MIMO (CF-mMIMO). CF-mMIMO is accompanied by many challenges, one of
which is efficiently allocating limited resources. In this paper, we focus on
a major resource allocation problem in wireless networks, namely the Pilot
Assignment problem (PA). We show that PA is strongly NP-hard and that it does
not admit a polynomial-time constant-factor approximation algorithm. Further,
we show that PA cannot be approximated in polynomial time within
$\mathcal{O}(K^{2})$ (where $K$ is the number of users) when the system
consists of at least three pilots. Finally, we present an approximation lower
bound of $1.058$ (resp. $\epsilon|K|^{2}$, for $\epsilon>0$) in special cases
where the system consists of exactly two (resp. three) pilots.

###### Keywords:

Pilot Assignment Cell-Free Massive MIMO NP-hard optimization problem Strong
NP-hardness Approximability

##  1 Introduction

###  1.1 Background: Cell-free Massive MIMO

Wireless networks is an essential technology for enabling flexible
communication and connectivity between individuals (or machines) across
regions. In addition, it is transforming every sector of the economy
(transportation, healthcare, education, etc.), and powerful new technologies
(artificial intelligence, internet of things, etc.) are being built upon it.
Cellular networks is the technology that 1G to 5G relies on [16, 26]. Here,
the coverage area is divided up into non-overlapping cells, and we have a
single Access Point (AP) coordinating data transmissions amongst user devices
within its cell.

As the number of devices that depend on wireless communication networks
continues to grow, each needing a high connection rate and better coverage
with minimal interference, this technology will no longer be suitable [20,
26]. Particularly, resources (e.g. channels, power, spectrum) in a wireless
network are limited and must be managed efficiently. Further, the User
Equipments (UEs) at the edge of the cells get poor service due to _inter-cell
interference_.

For future wireless communications (e.g., 6G), the key technology that has the
potential to enhance connectivity and provide better coverage for billions of
users is referred to as Cell-Free Massive Multiple-Input Multiple-Output (CF-
mMIMO). As the name suggests, CF-mMIMO allows a device/user (UE) to be served
by multiple access points (APs) that are within its range without the notion
of boundaries; in contrast to the current technology, which allows each UE to
be served by only one AP within a defined boundary. The goal of this network
is to reduce inter-cell interferences, improve the uniform distribution of
spectral efficiency amongst users and enhance network reliability [20]. CF-
mMIMO is accompanied by many challenges, one of which is how to efficiently
manage limited resources (spectrum, pilot signals, energy, and power) – the
so-called resource allocation problem in wireless networks [5].

###  1.2 The Pilot Assignment problem

Throughout this paper, we will consider a CF-mMIMO system with $M$ single-
antenna APs and $K$ $(K\ll M)$ UEs where the APs are randomly distributed in a
large area. Since a large number of distributed APs jointly provide uniform
service to a small number of UEs without any notion of boundaries, it is often
the case that _AP selection_ is done for each user, such that only a subset of
the APs providing service above a certain threshold are considered for any
energy or spectral efficiency calculations pertaining to that user [19, 25].
An important assumption in this paper is that AP selection is always done for
any CF-mMIMO system we consider [25]. We now turn our attention towards a
major problem that hinders resource allocation in wireless communication
networks, and is a resource allocation problem itself: the Pilot Assignment
problem (PA).

It is essential to acquire accurate _Channel State Information (CSI)_ between
the UEs and the APs to reap all the benefits potentially provided by the
distributed user-centric CF-mMIMO architecture [5]. Channel estimation allows
APs to process data signals from the UEs. To perform channel estimation for a
user, a _pilot signal_ needs to be assigned to it. In the system setting, it
is assumed that APs and UEs do not have _a priori_ CSI at the beginning of a
coherent interval. The CSI is estimated in what is called a _pilot training
phase_ , which usually happens in the uplink. Channel estimation is needed
only at the beginning of a coherent interval $\tau_{c}$. Thus, $\tau$ pilot
sequences (or signals) of length $\tau$ each are assigned to the UEs prior to
uplink data transmission for channel estimation. Each UE is assigned one
pilot. The received pilot information is used for channel estimation. The
estimated channel is used to detect the received data, thereby allowing us to
calculate the Spectral Efficiency (SE) of each UE [7]. However, due to the
limited length of the coherence interval, the available number of orthogonal
pilot sequences is normally smaller than the number of UEs $(\tau\ll K)$ and
some UEs have to reuse a given pilot. Hence, the orthogonality among the pilot
sequences for all UEs is typically not achieved. The pilot reuse causes an
impairment known as pilot contamination, which can degrade the system
performance, by lowering the achievable uplink/downlink rates and signal-to-
interference-plus-noise ratio (SINR) of the system [19, 25].

###  1.3 Existing work and contributions of this paper

PA has been extensively researched from the engineering perspective, with the
aim of constructing heuristic-based algorithms that return sub-optimal
solutions for this distributed architecture. The most straightforward and
naive pilot allocation strategy is the _random_ pilot assignment scheme, in
which the available pilots are assigned randomly to each user [20]. Of course,
this does not address any of the problems, including two nearby users sharing
the same pilot, and thus turns out to be the worst scheme. The _greedy_ pilot
assignment scheme proposed in [20] works by iteratively improving the downlink
rate for the worst user. However, such a method can only improve the worst
user’s performance at any given point, and cannot guarantee an improvement in
the whole system’s performance. This means that this algorithm is not
guaranteed to converge stably to a global maximum value.

The _location-based greedy_ pilot assignment scheme utilizes the location
information of the users for the initial assignment of pilots in the greedy
scheme, instead of random assignment. This method, however, does not prove to
be very effective in practice and only promotes the throughput performances of
a few users [19, 27]. The _structured_ pilot assignment scheme maximizes the
minimum distance among UEs that share the same pilot using a clustering
algorithm, but the implementation in a real-world cell-free massive MIMO
system is hindered by the difficulty of finding the centroid APs in such
practical systems [2, 19]. The _Maximal Increment_ (MI) algorithm maximizes
the achievable (downlink) rate by maximizing the increment in an iterative
algorithm, but it has high time complexity [24]. The _Hungarian Algorithm_
based pilot assignment scheme is an iterative procedure based on the Hungarian
algorithm to enhance system throughput and fairness by avoiding pilot reuse
among nearby users. However, it has been observed that it is not sufficiently
accurate to measure pilot contamination solely based on the geographical
distance between the users [4, 25].

Recently, two graph-based pilot assignment schemes have been used: the _graph-
colouring_ based pilot assignment scheme [19] and the _Max- $k$-Cut_ based
pilot assignment scheme in a weighted graphic framework [25]. In both cases,
the CF-mMIMO architecture is modelled as a graph, with the UEs forming the
vertices and the edges representing the interference between the UEs. The
pilot assignment optimization is then solved on this graph. Since both the
graph-colouring and the Max-$k$-Cut problems fall in the class of NP-hard
problems, heuristic graph algorithms have been employed to find reasonable
solutions to PA, supported by experimental results obtained via simulations,
where they outperform other non-graph theoretic algorithms with reasonable
time complexity. Further, the Max-$k$-Cut scheme even outperforms the graph-
colouring scheme [19, 25], making it the state of the art. This led us to
believe that there must be some sort of natural relation between the pilot
assignment optimization problem and classical graph-theoretic optimization
problems. The existing experimental results in the literature aim to optimize
a certain Quality of Service (QoS) metric such as the sum-user SE, the system
throughput, and the system Energy Efficiency (EE), all of which can be
expressed via the uplink/downlink achievable rates, which further depend on
the Signal-to-Interference-plus-Noise Ratio (SINR) [4, 5, 18, 19, 25].

##### Our contribution.

Despite all the research effort that has been put into solving the pilot
assignment problem in cell-free massive MIMO systems, PA has received very
little attention from a theoretical computer science perspective. In
particular, to the best of our knowledge, there are no complexity results for
this problem in the literature. Consequently, in this paper, we show that PA
is _strongly_ NP-hard via a reduction from Min-$k$-Partition. We further show
that the problem does not admit a polynomial-time constant-factor
approximation algorithm. Inspired by the results in [8], we show that PA
cannot be approximated in polynomial time within $\mathcal{O}(K^{2})$ (where
$K$ is the number of users) when there are at least three pilots in the
system. We also present an approximation lower bound of $1.058$ (resp.
$\epsilon|K|^{2}$, for $\epsilon>0$) in special cases where the system
consists of exactly two (resp. three) pilots. The implication of our result is
that any positive (explicit bounds on performance ratios) or negative
approximation results for Min-$k$-Partition can be directly translated for PA.

##### Organization.

The remainder of this paper is organized as follows: We present preliminary
definitions, and formally define the CF-mMIMO system as well as the PA
optimization problem in Section 2. We present our complexity results on PA in
Section 3. Finally, in Section 4, we present some concluding remarks and
potential directions for future work.

##  2 Preliminaries and problem definition

###  2.1 Definitions

The results in this paper use well-established terminologies from complexity
and approximation theory. While we recall the most important ones for
completness, we refer interested readers to [3, Chapter 1] for the formal
definitions of terms such as optimization problems, NP-hardness, strong NP-
hardness, approximation classes APX and $F$-APX, and the complete definition
of AP-reducibility.

######  Definition 1 (Optimization problem)

An optimization problem $\Pi$ is a tuple
$(I_{\Pi},\,SOL_{\Pi},\,m_{\Pi},\,\textup{goal}_{\Pi})$ where:

  * •

$I_{\Pi}$ is the set of instances of $\Pi$,

  * •

$SOL_{\Pi}$ is a function that associates to an instance $x\in I_{\Pi}$, the
set of feasible solutions of $x$,

  * •

$m_{\Pi}$ is a measure function, defined for a pair $(x,y)$ where $x\in
I_{\Pi}$ and $y\in SOL_{\Pi}(x)$, that returns a positive rational which is
the value of the feasible solution $y$.

  * •

$\textup{goal}_{\Pi}\in\\{\textsc{min, max}\\}$ denotes whether $\Pi$ is a
minimization or maximization problem.

Given an input instance $x$, we will denote by $SOL_{P}^{*}(x)$ the set of
optimal solutions of $x$. The value of any optimal solution $y^{*}(x)$ of $x$
will be denoted by $m^{*}_{\Pi}(x)$.

######  Definition 2 (The class NPO)

An optimization problem $\Pi=(I_{\Pi},\,SOL_{\Pi},\,\\\
m_{\Pi},\,\textup{goal}_{\Pi})$, where the tuple consists of problem
instances, feasible solutions for every instance, measure function associated
with every feasible solution, and goal of optimization respectively, belongs
to the class NPO if the following holds:

  1. 1.

the set of instances $I_{\Pi}$ is recognizable in polynomial time,

  2. 2.

there exists a polynomial $q$ such that, given an instance $x\in I_{\Pi}$,

    1. (a)

$|y|\leq q(|x|)\ \ \forall\;y\in SOL_{\Pi}(x)$,

    2. (b)

and it is decidable in polynomial time whether $y\in SOL_{\Pi}(x)$ for every
$y$ with $|y|\leq q(|x|)$.

  3. 3.

the measure function $m_{\Pi}$ is computable in polynomial time.

######  Definition 3 (NP-hard optimization problems)

An optimization problem $\Pi$ is called NP-hard if, for every decision problem
$\Pi^{\prime}\in\textup{NP}$, $\Pi^{\prime}\leq_{T}^{p}\Pi$, that is,
$\Pi^{\prime}$ can be solved in polynomial time by an algorithm which queries
an “oracle” that, for any instance $x\in I_{\Pi}$, returns an optimal solution
$y^{*}(x)$ of $x$ along with its value $m_{\Pi}^{*}(x)$.

######  Definition 4 (Strong NP-hardness)

Let $\Pi$ be a decision problem in NP, with an instance $x\in I_{\Pi}$. Let
$\textup{max}(x)$ denote the value of the largest number occurring in the
instance $x$. Given a polynomial $p$, let $\Pi^{\textup{max},p}$ be the
restriction of $\Pi$ to those instances with the property that
$\textup{max}(x)\leq p(|x|)$. If $\Pi^{\textup{max},p}$ remains an NP-hard
problem for some polynomial $p$, then $\Pi$ is called strongly NP-hard.

######  Definition 5 (Performance ratio)

Given an optimization problem $\Pi$, for any instance $x$ of $\Pi$ and for any
feasible solution $y$ of $x$, the performance ratio of $y$ with respect to $x$
is defined as

$R(x,y)=\max\left(\frac{m(x,y)}{m^{*}(x)},\frac{m^{*}(x)}{m(x,y)}\right).$

######  Definition 6 ($\bm{r(n)}$-approximate algorithm)

Given an optimization problem $\Pi$ in NPO, an approximation algorithm
$\mathcal{A}$ for $\Pi$, and a function $r:\mathbb{N}\mapsto(1,\infty)$, we
say that $\mathcal{A}$ is an $\bm{r(n)}$-approximate algorithm for $\Pi$ if,
for any instance $x$ such that $SOL(x)\neq\emptyset$, the performance ratio of
the feasible solution $\mathcal{A}(x)$ with respect to $x$ satisfies the
following inequality:

$R(x,\mathcal{A}(x))\leq r(|x|).$

######  Definition 7 (Class APX)

The class of all NPO problems $\Pi$ such that, for some fixed constant $c>1$,
there exists a polynomial-time $c$-approximate algorithm $($also called
constant-factor approximation algorithm$)$ for $\Pi$.

######  Definition 8 (Class $F$-APX)

Given a class of functions $F$, $F$-APX is the class of all NPO problems $\Pi$
such that, for some function $r\in F$, there exists a polynomial-time
$r(n)$-approximate algorithm for $\Pi$.

In the context of approximation algorithms, a reduction from a problem
$\Pi_{1}$ to a problem $\Pi_{2}$ should guarantee that an approximate solution
for $\Pi_{2}$ yields an approximate solution for $\Pi_{1}$. Thus we need not
only a function $f$ mapping instances of $\Pi_{1}$ into instances of
$\Pi_{2}$, but also a function $g$ mapping back solutions of $\Pi_{2}$ into
solutions of $\Pi_{1}$. Next, we define an approximation-preserving
reducibility called _AP-reducibility_.

######  Definition 9 (AP-reducibility)

Let $P_{1}$ and $P_{2}$ be two optimization problems in NPO. $P_{1}$ is said
to be AP-reducible to $P_{2}$, written $P_{1}\leq_{AP}P_{2}$, if there exist
two functions $f$ and $g$ and a constant $\alpha\geq 1$ such that:

  1. 1.

For an instance $x\in I_{P_{1}}$, and for any rational $r>1$, $f(x,r)\in
I_{P_{2}}$.

  2. 2.

For an instance $x\in I_{P_{1}}$, and for any rational $r>1$, if
$SOL_{P_{1}}(x)\neq\emptyset$, then $SOL_{P_{2}}(f(x,r))\neq\emptyset$.

  3. 3.

For any instance $x\in I_{P_{1}}$, for any rational $r>1$, and for any $y\in
SOL_{P_{2}}(f(x,r))$, $g(x,y,r)\in SOL_{P_{1}}(x)$.

  4. 4.

$f$ and $g$ are computable by two algorithms $\mathcal{A}_{f}$ and
$\mathcal{A}_{g}$, respectively, whose running time is polynomial for any
fixed rational $r$.

  5. 5.

For any instance $x\in I_{P_{1}}$, for any rational $r>1$, and for any $y\in
SOL_{P_{2}}(f(x,r))$,

$R_{P_{2}}(f(x,r),y)\leq r\>\Rightarrow\>R_{P_{1}}(x,g(x,y,r))\leq
1+\alpha(r-1).$

In the rest of this paper, this condition will be referred to as the AP-
condition.

The triple $(f,g,\alpha)$ is said to be an AP-reduction from $P_{1}$ to
$P_{2}$.

###### Remark 1

In most reductions from one optimization problem to another in the literature,
the quality of the solution we are looking for is not required to be known
explicitly. This is the case with our reductions as well, so we shall replace
$f(x,r)$ and $g(x,y,r)$ with $f(x)$ and $g(x,y)$, respectively.

###  2.2 System Model

Building on the description of PA in cell-free massive MIMO (CF-mMIMO) in
Section 1.2, we remark that the channel estimation error caused by pilot
contamination translates into affected achievable rates and eventually leads
to an observable degradation of system throughput. Thus, the system
performance of cell-free massive MIMO has been characterized by the system
throughput in the literature [25], which is defined as
$\sum\limits_{k=1}^{K}R_{k}^{u}$, where $K$ is the number of users and
$R_{k}^{u}$ denotes the uplink achievable rate for user $k$. The quantity
$R_{k}^{u}$ is further defined as $R_{k}^{u}=$

$\frac{1-\tau/\tau_{c}}{2}\log_{2}\left(1+\frac{\rho^{u}\eta_{k}\Bigl{(}\sum_{m\in
A(k)}\gamma_{km}\Bigl{)}^{2}}{\begin{multlined}\rho^{u}\sum_{k^{\prime}\in
O(k)}\eta_{k^{\prime}}\Bigl{(}\sum_{m\in
A(k)}\gamma_{km}\frac{\beta_{k^{\prime}m}}{\beta_{km}}\Bigl{)}^{2}\\\
+\rho^{u}\sum_{k^{\prime}=1}^{K}\eta_{k^{\prime}}\sum_{m\in
A(k)}\gamma_{km}\beta_{k^{\prime}m}+\sum_{m\in
A(k)}\gamma_{km}\end{multlined}\rho^{u}\sum_{k^{\prime}\in
O(k)}\eta_{k^{\prime}}\Bigl{(}\sum_{m\in
A(k)}\gamma_{km}\frac{\beta_{k^{\prime}m}}{\beta_{km}}\Bigl{)}^{2}\\\
+\rho^{u}\sum_{k^{\prime}=1}^{K}\eta_{k^{\prime}}\sum_{m\in
A(k)}\gamma_{km}\beta_{k^{\prime}m}+\sum_{m\in A(k)}\gamma_{km}}\right)$ (1)

where

  * ·

$\eta_{k}$ is the uplink power control coefficient,

  * ·

$\rho^{u}$ is the normalized uplink SNR (signal-to-noise ratio),

  * ·

$\beta_{km}$ denotes the large-scale fading coefficient between user $k$ and
AP $m$ including geometric path loss and shadowing,

  * ·

$\gamma_{km}$ denotes the mean-square of the channel estimation of the channel
coefficient between user $k$ and AP $m$,

  * ·

$A(k)$ denotes the indices of the APs serving user $k$, and

  * ·

$O(k)$ denotes the set of indices of users $k^{\prime}$ with the same pilot as
user $k$, excluding user $k$.

###  2.3 Problem formulation

We present the first mathematical definition of a CF-mMIMO system as well as a
feasible pilot assignment for the system.

######  Definition 10 (Cell-Free Massive MIMO system)

Let $\mathcal{A}$ denote the set of APs with cardinality $M$, $U$ denote the
set of users with cardinality $K$, and $\Psi$ denote the set of pilots with
cardinality $\tau$. Let $\bm{\beta}$ be a $K\times M$ matrix, with the
$(k,m)$-th element denoting the large-scale coefficient $\beta_{km}$ between
user $k$ and AP $m$. For each user $k$, the set $A(k)\;(1\leq k\leq K)$
denotes the indices of the subset of APs serving it, as described above. We
shall refer to the tuple
$\left(\mathcal{A},U,\\{A(k)\\}_{k=1}^{K},\bm{\beta},\Psi\right)$ as a cell-
free massive MIMO (CF-mMIMO) system S.

######  Definition 11 (Feasible Pilot Assignment)

A feasible pilot assignment for a CF-mMIMO system $S$ is a well-defined,
surjective function $f:U\rightarrow\Psi$.

We state an easy-to-see lemma:

###### Lemma 1

Finding feasible pilot assignments for the users in a given cell-free massive
MIMO system $S$ can be done in polynomial time.

###### Proof

All we really need is the partition of the set of users $U$ such that no two
subsets in the partition intersect. As long as $K\gg\tau$, this is always
possible. A simple greedy approach to see that this is true would be to
randomly select $\tau-1$ users from $U$, and assign them to the first $\tau-1$
pilots in $\Psi$ respectively. Then assign the remaining $K-\tau+1$ users to
the remaining $\tau$-th pilot in $\Psi$. By construction, this is a feasible
pilot assignment for the system $S$. ∎

We now motivate our definition of the Pilot Assignment problem:

As mentioned earlier in Introduction Section 1.2, we assume that AP selection
for each user has already been done. Thus, every quantity in Equation (1) is a
constant. The pilot assignment problem seeks to find the optimum sets $O(k)$
for all $k$. Put simply, we seek a partition of the users into $\tau$ non-
empty disjoint sets so that the pilot contamination in the system is
minimized. How pilot contamination can be defined mathematically is still a
topic of great interest. In this vein, notice that only the first term in the
sum in the denominator of the huge fraction inside the logarithm expression in
Equation (1) changes with a change in the assignment of pilots to users.
Further, as noted before, only a single term in the denominator changes, as
the rest are all constants. Thus we focus on the term

$\rho^{u}\sum_{k^{\prime}\in O(k)}\eta_{k^{\prime}}\Bigl{(}\sum_{m\in
A(k)}\gamma_{km}\frac{\beta_{k^{\prime}m}}{\beta_{km}}\Bigl{)}^{2}\text{.}$

As the logarithm is an increasing function, a decrease in this term causes the
entire expression to increase. In many well-cited papers in the field [20, 19,
25, 27], the pilot contamination effect at the $k$-th user is denoted by the
term

$\sum\limits_{k^{\prime}\in O(k)}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}\text{.}$

We understand here that dropping all the constants multiplied with this term
technically reduces it to a _simpler_ form of the pilot contamination problem.
Thus, in this paper, we prove hardness results for this definition of the
pilot contamination problem. Since our goal is to minimize pilot contamination
in the system with an optimum pilot assignment for all the users, we shall
consider the sum of the above terms for all the users, i.e., we aim to
minimize

$\sum\limits_{k=1}^{K}\sum\limits_{k^{\prime}\in O(k)}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}\text{.}$

There is also some physical intuition behind dropping the above constants. The
large-scale coefficient for a user and an AP is higher when they are
geographically closer [22]. It is safe to assume that for a user $k$, AP
selection yields only those APs $m$ in the set $A(k)$ for which the large-
scale coefficients $\beta_{km}$ are reasonably high. The above equations tell
us that given a user $k$, the potential disturbance from users $k^{\prime}$ is
severe when the proximity between the interfering users $k^{\prime}$ and the
APs in the set $A(k)$ is higher than that between the user $k$ and the APs in
$A(k)$. In a way, we want to put those users $k^{\prime}$ in $O(k)$, whose
large-scale coefficients with respect to the APs that have been selected to
serve $k$ are low. In other words, they are farther from those APs than user
$k$.

To summarize the development so far, we have that given $M$ APs, $K$ users,
with each user assigned a set $A(k)\;(1\leq k\leq K)$ which denotes the
indices of the subset of APs serving it, large-scale coefficients $\beta_{km}$
between a user $k$ and AP $m$, and $\tau$ pilots, we need to find a partition
of the $K$ users into $\tau$ disjoint sets (where a set contains the users
served by the same pilot) such that

$\sum\limits_{k=1}^{K}\sum\limits_{k^{\prime}\in O(k)}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}$ (2)

is minimized, where $O(k)$ is the set of indices users $k^{\prime}$ with the
same pilot as user $k$, excluding user $k$. Note that since AP selection is
done before pilot assignment, the innermost summation remains untouched in
this optimization problem.

Now let the $\tau$ subsets of $U$ induced by $f$ be $V_{1},V_{2},\dots
V_{\tau}$. In Equation (2), observe the outer two summations. Given a user
$k$, we only have to consider those users $k^{\prime}$ which are served by the
same pilot as it. In other words, given a set in a partition, we must look at
all possible pairs of users within it. We must then look at the contribution
of the _pair_ $k,k^{\prime}$ to the second sum, which by symmetry turns out to
be

$\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{km^{\prime}}/\beta_{k^{\prime}m^{\prime}}\right)^{2}$
(3)

As mentioned in [25], we can regard the above term as the quantity of
interference (thus leading to potential pilot contamination) between users $k$
and $k^{\prime}$. Since the order or permutation of the elements of the pair
$k,k^{\prime}$ matters, each pair of elements in a partition contributes _two_
terms to the second sum.

We then rewrite the outer two summations in Equation (2) as a summation over
all possible pairs $k,k^{\prime}$ of Equation (3), and then a summation of
this over all sets in the partition:

$\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\Biggl{(}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{km^{\prime}}/\beta_{k^{\prime}m^{\prime}}\right)^{2}\Biggl{)}\\\
$ (4)

Thus, we get the following definition for the Pilot Assignment optimization
problem:

######  Definition 12 (Pilot Assignment Problem (PA))

Given a cell-free massive MIMO system $S$, we call the optimization problem

$\min\limits_{ffeasible}\sum\limits_{\begin{subarray}{c}k,k^{\prime}\in U\\\
f(k)=f(k^{\prime})\end{subarray}}\Biggl{(}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{km^{\prime}}/\beta_{k^{\prime}m^{\prime}}\right)^{2}\Biggl{)}$

the Pilot Assignment (PA) problem.

We now define a classical graph problem that shall be crucial in proving our
results.

######  Definition 13 (Min-$k$-Partition)

Given an undirected graph $G=(V,E)$ with $n$ vertices and weight
$\omega_{i,j}\in\mathbb{Q}_{+}$ for the edge joining vertices $i$ and $j\ \
\forall\;1\leq i,j\leq n$, the Min-$k$-Partition problem seeks to find a
partition $\mathcal{V}$ of $V$ into $k$ disjoint sets
$\\{V_{1},V_{2},\dots,V_{k}\\}$ such that the total weight of the edges with
endpoints within the same set is minimum.

The objective of the above problem can be formulated as:

$\min\limits_{\mathcal{V}=\\{V_{1},V_{2},\dots,V_{k}\\}}\hskip
2.84526pt\sum\limits_{p=1}^{k}\hskip 4.2679pt\sum\limits_{i,j\in
V_{p}}\omega_{i,j}$ (5)

Note that the Max-$k$-Cut problem referred to in Section 1.3 is the dual of
the Min-$k$-Partition problem. Moreover, both the Min-$k$-Partition and the
Max-$k$-Cut problems are known to be NP-hard [1, 6, 12].

We shall formally define both the optimization and decision versions of the
problem as per Definition 1 in Appendix 0.A. These can be referred to if the
reader wants an explicit definition of PA as a tuple.

##  3 Complexity results for PA

###  3.1 Primary results on complexity

To talk about the computational complexity of PA, we assume that all numerical
values appearing as input data are rational and that they are encoded in
binary form. We now present our first major theorem.

###### Theorem 3.1

The following results hold for the time complexity of PA:

  1. $(i)$

PA $\in$ NPO.

  2. $(ii)$

PA is NP-hard.

  3. $(iii)$

PA is strongly NP-hard.

###### Proof

  1.   2. $(i)$

It is recognizable in polynomial time whether a string encodes a tuple
representing a cell-free massive MIMO system, as it primarily involves a check
of the cardinality of multiple sets, and the dimension of a matrix. If all the
users and pilots are listed individually, then the encoding length of a
feasible pilot assignment for the users cannot exceed the encoding length of
the CF-mMIMO system. From Lemma 1, we know that it is decidable in polynomial
time if a pilot assignment is feasible. Finally, it is clear that Equation (4)
is computable in polynomial time. Therefore, PA $\in$ NPO.

  3. $(ii)$

We now present our proof of part $(ii)$, i.e., PA is NP-hard, by establishing
the following claim: Min-$k$-Partition $\leq_{T}^{p}$ PA.

Consider an arbitrary instance of the Min-$k$-Partition problem, specified by
a weighted graph $G=(V,E,\omega)$, where $\omega:E\rightarrow\mathbb{R}_{+}$
is a function mapping edges to their weights. We construct an instance of PA
as follows:

Set $K=|V|$. The set of users $U$ is set to be the set of vertices $V$. Thus,
$|U|=K$. The number of pilots $\tau$ is set to be $k$. This determines the set
$\Psi=\\{1,\dots,k\\}$. For all users indexed by $1\leq i\leq K$, set
$|A(i)|=1$. This determines $K$ number of APs. Since we know that in a
practical cell-free massive MIMO system, we have $M\gg K$, we could define
many dummy APs to achieve this condition. We set the total number of APs in
our PA instance as some arbitrarily large constant $M\gg K$, which determines
the set $\mathcal{A}=\\{1,\dots,K,\dots,M\\}$. Further, $\forall\;1\leq i\leq
K$, let $A(i)=\\{i\\}$. Thus, a single, distinct AP indexed by $i$ serves the
user $i$. Now, $\forall\;1\leq i\leq K$ and $\forall\;1\leq m\leq M$ set

$\beta_{im}=\begin{cases}1&\text{if $m=i$,}\\\
\sqrt{\frac{\omega((i,m))}{2}}&\text{if $m\neq i$ and $m\leq K$,}\\\
0&\text{otherwise.}\end{cases}$

This determines the matrix $\bm{\beta}$ in our instance of the problem.

$(\Rightarrow)$ If we have a solution to an instance of the Min-$k$-Partition
problem, then by Definition 13, we have a partition
$\mathcal{V}=\\{V_{1},V_{2},\dots,V_{k}\\}$ of the vertex set $V$ such that
the expression $\sum\limits_{t=1}^{k}\sum\limits_{i,j\in V_{t}}\omega((i,j))$
is minimized. By our construction, the set of vertices $V$ is the set of users
$U$ and $k$ is the cardinality of the set $\Psi$, $\tau$. Replacing $k$ by
$\tau$ and $i,j$ by the arbitrary indices $k,k^{\prime}$ to denote the users
in our constructed instance of the PA problem, we get that the minimized
equation is $\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\omega((k,k^{\prime}))$. Recall that the objective function to be
minimized in a general instance of PA is Equation (4), which can be simplified
to

$\displaystyle\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\Biggl{(}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{km^{\prime}}/\beta_{k^{\prime}m^{\prime}}\right)^{2}\Biggl{)}$
$\displaystyle=\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\Biggl{(}\left(\beta_{k^{\prime}k}/\beta_{kk}\right)^{2}+\left(\beta_{kk^{\prime}}/\beta_{k^{\prime}k^{\prime}}\right)^{2}\Biggl{)}$
$\displaystyle=\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\omega((k,k^{\prime}))$

Thus we have a solution to our PA problem instance.

$(\Leftarrow)$ By the above simplification of Equation (4), if we have a
solution for the above-constructed instance of PA, we end up minimizing the
expression

$\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\omega((k,k^{\prime}))$

Now, we map the users $k,k^{\prime}$ back to the vertices of the graph via
arbitrary indices $i,j$, and note that the number of pilots $\tau$ is in fact
the desired number of cuts, $k$. So we end up minimizing the expression

$\sum\limits_{t=1}^{k}\sum\limits_{i,j\in V_{t}}\omega((i,j))$

which represents the total weight of such edges which have both endpoints in
the same partition. Thus, due to the construction of our PA instance, we also
have a solution to the corresponding Min-$k$-Partition instance.

Therefore, the Min-$k$-Partition instance has a solution _if and only if_ if
the above PA instance has a solution. This proves our claim. Since
Min-$k$-Partition is NP-hard, we conclude that PA is NP-hard.

  4. $(iii)$

It is stated in [9] that Min-$k$-Partition is strongly NP-hard due to a
reduction from the Graph $k$-Colourability problem, which has been proven to
be strongly NP-complete [11]. As we could not find a reference for an explicit
proof of this fact in the literature, we give a simple proof of the
aforementioned reduction: The Chromatic Number or Graph $k$-Colourability is a
non-numeric decision problem which asks whether the vertices of a graph $G$
can be coloured using at most $k$ colours such that no two adjacent vertices
have the same colour. In other words, it asks if we can partition the vertices
into at most $k$ sets such that each of the sets is an independent set.

We give a simple Turing reduction from Graph $k$-Colourability to
Min-$k$-Partition as follows: Given an instance $(G,E,k)$ of the Graph
$k$-Colourability problem, associate to it an instance of Min-$k$-Partition
defined by $G=(V,E,\omega)$, such that $\omega:E\rightarrow 1$. It is easy to
see that $G$ is $k$-colourable if and only if the optimal solution to the
associated instance of Min-$k$-Partition yields a value of $0$. This is due to
the fact that a solution to the $k$-Colouring problem on $G$ induces $k$
independent sets in $G$. In our instance of Min-$k$-Partition, these $k$
independent sets translate to $k$ subsets of the set of vertices $V$ of the
graph, such that no two vertices in a given subset are adjacent. Thus, the
endpoints of any edge in $G$ must be in two different sets. This gives us the
minimum possible value of the sum of the weights of the edges with endpoints
in the same partition: $0$. Thus, we see that independent sets in $G$ give us
the optimum solution to the constructed instance of Min-$k$-Partition. On the
other hand, if the solution to our Min-$k$-Partition instance has a value of
$0$, then all the edges in $G$ have endpoints in disjoint sets of the
partition. This follows from the fact that the weight of each edge is 1. Thus,
the vertices in a given subset are pairwise disjoint, forming an independent
set. Colouring the $k$ independent sets in this partition of $V$ using $k$
different colours gives us the desired solution to the Graph $k$-Colourability
problem. ∎

A corollary of the above theorem follows immediately:

###### Corollary 1

For every $q\in\mathbb{Q}_{+}$, the decision version of PA is NP-complete.

###  3.2 Further results on approximability

The first theorem tells us that unless P $=$ NP, there exists no polynomial-
time algorithm to solve PA. We turn our attention to the more practical
aspects of tackling this problem. Instead of trying to obtain optimal
solutions, we look at how well we can approximate the optimal solution to the
problem in polynomial time. Since we are dealing with optimization problems
(as opposed to decision problems), we must be careful when giving a
polynomial-time reduction from one optimization problem to the other. While
the decision problems corresponding to most NP-hard optimization problems
admit a standard polynomial-time many-one (or Karp) reduction to each other,
the optimization problems do not share the same approximability properties.
This is due to the fact that many-one reductions do not always preserve the
measure function and, even if they do, they seldom preserve the quality of the
solutions. This is reflected in the approximability of the equivalent
Min-$k$-Partition and Max-$k$-Cut problems as well. We know that while
Max-$k$-Cut is APX-complete, Min-$k$-Partition is not in APX (see Appendix B
of [3]).

Thus, we appeal to Definition 9 to introduce a stronger kind of reducibility,
namely AP-reducibility. Although different types of approximation-preserving
reducibilities exist in the literature, AP-reducibility is sufficiently
general to incorporate the properties of almost all such reducibilities, while
also establishing a _linear relation_ between performance ratios.
Approximation-preserving reductions induce an order on optimization problems
based on their “difficulty” of being approximated. Approximation-preserving
reductions are also an essential tool for proving non-approximability results.

Next, we state four lemmas, which will help us prove our second theorem.

######  Lemma 2 ([3])

If P $\neq$ NP, exp-APX $\subset$ NPO.

###### Proof

While this fact is stated in [3], we give a detailed proof (with an example
mentioned in [3]) as follows:

Let $P=(I,\,SOL,\,m,\,\textup{goal})$ be a problem in NPO. Since $m$ is
computable in polynomial time, there exist $h$ and $k$ such that for any $x\in
I$ with $|x|=n$ and for any $y\in SOL(x)$, $m(x,y)\leq h2^{n^{k}}$. This is
because the range of possible values of $m(x,y)$ has an upper bound given by
$M=2^{p(|x|)}$ for some polynomial $p$, which is again due to the properties
of NPO problems which state that the length $|y|$ of any solution $y\in
SOL(x)$ is bounded by $q(|x|)$ for some polynomial $q$, and $m$ is computable
in polynomial time (see Definition 9). This implies that any feasible solution
has a performance ratio bounded by $h2^{n^{k}}$. Indeed, the polynomial bound
on the computation time of the measure function for all NPO problems implies
that they are $h2^{n^{k}}$-approximable for some $h$ and $k$. This seems to
imply that the classes exp-APX and NPO are the same. However, we note that
there exist several problems in NPO for which it is hard even to decide
whether any feasible solution exists, (and thus to find such a feasible
solution) unless P $=$ NP. An example of such a problem is the Minimum
$\\{0,1\\}$-Linear Programming problem, which belongs to NPO. The problem
instance consists of a matrix $A\in\mathbb{Z}^{m\times n}$ and vectors
$b\in\mathbb{Z}^{m}$, $w\in\mathbb{N}^{n}$. The problem asks for a solution
$x\in\\{0,1\\}^{n}$ such that $Ax\geq b$, and the measure function
$\sum\limits_{i=1}^{n}w_{i}x_{i}$ is minimized. Given an integer matrix $A$
and an integer vector $b$, deciding whether a binary vector $x$ exists such
that $Ax\geq b$ is NP-hard, as the Satisfiability problem is polynomial-time
reducible to this decision problem (see Example 1.10 in Section 1.3.1, Chapter
1 of [3]). This implies that, if P $\neq$ NP, then Minimum $\\{0,1\\}$-Linear
Programming does not belong to exp-APX. ∎

###### Lemma 3

The polynomial-time reduction from Min-$k$-Partition to PA given in Theorem
$3.1.($ii$)$ is an AP-reduction with $\alpha=1$.

###### Proof

Consider an instance $G=(V,E,\omega)$ of Min-$k$-Partition, we need to
determine the function $f$ that maps it to an instance of PA. A general
instance of PA is determined by the tuple
$\left(\mathcal{A},U,\\{A(k)\\}_{k=1}^{K},\bm{\beta},\Psi\right)$. Recall the
definition of AP-reduction from Definition 9. From our reduction, we get that
$f:(V,E,\omega)\mapsto\left(\\{1,\dots,|V|,\dots,M\\},\,V,\,\\{i\\}_{i=1}^{|V|},\,\bm{\beta},\,\\{1,\dots,k\\}\right)$,
where $M$ is an arbitrary constant such that $M\gg|V|$, and the $im$-th
element of the matrix $\bm{\beta}$ is $\beta_{im}=1$ if $m=i$,
$\sqrt{\frac{\omega((i,m))}{2}}$ if $m\neq i$ and $m\leq K$, and 0 otherwise.
Moreover, if $h$ is the feasible assignment that forms the solution of our
constructed instance of PA, then the partition of vertices
$\mathcal{V}=\\{V_{1},V_{2},\dots,V_{k}\\}$ that forms the solution of our
original Min-$k$-Partition instance is defined as $V_{t}=\\{i\,|\,h(i)=t\\}$
where $i\in V$. We set $g:(G,h)\mapsto\mathcal{V}$, where $V_{t}=\\{k\,|\,k\in
U\;\text{and}\;h(k)=t\\}\quad\forall\;1\leq t\leq\tau$. Notice that $f$ and
$g$ do not depend on the performance ratio.

Finally, for any instance $G$ of Min-$k$-Partition, with $S=f(G)$ as the
constructed instance of PA, $h$ as the solution of $S$, and
$\mathcal{V}=g(G,\mathcal{V})$ as the solution to the original instance $G$ of
Min-$k$-Partition, we see that
$m_{\textsc{M$k$P}}(G,\mathcal{V})=m_{\textsc{PA}}(S,h)$ (where M$k$P is short
for Min-$k$-Partition), by the nature of the constructed instances and
solutions. We conclude that $f$ and $g$ satisfy the AP-condition with
$\alpha=1$, and thus the polynomial-time reduction described above is an AP-
reduction. ∎

###### Lemma 4

PA $\leq_{AP}$ Min-$k$-Partition with $\alpha=1$.

###### Proof

Since we’ve proved that the decision version of PA is NP-complete, it follows
from the definition of NP-completeness that PA and Min-$k$-Partition are
equivalently hard. We first give an explicit polynomial-time reduction from PA
to Min-$k$-Partition, and then prove that it is in fact an AP-reduction.

Consider an arbitrary instance of PA, specified by the cell-free massive MIMO
system $S=(\mathcal{A},U,A(k),\bm{\beta},\Psi)$ with
$|\mathcal{A}|=M,\,|U|=K,\,|\Psi|=\tau$. We construct an instance of
Min-$k$-Partition as follows: Define a _complete_ graph $G=(V,E,\omega)$
(where $\omega:E\rightarrow\mathbb{R}_{+}$ is a function that maps the edges
in our graph to positive real values), by setting $V=U$. By construction, we
have $|V|=K$ and $|E|=\frac{K(K+1)}{2}$. For any edge $(k,k^{\prime})\in E$,
where $k,k^{\prime}\in V$, we set

$\omega((k,k^{\prime}))=\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime},m}/\beta_{k,m}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{k,m^{\prime}}/\beta_{k^{\prime},m^{\prime}}\right)^{2}.$

The weight function $\omega$ defined above satisfies a symmetric property,
i.e., $\omega((k,k^{\prime}))=\omega((k^{\prime},k))$. It is important to note
that we set the value of $k$ that is referred to in the title of the
Min-$k$-Partition problem to $\tau$. So we have constructed an instance of a
Min-$\tau$-Partition problem.

($\Rightarrow$) If we have a solution to an instance of PA, then we have
minimized the optimization function given by Equation (4), which we state
again:

$\sum\limits_{t=1}^{\tau}\sum\limits_{k,k^{\prime}\in
V_{t}}\Biggl{(}\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime}m}/\beta_{km}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{km^{\prime}}/\beta_{k^{\prime}m^{\prime}}\right)^{2}\Biggl{)}$

But notice that the objective function to be minimized in a general instance
of the Min-$k$-Partition problem is $\sum\limits_{t=1}^{k}\sum\limits_{i,j\in
V_{t}}\omega((i,j))$. By the construction of our instance of the
Min-$k$-Partition problem, the users $U$ form the vertices $V$ of the graph
and the cardinality $\tau$ of the set of pilots $\Psi$ is $k$ (which is in the
title of the problem, denoting the number of subsets of the vertices).
Replacing $\tau$ by $k$ and the user indices $k,k^{\prime}$ by the arbitrary
indices $i,j$ to denote the vertices of our graph, we get that the function
minimized by solving the PA instance is

$\displaystyle\sum\limits_{t=1}^{k}\sum\limits_{i,j\in
V_{t}}\Biggl{(}\sum\limits_{m\in
A(i)}\left(\beta_{jm}/\beta_{im}\right)^{2}+\sum\limits_{m^{\prime}\in
A(j)}\left(\beta_{im^{\prime}}/\beta_{jm^{\prime}}\right)^{2}\Biggl{)}=$
$\displaystyle\sum\limits_{t=1}^{k}\sum\limits_{i,j\in V_{t}}\omega((i,j))$

Therefore, we have a solution to our instance of the Min-$\tau$-Partition
problem.

($\Leftarrow$) By the above argument, it is clear that if we have a solution
to our constructed instance of the Min-$\tau$-Partition problem, we also have
a solution to the corresponding PA instance by a reverse change of indices, as
seen in Theorem $3.1.($ii$)$.

Hence, we have shown an explicit polynomial-time reduction from PA to
Min-$k$-Partition. What remains to be verified is that this is an AP-
reduction. To see this, consider an instance of PA given by
$S=\left(\mathcal{A},U,\\{A(k)\\}_{k=1}^{K},\bm{\beta},\Psi\right)$. A general
instance of Min-$k$-Partition is given by an undirected graph
$G=(V,E,\omega)$. In the above reduction, we have that $G$ is a complete graph
with $V=U$ and $\omega((i,j))=\sum\limits_{m\in
A(i)}\left(\beta_{j,m}/\beta_{i,m}\right)^{2}+\sum\limits_{m^{\prime}\in
A(j)}\left(\beta_{i,m^{\prime}}/\beta_{j,m^{\prime}}\right)^{2}\quad\forall\>i,j\in
V$. Recall Definition 9. Thus we have
$f:\left(\mathcal{A},U,\\{A(k)\\}_{k=1}^{K},\bm{\beta},\Psi\right)\mapsto\left(U,E(K_{U}),w\right)$
where $E(K_{U})$ denotes the set of edges of the complete graph on the
vertices denoted by $U$, and $\omega((k,k^{\prime}))=\sum\limits_{m\in
A(k)}\left(\beta_{k^{\prime},m}/\beta_{k,m}\right)^{2}+\sum\limits_{m^{\prime}\in
A(k^{\prime})}\left(\beta_{k,m^{\prime}}/\beta_{k^{\prime},m^{\prime}}\right)^{2}$.
Further, if we have obtained the partition
$\mathcal{V}=\\{V_{1},V_{2},\dots,V_{k}\\}$ of the vertex set $V$ in our
constructed instance of Min-$k$-Partition, we get that the feasible assignment
$h$ which is the solution to the corresponding PA instance is defined as
$h(k)=t\ \text{such that}\;k\in V_{t}\quad\forall\>k\in U$. We set
$g:(S,\mathcal{V})\mapsto h$, where $h(i)=t\ \text{such that}\ i\in
V_{t}\in\mathcal{V}$. Notice that $f$ and $g$ do not depend on the performance
ratio.
Finally, for any instance $S$ of PA, with $G=f(S)$ as the constructed instance
of Min-$k$-Partition, $\mathcal{V}$ as the solution of $G$, and
$h=g(S,\mathcal{V})$ as the solution to the original instance $S$ of PA, we
see that $m_{\textsc{PA}}(S,h)=m_{\textsc{M$k$P}}(G,\mathcal{V})$ (where M$k$P
is short for Min-$k$-Partition), by the nature of the constructed instances
and solutions. We conclude that $f$ and $g$ satisfy the AP-condition with
$\alpha=1$, and thus the polynomial-time reduction described above is an AP-
reduction. ∎

Observe that an AP-reduction from PA to Min-$k$-Partition is important from a
practical viewpoint to prove positive approximation results for PA. In
particular, it allows us to translate the performance ratios that exist for
the approximation of special cases of Min-$k$-Partition (e.g., when $k$ is $2$
or $3$) into performance ratios for the corresponding PA problem [17]. On the
other hand, an AP-reduction from Min-$k$-Partition to PA is necessary to prove
negative approximability results for PA. We recall a few results on the
approximability of Min-$k$-Partition stated in [8, 17] in the form of a lemma.

###### Lemma 5

Assuming P $\neq$ NP, the following statements hold with respect to the
computational complexity of Min-$k$-Partition:

  1. $(i)$

The problem is not in APX. [21]

  2. $(ii)$

For $k\geq 3$, it is NP-hard to approximate Min-$k$-Partition within $O(|E|)$,
even when restricting the instances to graphs with
$|E|=\Omega(|V|^{2-\epsilon})$, for a fixed $\epsilon$, $0<\epsilon<1$. [17]

  3. $(iii)$

No polynomial time algorithm can achieve a better performance ratio than 1.058
in the case of $k=2$. [15]

  4. $(iv)$

In case of $k=2$, a polynomial time algorithm with a performance guarantee of
$\log|V|$ is known. [13]

  5. $(v)$

In case of $k=3$, a polynomial time algorithm with a performance guarantee of
$\epsilon|V|^{2}$ for any $\epsilon>0$ is known. [17]

Using Lemmas 2, 3, 4 and 5, we are now ready to prove the following theorem on
the approximability of PA, inspired by [8, Section 3.2.3].

###### Theorem 3.2

Assuming P $\neq$ NP, The following statements hold true for the Pilot
Assignment problem:

  1. $(i)$

PA is not in APX, however it is in exp-APX.

  2. $(ii)$

An approximation of PA within $\mathcal{O}(K^{2})$ for $\tau\geq 3$ is
impossible in polynomial time.

  3. $(iii)$

In the special case of $\tau=2$, while no polynomial time algorithm can
achieve a performance ratio better than 1.058, there exists an algorithm with
a performance guarantee of $\log|K|$ in polynomial time.

  4. $(iv)$

In the special case of $\tau=3$, there exists a polynomial time algorithm with
a performance guarantee of $\epsilon|K|^{2}$ for any $\epsilon>0$.

###### Proof

  1.   2. $(i)$

From Lemmas 1 , 2 and 5.(i), the result follows immediately.

  3. $(ii)$

From Lemma 5.(ii), we have that Min-$k$-Partition cannot be approximated
within $\mathcal{O}(|E|)$ in polynomial time for $k\geq 3$. Further, in PA, we
typically deal with complete (or dense) graphs. So we have that
$|E|=\Omega(K^{2})$, where $K$ is the number of users, or vertices in the
graph. The number of pilots available, or the number of partitions required in
the graph is $\tau$. Hence, using Lemma 3, we get that unless P $=$ NP, it is
impossible to approximate PA within $\mathcal{O}(K^{2})$ in polynomial time
for $\tau\geq 3$.

  4. $(iii)$

The first part of this claim follows from Lemma 3 and Lemma 5.(iii), while the
second part follows from Lemma 4 and Lemma 5.(iv).

  5. $(iv)$

As above, this follows easily from Lemma 4 and Lemma 5.(v). ∎

##  4 Conclusion

In this paper, we studied the inherent hardness of the pilot assignment
problem and found provable guarantees on the quality of achievable solutions
to the problem. We defined the cell-free massive MIMO system mathematically,
which is crucial in any theoretical study of this problem. We further proved
that PA is strongly NP-hard, and at the same time, does not belong to the APX
class of problems. The big picture here is that, to the best of our knowledge,
our paper is the first to study PA from a theoretical computer science
perspective, providing complexity results for the problem.

Recall that while the Max-$k$-Cut problem (see Section 1.3) has been used to
develop the current state of the art for PA, our contribution here is to focus
on its dual problem, the Min-$k$-Partition. Due to the varying nature of the
approximability of these optimization problems, it is better to apply a
heuristic for the Min-$k$-Partition problem to solve PA. This is due to the
fact that the performance ratio of any heuristic/algorithm designed for
Min-$k$-Partition can be translated directly for PA. There is extensive
research on formulating and solving the Min-$k$-Partition problem using Linear
Programming (LP) and Semi-definite Programming (SDP) relaxation approaches [6,
8, 9, 10, 14, 23]. This remains an active area of research. Further research
in this area seems to be a step in the right direction towards finding better
optimal solutions for PA.

It is also interesting to note that there has been very little research on the
parameterized complexity of the Min-$k$-Partition problem. This leads us to
believe that the problem may not be FPT (fixed-parameter tractable). A
practical question that arises here is if this problem admits an XP algorithm
for some suitable parameter. Such an algorithm may yield a pilot assignment
scheme with superior performance, depending on the parameter used in the
algorithm.

####  4.0.1 Acknowledgements.

The authors thank Prof. David Manlove for his feedback on drafts of this
paper. Further, we gratefully acknowledge the support of Dr. Yusuf Sambo and
Dr. Abdulrahman Al Ayidh in understanding the problem as well as its existing
heuristics, during the early stages of this project. This work was done while
S. Prusty was working on her Master’s project at the School of Computing
Science, University of Glasgow. S. Prusty would like to thank DST-INSPIRE,
Government of India for their support via the Scholarship for Higher Education
(SHE) programme.

##  Appendix 0.A Appendix for Section 2.3

###  0.A.1 Definitions of the Decision and Optimization versions of PA

######  Definition 14 (Decision version of PA)

The decision version of PA is defined by a triple
$(I_{\textsc{PA}},q,SOL_{\textsc{PA}})$, where $I_{\textsc{PA}}$ is the set of
all cell-free massive MIMO systems $S$, $q\in\mathbb{Q}_{+}$ and
$SOL_{\textsc{PA}}:I_{\textsc{PA}}\rightarrow\\{0,1\\}$ is a function that
assigns to each pair $(S,q)$ either the value 0 or 1. The assignment is done
based on whether an instance $S$ has a value of at most $q$ for Equation
$(\ref{eq6})$. The problem asks if there exists an instance $S\in
I_{\textsc{PA}}$ such that given a number $q$, $SOL_{\textsc{PA}}(S,q)=1$.

######  Definition 15 (Optimization version of PA)

The minimization problem PA is characterized by the tuple
$(I_{\textsc{PA}},SOL_{\textsc{PA}},m_{\textsc{PA}},\textsc{min})$, where
$I_{\textsc{PA}}$ is the set of all cell-free massive MIMO systems $S$
$($instances of PA$)$, $SOL_{\textsc{PA}}$ is a function that assigns every
instance $S\in I_{\textsc{PA}}$ to its set of feasible pilot assignments $f$,
and $m_{\textsc{PA}}$ is a measure function that assigns to each pair $(S,f)$,
where $S\in I_{\textsc{PA}}$ and $f\in SOL_{\textsc{PA}}(S)$, the value of
Equation $(\ref{eq6})$. The problem asks for a given instance $S$, a feasible
assignment $f\in SOL_{\textsc{PA}}(S)$ such that
$m_{\textsc{PA}}(S,f)=\min\limits_{f^{\prime}\in
SOL_{\textsc{PA}}(S)}m_{\textsc{PA}}(S,f^{\prime})$.

## References

  * [1] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (May 1998), https://doi.org/10.1145/278298.278306
  * [2] Attarifar, M., Abbasfar, A., Lozano, A.: Random vs structured pilot assignment in cell-free massive mimo wireless networks. In: 2018 IEEE International Conference on Communications Workshops (ICC Workshops). pp. 1–6. IEEE (2018), https://doi.org/10.1109/ICCW.2018.8403508
  * [3] Ausiello, G., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., Kann, V.: Complexity and Approximation. Springer Berlin, Heidelberg, 1 edn. (1999), https://doi.org/10.1007/978-3-642-58412-1
  * [4] Buzzi, S., D’Andrea, C., Fresia, M., Zhang, Y.P., Feng, S.: Pilot assignment in cell-free massive mimo based on the hungarian algorithm. IEEE Wireless Communications Letters 10(1), 34–37 (2021), https://doi.org/10.1109/LWC.2020.3020003
  * [5] Chen, S., Zhang, J., Zhang, J., Björnson, E., Ai, B.: A survey on user-centric cell-free massive mimo systems. Digital Communications and Networks 8(5), 695–719 (2022), https://doi.org/10.1016/j.dcan.2021.12.005
  * [6] Chopra, S., Rao, M.R.: The partition problem. Mathematical Programming 59, 87–115 (1993), https://doi.org/10.1007/BF01581239
  * [7] Duan, Z., Zhao, F., Wang, Y.: Pilot allocation and data power optimization based on access point selection in cell-free massive mimo. Wirel. Commun. Mob. Comput. 2022 (Jan 2022), https://doi.org/10.1155/2022/4044783
  * [8] Eisenblätter, A.: Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds. Ph.D. thesis (2001)
  * [9] Fairbrother, J., Letchford, A.N.: Projection results for the k-partition problem. Discrete Optimization 26, 97–111 (2017), https://doi.org/10.1016/j.disopt.2017.08.001
  * [10] Frieze, A., Jerrum, M.: Improved approximation algorithms for max k-cut and max bisection. Algorithmica 18(1), 67–81 (May 1997), https://doi.org/10.1007/BF02523688
  * [11] Garey, M.R., Johnson, D.S.: “Strong” NP-completeness results: Motivation, examples, and implications. J. ACM 25(3), 499–508 (July 1978), https://doi.org/10.1145/322077.322090
  * [12] Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1990)
  * [13] Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing 25(2), 235–251 (1996), https://doi.org/10.1137/S0097539793243016
  * [14] Ghaddar, B., Anjos, M.F., Liers, F.: A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Annals of Operations Research 188, 155–174 (2011), 10.1007/s10479-008-0481-4
  * [15] Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (Jul 2001), https://doi.org/10.1145/502090.502098
  * [16] Interdonato, G., Björnson, E., Quoc Ngo, H., Frenger, P., Larsson, E.G.: Ubiquitous cell-free massive mimo communications. EURASIP Journal on Wireless Communications and Networking 2019(1), 1–13 (Aug 2019), https://doi.org/10.1186/s13638-019-1507-0
  * [17] Kann, V., Khanna, S., Lagergren, J., Panconesi, A.: On the hardness of approximating max k-cut and its dual. Tech. rep. (1997)
  * [18] Li, N., Gao, Y., Xu, K.: On the optimal energy efficiency and spectral efficiency trade-off of cf massive mimo swipt system. EURASIP J. Wirel. Commun. Netw. 2021(1) (Aug 2021), https://doi.org/10.1186/s13638-021-02035-w
  * [19] Liu, H., Zhang, J., Jin, S., Ai, B.: Graph coloring based pilot assignment for cell-free massive mimo systems. IEEE Transactions on Vehicular Technology 69(8), 9180–9184 (2020), https://doi.org/10.1109/TVT.2020.3000496
  * [20] Ngo, H.Q., Ashikhmin, A., Yang, H., Larsson, E.G., Marzetta, T.L.: Cell-free massive mimo versus small cells. IEEE Transactions on Wireless Communications 16(3), 1834–1850 (2017), https://doi.org/10.1109/TWC.2017.2655515
  * [21] Sahni, S., Gonzalez, T.: P-complete approximation problems. J. ACM 23(3), 555–565 (07 1976), https://doi.org/10.1145/321958.321975
  * [22] Schwengler, T.: Wireless and Cellular Communications (paperback). Lulu.com (2019), https://books.google.co.in/books?id=afdbzQEACAAJ
  * [23] Wang, G., Hijazi, H.L.: Exploiting sparsity for the min k-partition problem. Mathematical Programming Computation 12, 109 – 130 (2017). https://doi.org/10.1007/s12532-019-00165-3, https://doi.org/10.1007/s12532-019-00165-3
  * [24] Yin, X., Dai, J., Wang, J., Zhao, J., Cheng, C.: Pilot allocation and power control in cell-free massive mimo systems. Wireless Personal Communications 109, 2489 – 2506 (2019), https://doi.org/10.1007/s11277-019-06694-3
  * [25] Zeng, W., He, Y., Li, B., Wang, S.: Pilot assignment for cell free massive mimo systems using a weighted graphic framework. IEEE Transactions on Vehicular Technology 70(6), 6190–6194 (2021), https://doi.org/10.1109/TVT.2021.3076440
  * [26] Zhang, J., Björnson, E., Matthaiou, M., Ng, D.W.K., Yang, H., Love, D.J.: Prospective multiple antenna technologies for beyond 5g. IEEE Journal on Selected Areas in Communications 38(8), 1637–1660 (2020), https://doi.org/10.1109/JSAC.2020.3000826
  * [27] Zhang, Y., Cao, H., Zhong, P., Qi, C., Yang, L.: Location-based greedy pilot assignment for cell-free massive mimo systems. In: 2018 IEEE 4th International Conference on Computer and Communications (ICCC). pp. 392–396. IEEE (2018), https://doi.org/10.1109/CompComm.2018.8780756