Topological sorting of a DAG where special vertices have to come in even groups

Question

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

Answer 1

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

Answer 2

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

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.