Manber's graph-partitioning implementation
How do I check for the "preference" of non queues vertices?


The previous step was

          if switching v to the opposite set improves the sum of weights then
             switch v;


so clearly you already know how to check for the preference of a vertex. Whether or not it is in the queue is immaterial.

To do it efficiently requires some additional data storage and pre-calculation which is not explicitly described in the pseudocode. In more detail,

Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times
       randomly assign each vertex to either V1 or V2 with equal probability;

       initialise two arrays of edge weight sums, internalSums and externalSums
       for each edge e = (s, t) in E do
          if s and t are in the same partition
             increment internalSums[s] and internalSums[t] by weight(e)
          else
             increment externalSums[s] and externalSums[t] by weight(e)

       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if internalSums[v] &gt; externalSums[v]
             switch v;
             swap internalSums[v] and externalSums[v]
             for each edge e = (v, u) in E do
                update internalSums[u] and externalSums[u] appropriately
                if u is not in the queue and internalSums[u] &gt; externalSums[u]
                   enqueue u
       store the best solution to date;





  Is it even needed? I've implemented the algorithm without this part and it seems working as intended.


I must confess that I would be unable to distinguish easily between the algorithm working as intended and the algorithm selecting a purely random partition and skipping the rest of the process.