Understanding constrained QAOA

I’m trying to understand how QAOA solves the MIS problem. In the original paper on QAOA (arxiv:1411.4028), section VII seems to talk about how constraints can be imposed on the problem by choosing the mixer hamiltonian appropriately. I don’t understand how exactly this works though, so if someone could explain the math behind this (or point me to a relevant resource), that would be really great.

The paper phrases the maximum independent set problem as
maximize $\sum z_j$
subject to
${z_i}$ represents an independent subset.
Here the string z belonging to the independent subset is the constraint, where $\sum z_j$ is the objective.
Hence $C=\sum z_j$ is one of the Hamiltonian.
The other Hamiltonian $B$ connects an independent set to another one with Hamming distance 1.

For example, if a graph of 3 vertices (0,1,2) has edges between 0 and 1. The possible independent set will be ${000,100,010,001,101,010}$. So $B$ will satisfy
$\langle 000|B|100\rangle=1$, $\langle 000|B|010\rangle=1$, etc.

So applying $B$ is sort of like a quantum walk.

The algorithm then proceeds by alternatively evolving between $B$ and $C$, starting from $|0...0\rangle$. starting from the ground state of $C$, to the ground state of $-B$, to the ground state of $-C$.

I have no idea how $B$ can be constructed, as it is the flip operator restricted to the set of independent sets.

Below are my wild guess on how to construct it.
I suppose $B$ can be formally written as $B=(\sum \sigma_x) P$, where $P$ is the projection from all possible strings to the set of independent sets. If one has the original graph, one can construct a two-body Hamiltonian where there is interaction between vertices if there is an edge between them. Then the projection operator is simply the projection to the zero eigenspace of this Hamiltonian...

@eltonjohn007 Thanks for the reply! The part where you mentioned that we go from the ground state of $C$ to the ground state of $-B$ and in turn to the ground state of $-C$ was really insightful. But I still have doubts about our choice of $B$.
I drew out the matrix for $B$ from your example and one thing that made sense to me is that the last two rows and columns corresponding to $110$ and $111$ are filled with 0s and that this would be true for any positive power of $B$ as well.
$$B=\begin{bmatrix}
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}$$
Since $e^{-iB\beta}$ is the Identity plus a linear combination of powers of $B$ (Taylor series expansion), we can be sure that this operator will never take a legal bitstring to an illegal bitstring. But then why do we worry about the Hamming distance when defining $B$? What if, for example, I replaced $B$ with a matrix whose entries were $1$ everywhere except where the row or column corresponds to that of an illegal bitstring?
$$B=\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}$$
Would this work just as well? I’m fairly certain I’m missing something.

The part about going from the ground state of $C$ to the ground state of $-B$ and then to the ground state of $-C$ is really the intuition behind the adiabatic version. The QAOA version will probably never hit the ground state of $-B$.

You are right that in the simple example I gave, the second $B$ would also work in principle. $B$ is a transition matrix we construct. If you write $B$ in Pauli basis, your $B$ will involve higher order terms, which might be difficult to implement. If $B$ is to transition between states of Hamming distance 1, then it is much easier to implement, it will be just like $\sum \sigma_x$ restricted to the valid states.

Again I do not have any idea how to implement this in practise, especially the part on how to restrict to the valid states.

I see. So it's a matter of convenience in the math and subsequent implementation. Thanks a lot for your responses :)