  We introduce the constrained topological sorting problem (CTS): given a
regular language K and a directed acyclic graph G with labeled vertices,
determine if G has a topological sort that forms a word in K. This natural
problem applies to several settings, e.g., scheduling with costs or verifying
concurrent programs. We consider the problem CTS[K] where the target language K
is fixed, and study its complexity depending on K. We show that CTS[K] is
tractable when K falls in several language families, e.g., unions of monomials,
which can be used for pattern matching. However, we show that CTS[K] is NP-hard
for K = (ab)^* and introduce a shuffle reduction technique to show hardness for
more languages. We also study the special case of the constrained shuffle
problem (CSh), where the input graph is a disjoint union of strings, and show
that CSh[K] is additionally tractable when K is a group language or a union of
district group monomials. We conjecture that a dichotomy should hold on the
complexity of CTS[K] or CSh[K] depending on K, and substantiate this by proving
a coarser dichotomy under a different problem phrasing which ensures that
tractable languages are closed under common operators.
