Topological sorting of a DAG where special vertices have to come in even groups Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine whether $G$ has a topological sort $v_1 &lt; \cdots &lt; v_n$ having the following property: when the sort is enumerating special vertices, then it must always enumerate an even number of them consecutively. In other words, at every step of the sort, we can either take one normal vertex, or take two special vertices one after the other, and we repeat this. Formally, for any contiguous subword $v_i, \ldots, v_{j-1}$ of $v_1, \ldots, v_n$ where all vertices are special, and which is maximal (either $i=1$ or $v_{i-1}$ is not special; and either $j = n-1$ or $v_j$ is not special), then we require that $j-i$ is even.

Is this decision problem NP-hard, or is it in PTIME?

Of course, a necessary condition is that there is an even number of special vertices. But this is not sufficient: the totally ordered graph $w_1 &lt; v_2 &lt; w_3$ with $w_1$ and $w_3$ special is a negative instance, as its only topological sort does not satisfy the condition. In general, the idea is that we can always freely consume non-special vertices, but we must be careful in which special vertices we consume to avoid getting stuck with an odd number of special vertices that block the rest of the graph from being enumerated. Consider for instance a DAG defined by $w_1 &lt; v &lt; w_2$ and $w_3 &lt; w_4$ with the $w_i$ being special and $v$ non-special, then the topological sort $w_1 &lt; w_3 &lt; v &lt; w_2 &lt; w_4$ satisfies the condition, but if we want to start a topological sort by $w_3 &lt; w_4$ then we are "stuck".

[This relates to work on mine about constrained topological sorting. It is listed as an open problem here (search for "Open problem: Is the same true of the CTS problem?"). We have a PTIME algorithm (Proposition 4.6 of the paper) for the much easier problem where $G$ is a disjoint union of chains (total orders), which is a rather intuitive but not entirely trivial greedy algorithm.]

Update (thanks @Louis): The problem presented here is related to another variant of topological sort, which seems unknown but pretty natural, which I'd call "two by two" or "pairwise" topological sorting. This is the problem where you are given a DAG $G = (V, E)$ with an even number of vertices, and you want to decide if there exists a topological sort $v_1 &lt; \cdots &lt; v_n$ where we take vertices two by two (with the second vertex already being available before having taken the first vertex), formally we add the condition that for all $0 \leq k &lt; (n/2)-1$, the vertices $v_{2k+1}$ and $v_{2k+2}$ are incomparable. I do not know the complexity of this problem, either. This problem reduces to the problem asked in my question (make all vertices special, and add a non-special vertex at the middle of every edge), in fact my problem is equivalent to a generalization of this problem.

I also don't know the complexity of the variant where we replace two by some other constant $k$, i.e., my problem where special vertices must be taken in groups of multiples of $k$, or the "$k$ by $k$" topological sorting problem. Any insights about their complexity are also welcome.
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.