2026-07-21T14:10:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23095 2025-10-02T12:37:21Z ddc:004 open_access

Representing Paths in Digraphs Dondi, Riccardo Popa, Alexandru Graph String Matching Computational Complexity Parameterized Complexity Algorithms In this contribution we consider two combinatorial problems related to graph string matching, motivated by recent approaches in computational genomics. Given a DAG where each node is labeled by a symbol, the problems aim to find a path in the DAG whose nodes contain all (or the maximum number of) symbols of the alphabet. We introduce a decision problem, Σ-Representing Path, that asks whether there exists a path that contains all the symbols of the alphabet, and an optimization problem, called Maximum Representing Path, that asks for a path that contains the maximum number of symbols. We analyze the complexity of the problems, showing the NP-completeness of {Σ-Representing Path} when each symbol labels at most three nodes in the DAG, and showing the APX-hardness of Maximum Representing Path when each symbol labels at most two nodes in the DAG. We complement the first result by giving a polynomial-time algorithm for Σ-Representing Path when each symbol labels at most two nodes in the DAG. Then we investigate the parameterized complexity of the two problems when the DAG has a limited distance from a set of disjoint paths and we show that both problems are W[1]-hard for this parameter. We consider the approximation of Maximum Representing Path, giving an approximation algorithm of factor √OPT, where OPT is the value of an optimal solution of the problem. We also show that Maximum Representing Path cannot be approximated within factor e/(e-1) - α, for any constant α > 0, unless NP ⊆ DTIME(|V|^{O(log log |V|)}) (V is the set of nodes of the DAG). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Riccardo Dondi and Alexandru Popa 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.1 urn:nbn:de:0030-drops-230954 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.1 eng https://creativecommons.org/licenses/by/4.0/legalcode