When they solve $Av=-b$ the assumption is that $A$ is non-singular. Whenever $A$ is singular the problem can either have no solution, or infinitely many solutions. In their case I believe it is the latter. Remember that $v = (p,s)$. What they say is that they set the solution for $p$ to be the edge midpoint: $p=\frac{p_1+p_2}{2}$ and then plug that into the equation to reduce the system:
\begin{align}
-b = Av \iff -\begin{bmatrix} b_1\\ b_2\end{bmatrix} =
\begin{bmatrix}
A_{11} & A_{12}\\
A_{21} & I
\end{bmatrix}
\begin{bmatrix}
p \\ s \end{bmatrix} =
\begin{bmatrix} A_{11} \\ A_{21}\end{bmatrix}p+ \begin{bmatrix} A_{12} \\ I \end{bmatrix} s.
\end{align}
If you assume the system is consistent, then $s = -b_2 - A_{21}p$. If the system is inconsistent, then you can try to find the solution that least violates it as:
$$(A_{12}^TA_{12}+I)s = -A_{12}^T(b_1+A_{11}p) - (b_2+A_{21}p).$$
I suppose the system ought to be consistent though.

Edit:

Here's a more general approach as to how you can factorize such problems if you assume $A_{22}$ is an invertible matrix (it is essentially block Gaussian elimination):

\begin{align}
\begin{bmatrix} b_1 \\ b_2\end{bmatrix} &=
\begin{bmatrix}
A_{11} & A_{12} \\ A_{21} & A_{22}
\end{bmatrix}
\begin{bmatrix}
x_1\\ x_2
\end{bmatrix}
\\
\begin{bmatrix}
b_1 \\ b_2 
\end{bmatrix}
&= \begin{bmatrix}
A_{11}x_1 + A_{12}x_2 \\
A_{21}x_1 + A_{22}x_2
\end{bmatrix}
\\
\begin{bmatrix}
b_1\\ 
A_{22}^{-1}(b_2 - A_{21}x_1)
\end{bmatrix} 
&=
\begin{bmatrix}
A_{11}x_1 + A_{12}x_2
\\
x_2
\end{bmatrix} 
\\
\begin{bmatrix}
b_1 - A_{12}A_{22}^{-1}b_2 \\
A_{22}^{-1}(b_2 - A_{21}x_1)
\end{bmatrix}
&=
\begin{bmatrix}
(A_{11}-A_{12}A_{22}^{-1}A_{21})x_1 \\ x_2
\end{bmatrix}
\end{align}

In your case $A_{22} = I$ so the inverse is just $I$. If the Schur complement $[A/A_{22}]= A_{11}-A_{12}A_{22}^{-1}A_{21}$ is invertible, then 
$$x_1 = [A/A_{22}]^{-1}(b_1 - A_{12}A_{22}^{-1}b_2), \quad x_2 = b_2 - A_{21}x_1.$$

But it could happen that the Schur complement is not invertible. If $b_1 - A_{12}A_{22}^{-1}b_2$ is in the range of $[A/A_{22}]$ you have infinitely many solutions, since if $x_1^*$ is a solution, and $w$ is a non-zero vector from the kernel of $[A/A_{22}]$, then also $x_1^* + \alpha w$ is a solution.
Having one such solution $x_1^*$ you can compute $x_2^* = b_2 - A_{21}x_1^*$. In the paper they set $x_1^* = \frac{p_1+p_2}{2}$. I haven't proven that this is necessarily a solution for their matrix though. If it is not, then what they are doing is potentially wrong.

The other case is that $b_1 - A_{12}A_{22}^{-1}b_2$ is 
not in the range of $[A/A_{22}]$. Then there are no solutions. But you can try for the closest thing to a solution in an $L_2$ sense. Then $$x_1^+ = [A/A_{22}]^+(b_1 - A_{12}A_{22}^{-1}b_2),$$
where $[A/A_{22}]$ is the Moore-Penrose inverse. You may again set $x_2 = b_2 - A_{21}x_1^+$. 

Note that in their case the Schur complement is:

$$[A/A_{22}] = A_{11}-A_{12}A_{22}^{-1}A_{21} = nn^T.$$