Topological sorting of a DAG where special vertices have to come in even groups
The problem you are calling "two-by-two" topological sorting is the Two Processor Scheduling Problem (unit-length jobs, under precedence constraints given by a partial order on the jobs -- i.e., the DAG).  The partial order on the jobs constrains them so that if x&lt;y then job y cannot be started until job x is completed.  Shelling the vertices of the DAG in pairs is like taking two unit-length jobs at a time to schedule on the two identical processors; a schedule with makespan n/2 is possible only if the DAG can be shelled in incomparable pairs, as required in your problem.

It is solvable in linear time, i.e., O(n+m) where n, m are number of, respectively, vertices and edges of the DAG. (Gabow, Gabow and Tarjan).  Earlier work by Coffman and Graham is a simpler but asymptotically not quite as fast algorithm; and Fujii, Kasami and Ninomiya also provide a poly-time algorithm. The Gabow and Tarjan algorithm has the advantage that you don't have to find the transitive reduction or transitive closure of the DAG first -- you can use it directly on the DAG.

I don't know the status of your original problem, though, where the distinguished vertices must be scheduled in blocks of even size.