Computing SEQ-IC-LCS of Labeled Graphs

Yuki Yonemoto; Yuto Nakashima; Shunsuke Inenaga

paper

Computing SEQ-IC-LCS of Labeled Graphs

arXiv:2307.07676

Abstract

We consider labeled directed graphs where each vertex is labeled with a non-empty string. Such labeled graphs are also known as non-linear texts in the literature. In this paper, we introduce a new problem of comparing two given labeled graphs, called the SEQ-IC-LCS problem on labeled graphs. The goal of SEQ-IC-LCS is to compute the the length of the longest common subsequence (LCS) $Z$ of two target labeled graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ that includes some string in the constraint labeled graph $G_{3} = (V_{3}, E_{3})$ as its subsequence. Firstly, we consider the case where $G_{1}$ , $G_{2}$ and $G_{3}$ are all acyclic, and present algorithms for computing their SEQ-IC-LCS in $O (∣ E_{1} ∣∣ E_{2} ∣∣ E_{3} ∣)$ time and $O (∣ V_{1} ∣∣ V_{2} ∣∣ V_{3} ∣)$ space. Secondly, we consider the case where $G_{1}$ and $G_{2}$ can be cyclic and $G_{3}$ is acyclic, and present algorithms for computing their SEQ-IC-LCS in $O (∣ E_{1} ∣∣ E_{2} ∣∣ E_{3} ∣ + ∣ V_{1} ∣∣ V_{2} ∣∣ V_{3} ∣ lo g ∣Σ∣)$ time and $O (∣ V_{1} ∣∣ V_{2} ∣∣ V_{3} ∣)$ space, where $Σ$ is the alphabet.

Accepted for PSC 2023