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...