Representing Paths in Digraphs - Alex Popa (3.6.2025)

v utorok 3.6.2025 o 11:00 hod. v posluchárni VIII

---

Prednášajúci: Alex Popa (Professor, Faculty of Mathematics and Computer Science, University of Bucharest, Romania)

Názov: Representing Paths in Digraphs

Termín: 3.6.2025, 11:00 hod., poslucháreň VIII

Abstrakt:
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 sqrt{OPT} , where OPT is the value of an optimal solution of the problem. We also show a hardness of approximation result for the Maximum Representing Path problem.

---