2026-07-25T00:32:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9119 2024-03-06T10:43:24Z ddc:004 open_access

Topological Sorting with Regular Constraints Amarilli, Antoine Paperman, Charles Topological sorting shuffle problem regular language 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli and Charles Paperman 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.115 urn:nbn:de:0030-drops-91193 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.115 eng https://creativecommons.org/licenses/by/3.0/legalcode