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

<p>It is solvable in linear time, i.e., O(n+m) where n, m are number of, respectively, vertices and edges of the DAG. (<a href="https://dl.acm.org/doi/pdf/10.1145/322326.322335" rel="nofollow noreferrer">Gabow</a>, <a href="https://www.sciencedirect.com/science/article/pii/0022000085900145" rel="nofollow noreferrer">Gabow and Tarjan</a>).  Earlier work by <a href="https://link.springer.com/article/10.1007/BF00288685" rel="nofollow noreferrer">Coffman and Graham</a> 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.</p>

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

CC BY-SA 4.0
2020-05-19T23:07:20.033Z
Looks super interesting, thanks a lot for the pointers, I'll investigate. Do you happen to know if the 3 processor scheduling problem, or more generally the k processor scheduling problem for any fixed k, is still in PTIME?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-05-20T01:27:07.123Z
@a3nm whether the 3 and k processor scheduling  problem is  in P is a major open problem. See some recent papers that provide a quasi-polynomial time approximation scheme which is significant progress after many decades. Here is a recent one by 
 Shi Li  which has pointers to other  work. https://arxiv.org/abs/2004.01231
Chandra Chekuri
CC BY-SA 4.0
2020-05-20T22:03:59.443Z
@ChandraChekuri many thanks for the pointer, I'll investigate! We'll also have to figure out whether the algorithm for 2 processor scheduling applies to our initial problem (intuitively, our problem is 2 processor scheduling except that for some comparability relations you can "cheat" and schedule the two jobs simultaneously if the first one is available and the second one is only blocked by the first one. Now I'm hoping this can make the problem NP-hard because otherwise there's little hope we can avoid the open problem... In any case many thanks to you and Gara for noticing this connection!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-05-19T19:56:40.367Z
2020-05-20T17:19:54.863Z
2020-05-20T17:19:54.863Z
Gara Pruesse
<p>OK, I'm coming back to this after some more thought based on the ideas of @GaraPruesse and @ChandraChekuri. I'm not 100% sure, because these arguments are a pain to formalize and visualize, but I think my problem of enumeration with special vertices coming in even groups (or in multiple-of-k groups) is in fact polynomially equivalent to the problem of two processor (or k processor) scheduling. So, if true, this answers my question pretty conclusively: the case of k=2 would be in PTIME by that algorithm, and the case of k>2 would be open. (An  interesting further question for my needs would be to study classes of directed graphs where the case of k>2 is known to be exactly solvable in PTIME, and see what this implies in our context, e.g., looking at <a href="https://doi.org/10.1137%2FS0097539790181889" rel="nofollow noreferrer">this paper</a>.)</p>

<p><strong>Forward reduction.</strong> It is clear that the problem of k-processor scheduling can be reduced in PTIME to my problem of enumerating in multiple-of-k groups: take the input DAG <span class="math-container">$G$</span>, make all vertices special, and replace every edge by two edges with a non-special vertex in the middle, yielding <span class="math-container">$G'$</span>. If there is a way to schedule <span class="math-container">$G$</span> with a k-processor schedule exactly, then we can schedule <span class="math-container">$G'$</span> according to my constraint, by doing the same, and eliminating the non-special vertices between each group. Conversely, any schedule of <span class="math-container">$G'$</span> must enumerate vertices in groups of <span class="math-container">$k$</span> that are incomparable (as all comparability relations have a non-special vertex in the middle), so it can be played on <span class="math-container">$G$</span>. The challenging direction is the reverse: showing that our problem actually reduces to scheduling in polynomial time (i.e., it is not harder).</p>

<p><strong>Backward reduction, step 1: removing comparability relations between non-special vertices.</strong> Given a DAG <span class="math-container">$G$</span> with special vertices, let's assume that the comparability relation has been transitively closed. Now let's look at the comparability relation between special vertices. I claim that we can simply forget about all comparability pairs between two non-special vertices, i.e., the graph <span class="math-container">$G_1$</span> where these pairs are removed has a topological sort grouping vertices in multiple-of-k groups iff <span class="math-container">$G$</span> did. One direction is obvious, and for the other direction, given a topological sort in <span class="math-container">$G_1$</span>, we should be able to enumerate the special vertices in <span class="math-container">$G$</span> in the same order, enumerating the non-special vertices greedily as soon as they are available. The key point is that whenever a non-special vertex <span class="math-container">$v$</span> is enumerated in <span class="math-container">$G_1$</span> then it has no unenumerated special predecessors in <span class="math-container">$G$</span>, and the same is true of all its unenumerated non-special predecessors in <span class="math-container">$G$</span>: so we can simply enumerate all the non-special predecessors of <span class="math-container">$v$</span>, including <span class="math-container">$v$</span>, in <span class="math-container">$G$</span>.</p>

<p><strong>Step 2: replacing non-special vertices by copies having only one predecessor and only one successor.</strong> Now we have a DAG <span class="math-container">$G_1$</span> on special vertices, with some additional non-special vertices that are only comparable to the special vertices. Let's take such a non-special vertex <span class="math-container">$v$</span> and look at its maximal special predecessors <span class="math-container">$p_1, ..., p_m$</span> and minimal special successors <span class="math-container">$s_1, ..., s_n$</span>. Let's argue that we can remove <span class="math-container">$v$</span> and replace it by <span class="math-container">$m \times n$</span> non-special copies <span class="math-container">$v_{i,j}$</span> with comparability relations <span class="math-container">$p_i &lt; v_{i,j}$</span> and <span class="math-container">$v_{i,j} &lt; s_j$</span>. In other words, we replace <span class="math-container">$v$</span> by a complete bipartite graph between the predecessors and successors with non-special vertices in the middle of every edge. Let <span class="math-container">$G_1'$</span> be the result, I argue that the transformation does not change the existence of a topological sort enumerating special vertices in multiple-of-k groups. One direction is clear: if you have a sort in <span class="math-container">$G_1$</span> then you can do the same in <span class="math-container">$G_1'$</span>, and when enumerating <span class="math-container">$v$</span> you instead enumerate all copies. But conversely, if you have a sort in <span class="math-container">$G_1'$</span>, then considering the first vertex in <span class="math-container">$s_1, ..., s_n$</span> that gets enumerated, say <span class="math-container">$s_j$</span>, we must have had a point where we enumerated the copies <span class="math-container">$v_{i,j}$</span> for all <span class="math-container">$i$</span>, and at that point all the <span class="math-container">$p_1, ..., p_m$</span> must have been enumerated, so in <span class="math-container">$G_1$</span> we can enumerate <span class="math-container">$v$</span> at that moment. So now we can iterate this argument to remove all non-special vertices having more than one successor or more than one predecessor, and get <span class="math-container">$G_2$</span> where all non-special vertices have exactly one predecessor and one successor, and no other comparability relations. (Of course the non-special vertices with no predecessor, or no successor, can simply be removed.)</p>

<p><strong>Step 3: doing a kind of transitive closure.</strong> Now we are getting very close to the scheduling problem, with "edges" that have a non-special vertex in the middle. Of course, "multi-edges", i.e., having multiple non-special vertices with the same predecessor and same successor, can be eliminated easily by keeping only one of the copies. But there is another problem: in <span class="math-container">$G_2$</span> we could still have comparability relations between special vertices that have no non-special vertices in the middle. (Or in other words, we have a scheduling problem where some comparability relations are not an obstacle to scheduling the vertices simultaneously.) So let's transitively close <span class="math-container">$G_2$</span> in the following sense: if there is a directed path of comparability relations going from a special vertex <span class="math-container">$u$</span> to a special vertex <span class="math-container">$v$</span> and that goes via some non-special vertex, then ensure that there is a non-special vertex having <span class="math-container">$u$</span> as predecessor and <span class="math-container">$v$</span> as successor. Call <span class="math-container">$G_3$</span> the result. This can be done in PTIME and obviously does not change the existence of topological sorts with multiple-of-k groups: if there is a suitable sort in <span class="math-container">$G_3$</span> then there is one in <span class="math-container">$G_2$</span>, and conversely given a sort in <span class="math-container">$G_2$</span>, every additional non-special vertex in <span class="math-container">$G_3$</span> can be enumerated at the moment where the witnessing non-special vertex on the witnessing path was itself enumerated.</p>

<p><strong>Step 4: removing comparability relations between special vertices.</strong> Now we are ready to finally reduce to the scheduling problem. Call <span class="math-container">$G_4$</span> the result of dropping from <span class="math-container">$G_3$</span> all comparability relations that are between special vertices directly. (Intuitively, we remove these "fake" comparability relations, and only keep comparability relations between special vertices that have a non-special vertex in the middle.) Clearly if there is a topological sort in <span class="math-container">$G_3$</span> with vertices coming in multiple-of-k groups, the same in true in <span class="math-container">$G_4$</span>. For the converse direction, consider a suitable sort in <span class="math-container">$G_4$</span>, and a moment where some vertex <span class="math-container">$v$</span> is enumerated which is not available in <span class="math-container">$G_3$</span>. This means that <span class="math-container">$v$</span> is blocked in <span class="math-container">$G_3$</span> by some special vertex <span class="math-container">$v'$</span> and we have a comparability relation <span class="math-container">$v' &lt; v$</span> in <span class="math-container">$G_3$</span> not reflected in <span class="math-container">$G_4$</span>. Take some <span class="math-container">$v'$</span> in <span class="math-container">$G_3$</span> which is minimal in that sense, i.e., an unenumerated ancestor of <span class="math-container">$v$</span> that only precedes <span class="math-container">$v$</span> via paths involving no non-special vertices. But now, observe that all successors of <span class="math-container">$v$</span> in <span class="math-container">$G_4$</span> must be successors of <span class="math-container">$v'$</span> in <span class="math-container">$G_4$</span>, and all predecessors of <span class="math-container">$v'$</span> in <span class="math-container">$G_4$</span> are predecessors of <span class="math-container">$v$</span> in <span class="math-container">$G_4$</span>. This is thanks to the closure done at the previous step. The second point guarantees that, if <span class="math-container">$v$</span> is available in <span class="math-container">$G_4$</span>, then using also the minimality of <span class="math-container">$v'$</span> in <span class="math-container">$G_3$</span>, we know that <span class="math-container">$v'$</span> can be enumerated in <span class="math-container">$G_3$</span> (it can only be blocked by predecessors in <span class="math-container">$G_3$</span> that are also predecessors in <span class="math-container">$G_4$</span>, thanks to minimality); and the first point guarantees that we lose nothing by enumerating <span class="math-container">$v'$</span> in the sort in <span class="math-container">$G_4$</span> instead of <span class="math-container">$v$</span>, as <span class="math-container">$v$</span> only helps make available vertices that are also blocked by <span class="math-container">$v'$</span>. So we can swap <span class="math-container">$v$</span> and <span class="math-container">$v'$</span> in the topological sort of <span class="math-container">$G_4$</span>. By repeating the argument, we get a topological sort in <span class="math-container">$G_4$</span> which is also a topological sort in <span class="math-container">$G_3$</span>, showing the equivalence.</p>

<p><strong>Step 5: conclusion.</strong> Now, <span class="math-container">$G_4$</span> consists of special vertices, and of "edges with non-special vertices in the middle", i.e., non-special vertices that have precisely one special predecessor and one special successor, and these are the only comparability relations. So this is exactly the setting of the k processor scheduling problem: finding a topological sort of <span class="math-container">$G_4$</span> with multiple-of-k groups exactly amounts to finding a scheduling with k processors of <span class="math-container">$G_4'$</span> where each "edge with a non-special vertex in the middle" is replaced by an edge. So we have completed the reduction to the scheduling problem.</p>

<p>Again, I'm not 100% sure that this tedious argument is correct. (Probably it would be wiser to present it in a "meet-in-the-middle" way by showing that some generalization of k processor scheduling, e.g., the variant with additional edges that imply order between elements but allow concurrent scheduling, is still polynomially equivalent.) But if it is correct, it solves our question in a really unexpected way. I'm really grateful to @GaraPruesse and @ChandraChekuri for noticing the connection and giving pointers.</p>

CC BY-SA 4.0
2020-06-11T13:13:28.243Z
2020-06-11T13:20:38.830Z
2020-06-11T13:20:38.830Z
Antoine Amarilli 'a3nm'
<p>Consider the following problem. The input is a <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow noreferrer">directed acyclic graph</a> (DAG) <span class="math-container">$G = (V, E)$</span>, and a subset <span class="math-container">$V' \subseteq V$</span> of vertices, which we call <em>special vertices</em>. The question is to determine whether <span class="math-container">$G$</span> has a <a href="https://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow noreferrer">topological sort</a> <span class="math-container">$v_1 &lt; \cdots &lt; v_n$</span> 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 <span class="math-container">$v_i, \ldots, v_{j-1}$</span> of <span class="math-container">$v_1, \ldots, v_n$</span> where all vertices are special, and which is maximal (either <span class="math-container">$i=1$</span> or <span class="math-container">$v_{i-1}$</span> is not special; and either <span class="math-container">$j = n-1$</span> or <span class="math-container">$v_j$</span> is not special), then we require that <span class="math-container">$j-i$</span> is even.</p>

<p><strong>Is this decision problem NP-hard, or is it in PTIME?</strong></p>

<p>Of course, a necessary condition is that there is an even number of special vertices. But this is not sufficient: the totally ordered graph <span class="math-container">$w_1 &lt; v_2 &lt; w_3$</span> with <span class="math-container">$w_1$</span> and <span class="math-container">$w_3$</span> 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 <span class="math-container">$w_1 &lt; v &lt; w_2$</span> and <span class="math-container">$w_3 &lt; w_4$</span> with the <span class="math-container">$w_i$</span> being special and <span class="math-container">$v$</span> non-special, then the topological sort <span class="math-container">$w_1 &lt; w_3 &lt; v &lt; w_2 &lt; w_4$</span> satisfies the condition, but if we want to start a topological sort by <span class="math-container">$w_3 &lt; w_4$</span> then we are "stuck".</p>

<p>[This relates to work on mine about <a href="https://arxiv.org/abs/1707.04310" rel="nofollow noreferrer">constrained topological sorting</a>. It is listed as an open problem <a href="https://paperman.name/prob/dag_page/index.html" rel="nofollow noreferrer">here</a> (search for "Open problem: Is the same true of the CTS problem?"). We have a PTIME algorithm (Proposition 4.6 of <a href="https://arxiv.org/abs/1707.04310" rel="nofollow noreferrer">the paper</a>) for the much easier problem where <span class="math-container">$G$</span> is a disjoint union of chains (total orders), which is a rather intuitive but not entirely trivial greedy algorithm.]</p>

<p><strong>Update (thanks <a href="https://cstheory.stackexchange.com/users/45122/louis">@Louis</a>):</strong> The problem presented here is related to another variant of topological sort, which seems unknown but pretty natural, which I'd call <strong>"two by two" or "pairwise" topological sorting</strong>. This is the problem where you are given a DAG <span class="math-container">$G = (V, E)$</span> with an even number of vertices, and you want to decide if there exists a topological sort <span class="math-container">$v_1 &lt; \cdots &lt; v_n$</span> 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 <span class="math-container">$0 \leq k &lt; (n/2)-1$</span>, the vertices <span class="math-container">$v_{2k+1}$</span> and <span class="math-container">$v_{2k+2}$</span> are incomparable. <strong>I do not know the complexity of this problem, either.</strong> 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.</p>

<p>I also don't know the complexity of the variant where we replace two by some other constant <span class="math-container">$k$</span>, i.e., my problem where special vertices must be taken in groups of multiples of <span class="math-container">$k$</span>, or the "<span class="math-container">$k$</span> by <span class="math-container">$k$</span>" topological sorting problem. Any insights about their complexity are also welcome.</p>

<cc.complexity-theory><graph-algorithms><np-hardness><topological-sorting>
Topological sorting of a DAG where special vertices have to come in even groups
Antoine Amarilli 'a3nm'
# Topological sorting of a DAG where special vertices have to come in even groups

(Asked by: username_0 on 2020-05-15)

Consider the following problem. The input is a [directed acyclic graph](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Topological_sorting) $v\_1 < \cdots < 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 < v\_2 < 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 < v < w\_2$ and $w\_3 < w\_4$ with the $w\_i$ being special and $v$ non-special, then the topological sort $w\_1 < w\_3 < v < w\_2 < w\_4$ satisfies the condition, but if we want to start a topological sort by $w\_3 < w\_4$ then we are "stuck".

[This relates to work on mine about [constrained topological sorting](https://arxiv.org/abs/1707.04310). It is listed as an open problem [here](https://paperman.name/prob/dag_page/index.html) (search for "Open problem: Is the same true of the CTS problem?"). We have a PTIME algorithm (Proposition 4.6 of [the paper](https://arxiv.org/abs/1707.04310)) 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](https://cstheory.stackexchange.com/users/45122/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 < \cdots < 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 < (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.

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness, topological-sorting

---

## 2 answers

### Answer by username_1 on 2020-05-19. Score: 4

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

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](https://dl.acm.org/doi/pdf/10.1145/322326.322335), [Gabow and Tarjan](https://www.sciencedirect.com/science/article/pii/0022000085900145)). Earlier work by [Coffman and Graham](https://link.springer.com/article/10.1007/BF00288685) 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.

> **Comments:**
> **username_0**: Looks super interesting, thanks a lot for the pointers, I'll investigate. Do you happen to know if the 3 processor scheduling problem, or more generally the k processor scheduling problem for any fixed k, is still in PTIME?  
> **username_2**: @a3nm whether the 3 and k processor scheduling  problem is  in P is a major open problem. See some recent papers that provide a quasi-polynomial time approximation scheme which is significant progress after many decades. Here is a recent one by   Shi Li  which has pointers to other  work. https://arxiv.org/abs/2004.01231  
> **username_0**: @ChandraChekuri many thanks for the pointer, I'll investigate! We'll also have to figure out whether the algorithm for 2 processor scheduling applies to our initial problem (intuitively, our problem is 2 processor scheduling except that for some comparability relations you can "cheat" and schedule the two jobs simultaneously if the first one is available and the second one is only blocked by the first one. Now I'm hoping this can make the problem NP-hard because otherwise there's little hope we can avoid the open problem... In any case many thanks to you and Gara for noticing this connection!  

---

### Answer by username_0 on 2020-06-11. Score: 1

OK, I'm coming back to this after some more thought based on the ideas of @GaraPruesse and @ChandraChekuri. I'm not 100% sure, because these arguments are a pain to formalize and visualize, but I think my problem of enumeration with special vertices coming in even groups (or in multiple-of-k groups) is in fact polynomially equivalent to the problem of two processor (or k processor) scheduling. So, if true, this answers my question pretty conclusively: the case of k=2 would be in PTIME by that algorithm, and the case of k>2 would be open. (An interesting further question for my needs would be to study classes of directed graphs where the case of k>2 is known to be exactly solvable in PTIME, and see what this implies in our context, e.g., looking at [this paper](https://doi.org/10.1137%2FS0097539790181889).)

**Forward reduction.** It is clear that the problem of k-processor scheduling can be reduced in PTIME to my problem of enumerating in multiple-of-k groups: take the input DAG $G$, make all vertices special, and replace every edge by two edges with a non-special vertex in the middle, yielding $G'$. If there is a way to schedule $G$ with a k-processor schedule exactly, then we can schedule $G'$ according to my constraint, by doing the same, and eliminating the non-special vertices between each group. Conversely, any schedule of $G'$ must enumerate vertices in groups of $k$ that are incomparable (as all comparability relations have a non-special vertex in the middle), so it can be played on $G$. The challenging direction is the reverse: showing that our problem actually reduces to scheduling in polynomial time (i.e., it is not harder).

**Backward reduction, step 1: removing comparability relations between non-special vertices.** Given a DAG $G$ with special vertices, let's assume that the comparability relation has been transitively closed. Now let's look at the comparability relation between special vertices. I claim that we can simply forget about all comparability pairs between two non-special vertices, i.e., the graph $G\_1$ where these pairs are removed has a topological sort grouping vertices in multiple-of-k groups iff $G$ did. One direction is obvious, and for the other direction, given a topological sort in $G\_1$, we should be able to enumerate the special vertices in $G$ in the same order, enumerating the non-special vertices greedily as soon as they are available. The key point is that whenever a non-special vertex $v$ is enumerated in $G\_1$ then it has no unenumerated special predecessors in $G$, and the same is true of all its unenumerated non-special predecessors in $G$: so we can simply enumerate all the non-special predecessors of $v$, including $v$, in $G$.

**Step 2: replacing non-special vertices by copies having only one predecessor and only one successor.** Now we have a DAG $G\_1$ on special vertices, with some additional non-special vertices that are only comparable to the special vertices. Let's take such a non-special vertex $v$ and look at its maximal special predecessors $p\_1, ..., p\_m$ and minimal special successors $s\_1, ..., s\_n$. Let's argue that we can remove $v$ and replace it by $m \times n$ non-special copies $v\_{i,j}$ with comparability relations $p\_i < v\_{i,j}$ and $v\_{i,j} < s\_j$. In other words, we replace $v$ by a complete bipartite graph between the predecessors and successors with non-special vertices in the middle of every edge. Let $G\_1'$ be the result, I argue that the transformation does not change the existence of a topological sort enumerating special vertices in multiple-of-k groups. One direction is clear: if you have a sort in $G\_1$ then you can do the same in $G\_1'$, and when enumerating $v$ you instead enumerate all copies. But conversely, if you have a sort in $G\_1'$, then considering the first vertex in $s\_1, ..., s\_n$ that gets enumerated, say $s\_j$, we must have had a point where we enumerated the copies $v\_{i,j}$ for all $i$, and at that point all the $p\_1, ..., p\_m$ must have been enumerated, so in $G\_1$ we can enumerate $v$ at that moment. So now we can iterate this argument to remove all non-special vertices having more than one successor or more than one predecessor, and get $G\_2$ where all non-special vertices have exactly one predecessor and one successor, and no other comparability relations. (Of course the non-special vertices with no predecessor, or no successor, can simply be removed.)

**Step 3: doing a kind of transitive closure.** Now we are getting very close to the scheduling problem, with "edges" that have a non-special vertex in the middle. Of course, "multi-edges", i.e., having multiple non-special vertices with the same predecessor and same successor, can be eliminated easily by keeping only one of the copies. But there is another problem: in $G\_2$ we could still have comparability relations between special vertices that have no non-special vertices in the middle. (Or in other words, we have a scheduling problem where some comparability relations are not an obstacle to scheduling the vertices simultaneously.) So let's transitively close $G\_2$ in the following sense: if there is a directed path of comparability relations going from a special vertex $u$ to a special vertex $v$ and that goes via some non-special vertex, then ensure that there is a non-special vertex having $u$ as predecessor and $v$ as successor. Call $G\_3$ the result. This can be done in PTIME and obviously does not change the existence of topological sorts with multiple-of-k groups: if there is a suitable sort in $G\_3$ then there is one in $G\_2$, and conversely given a sort in $G\_2$, every additional non-special vertex in $G\_3$ can be enumerated at the moment where the witnessing non-special vertex on the witnessing path was itself enumerated.

**Step 4: removing comparability relations between special vertices.** Now we are ready to finally reduce to the scheduling problem. Call $G\_4$ the result of dropping from $G\_3$ all comparability relations that are between special vertices directly. (Intuitively, we remove these "fake" comparability relations, and only keep comparability relations between special vertices that have a non-special vertex in the middle.) Clearly if there is a topological sort in $G\_3$ with vertices coming in multiple-of-k groups, the same in true in $G\_4$. For the converse direction, consider a suitable sort in $G\_4$, and a moment where some vertex $v$ is enumerated which is not available in $G\_3$. This means that $v$ is blocked in $G\_3$ by some special vertex $v'$ and we have a comparability relation $v' < v$ in $G\_3$ not reflected in $G\_4$. Take some $v'$ in $G\_3$ which is minimal in that sense, i.e., an unenumerated ancestor of $v$ that only precedes $v$ via paths involving no non-special vertices. But now, observe that all successors of $v$ in $G\_4$ must be successors of $v'$ in $G\_4$, and all predecessors of $v'$ in $G\_4$ are predecessors of $v$ in $G\_4$. This is thanks to the closure done at the previous step. The second point guarantees that, if $v$ is available in $G\_4$, then using also the minimality of $v'$ in $G\_3$, we know that $v'$ can be enumerated in $G\_3$ (it can only be blocked by predecessors in $G\_3$ that are also predecessors in $G\_4$, thanks to minimality); and the first point guarantees that we lose nothing by enumerating $v'$ in the sort in $G\_4$ instead of $v$, as $v$ only helps make available vertices that are also blocked by $v'$. So we can swap $v$ and $v'$ in the topological sort of $G\_4$. By repeating the argument, we get a topological sort in $G\_4$ which is also a topological sort in $G\_3$, showing the equivalence.

**Step 5: conclusion.** Now, $G\_4$ consists of special vertices, and of "edges with non-special vertices in the middle", i.e., non-special vertices that have precisely one special predecessor and one special successor, and these are the only comparability relations. So this is exactly the setting of the k processor scheduling problem: finding a topological sort of $G\_4$ with multiple-of-k groups exactly amounts to finding a scheduling with k processors of $G\_4'$ where each "edge with a non-special vertex in the middle" is replaced by an edge. So we have completed the reduction to the scheduling problem.

Again, I'm not 100% sure that this tedious argument is correct. (Probably it would be wiser to present it in a "meet-in-the-middle" way by showing that some generalization of k processor scheduling, e.g., the variant with additional edges that imply order between elements but allow concurrent scheduling, is still polynomially equivalent.) But if it is correct, it solves our question in a really unexpected way. I'm really grateful to @GaraPruesse and @ChandraChekuri for noticing the connection and giving pointers.


---

