# Robustness and Usefulness in AI Explanation Methods

Erick Galinkin<EMAIL_ADDRESS>
###### Abstract

Explainability in machine learning has become incredibly important as machine
learning-powered systems become ubiquitous and both regulation and public
sentiment begin to demand an understanding of how these systems make
decisions. As a result, a number of explanation methods have begun to receive
widespread adoption. This work summarizes, compares, and contrasts three
popular explanation methods: LIME, SmoothGrad, and SHAP. We evaluate these
methods with respect to: robustness, in the sense of sample complexity and
stability; understandability, in the sense that provided explanations are
consistent with user expectations; and usability, in the sense that the
explanations allow for the model to be modified based on the output. This work
concludes that current explanation methods are insufficient; that putting
faith in and adopting these methods may actually be worse than simply not
using them.

##  1 Introduction

Machine learning has become a ubiquitous part of life for us. These algorithms
aim to predict, either via classification or regression, information about a
particular input. The trouble comes in that, as Doshi-Velez and Kim [11] put
it, any single metric is necessarily an incomplete description of the real
world. Given the influence these systems have in our lives, people seek to
understand precisely why a model made a particular decision. To this end,
research efforts around interpreting and explaining the predictions of models
have sprung up and have fallen into two overarching families: intrinsically
interpretable models and post-hoc explanation methods. The results of the
methods are typically quite similar, but while interpretable models aim to be
sufficiently simple that their predictions are easily reasoned about, post-hoc
explanation methods take a trained model that may be extremely complex and
construct explanations from properties of the model. This work focuses
primarily on popular explanation methods applied to trained models rather than
inherent interpretability.

Explanation methods are of particular concern because of the way that they
influence human behavior. Despite the challenges in defining terms like
interpretability in concrete terms [21], explanations are important for
improving trust and can also improve the speed at which human auditors perform
their work [30]. For some users, the mere presence of an explanation increases
that user’s trust in a model, even when the explanations are incorrect [6]. In
other cases, even data scientists who build models tend to rely too heavily on
these interpretability tools [19], demonstrating a failure to use the tool’s
appropriately. These challenges, and others, are detailed in Section 4.

##  2 Background

This work reflects on a number of explanation methods – namely LIME,
SmoothGrad, and SHAP. These methods have begun to see adoption in industry
[13] and are popular for their ease of implementation. To facilitate the
discussion in Section 3, we introduce the motivation and implementation of
these methods below.

###  2.1 Local Interpretable Model-Agnostic Explanations (LIME)

Local Interpretable Model-Agnostic Explanations (LIME) [29] is an explanation
method that aims to explain the predictions of any classifier, irrespective of
complexity or linearity. This is accomplished through an interpretable
representation that locally approximates the overall classifier. The
interpretable representation is derived from a class of potentially
interpretable models – limited in part by the complexity of the model, denoted
$\Omega(g)$. In this case, examples of complexity include tree depth or the
number of non-zero weights of a linear model.

In addition to minimizing complexity, LIME also seeks a model that minimizes
the locality-aware loss, or so-called fidelity function $\mathcal{L}$ for an
input $x$. $\mathcal{L}$ is a function that measures how good an interpretable
model $g$ is at approximating a classifier $f$ in a neighborhood $\pi_{x}$ of
$x$. Formally, given an input $x$, a classifier $f$, and a class of
potentially interpretable models $G$, the explanation produced by LIME is
obtained by:

$\xi(x)=\operatorname*{\arg\\!\min}_{g\in
G}\mathcal{L}(f,g,\pi_{x})+\Omega(g)$ (1)

LIME then perturbs and samples the space around each instance of interest,
$x$, constructing representations and labels for those representations. The
new samples are weighted by their distance from $x$. These representations and
labels are then used to select and train the model satisfying Equation 1. This
means that the explanation model used for a particular instance $x$ is the
model $g$ that is closest to the classifier $f$ with minimal model complexity
$\Omega(g)$. In practice, $\Omega(g)$ is a hyperparameter [25]. For example,
if we want to use linear regression models as our locally interpretable model,
we select the number of parameters $K$ to be used in the model.

###  2.2 SmoothGrad

SmoothGrad [36] is a gradient-based explanation method that builds on work
like Saliency Maps [34] and GradCAM [31]. Crucially, SmoothGrad is not, on its
own, an explanation method, but rather an extension of any existing gradient-
based explanation method. When we refer to SmoothGrad on its own, we refer to
implementations like iNNvestigate [3] where it complements so-called “vanilla”
gradient methods.

These gradient-based methods take advantage of the backpropogation algorithm
used in training neural networks, particularly convolutional neural networks
used in image classification. SmoothGrad was developed in response to two
issues in gradient-based explanation methods:

  1. 1.

The issue of one feature with a strong global effect but a small local
derivative “saturating” the sensitivity map

  2. 2.

Noisy gradients as a result of the class sensitivity function’s derivative
fluctuating locally

SmoothGrad aims to solve these problems by generating multiple versions of an
image of interest $x$ by adding noise to it. Pixel attribution maps – heatmaps
like those generated in Selvaraju et al. [31] – are then created for all of
these images, and those maps are then averaged together. The idea here is that
adding some noise sampled from a Gaussian distribution averaged over multiple
maps can smooth the local gradient fluctuations and lead to better maps.

###  2.3 Shapley Additive Explanations (SHAP)

Shapley Additive Explanations (SHAP) [23] is an explainability method that
leverages a game theoretic approach to understand model predictions. The work
was motivated as an attempt to unify six different methods for interpreting
model predictions, including LIME. SHAP works by assigning an importance value
to each feature for each prediction using Shapley value estimation methods.
The Shapley value [32] is a construct from cooperative named for Lloyd Shapley
that seeks to distribute the total gain in utility across a coalition of $n$
players according to each player’s marginal contribution. Formally, given a
characteristic function $v:2^{n}\rightarrow\mathbb{R},v(\emptyset)=0$ that
maps a a set of players to a value for that coalition, the set of all players
$N$ and a coalition of players $S\subseteq N$, a fair distribution for each
player $i$ in a coalition $S$ is given by:

$\phi_{i}(v)\sum_{S\subseteq
N\setminus\\{i\\}}\frac{\left|S\right|!(\left|N\right|-\left|S\right|-1)!}{\left|N\right|!}\left(v(S\cup\\{i\\})-v(S)\right)$
(2)

Theorem 1 of Lundberg and Lee [23] shows that only one possible explanation
model for the properties of local accuracy, missingness, and consistency holds
for additive feature attribution methods – explanation models that are linear
functions of binary variables – the Shapley value. Despite the fact that
exactly computing Shapley values is NP-Hard, the paper develops model-agnostic
approximations by assuming feature independence and model linearity. The paper
describes two classes of approximations: model-agnostic approximations and
model-specific approximations. The model-agnostic approximation introduced in
this initial work is called Kernel SHAP, which leverages linear LIME with
Shapley values. The model-specific approximations in the initial paper handle
linear models and deep neural networks using techniques from DeepLIFT [33].

The initial model was extended to provide visual explanations in later work
[24]. A further extension of SHAP [22] tackled the problems associated with
model-specific approximations of nonlinear, tree-based models. Tree SHAP, as
the author calls it, leverages feature perturbations to locally estimate the
interaction index, a game theoretic concept that follows from generalization
of the Shapley value properties.

##  3 Comparison of Explainability Methods

The three explainability methods above are all post-hoc methods that give a
view into machine learning black boxes. As discussed in Section 1, there is
growing interest in leveraging explainability and interpretability methods in
practice. This means that is is prudent to understand the strengths and
shortcomings of each method, and leverage the right one for our task. Table 1
summarizes some of the commonalities and differences between the methods,
which we detail in this section.

| Methodology | Local Explanation | Visualizable | Model Agnostic
---|---|---|---|---
LIME | Perturbation | ✓ | X | ✓
SmoothGrad | Gradient | ✓ | ✓ | X
SHAP | Perturbation | ✓ | ✓ | ✓
Table 1: Summary of LIME, SmoothGrad, and SHAP

###  3.1 Methodology

The three methods we consider fall under two different methodologies –
perturbation and gradient. Perturbation methods add some noise to inputs and
sample the space of perturbed inputs to assess the effect of small changes in
the space. Gradient-based methods instead use the gradients computed for given
inputs to explain model predictions.

Agarwal et al. [1] consider a variant of LIME for continuous data called
C-LIME and compare it directly to SmoothGrad. Interestingly, though ado much
has been made of the differences between perturbation and gradient-based
explanations, Agarwal et al. demonstrate that given the same Gaussian
distribution for perturbations and gradient computation, C-LIME and SmoothGrad
yield the same explanation in expectation. This suggests that the methodology
of the explanation is, on average, not meaningful to distinguish methods.

###  3.2 Local Explanation

We define local explainability as the ability to interrogate and explain
particular examples from the data. All three of the methods we consider here
offer local explanations for single predictions. This is a property that is
often desirable for legal and regulatory reasons, since it is often individual
predictions that lead to negative outcomes for individuals.

###  3.3 Visualizable

Visualizations are valuable tools for communicating data concisely in ways
that humans quickly and easily understand [40]. Consequently, having
explanations methods that lend themselves to visualizations can improve
understanding and interpretation. SmoothGrad can be used with any number of
gradient-based methods, but its use with the so-called “vanilla” gradient as
mentioned in Section 2.2 lends itself to the creation of heat maps.

SHAP, though it does not produce heat maps on images, has a Python package
111https://github.com/slundberg/shap that generates force plots which show how
each feature contributes to the model output. This method is used for
individual predictions but can also be used across entire datasets to
understand how the model treats the entirety of the dataset. In cases where we
want to understand the influence of a single feature, SHAP offers a way to
visualize the impact of that single feature across the dataset.

LIME, on the other hand, does not lend itself to a natural visualization. The
relatively simple nature of the LIME model means that variable importance
measures or partial dependence plots can be used to visualize attributes of
the more interpretable model, but these visualizations are less direct than
those produced by SmoothGrad or SHAP. Specifically, the visualization would be
informative about the surrogate model around the point of interest, and would
not give a view into how the larger model made the prediction relative to the
input in question.

###  3.4 Model Agnostic

Model agnostic methods are able to be used across a variety of model types. By
the No Free Lunch Theorem [41], we know that there is no single model that is
optimal for all tasks. This means that in practice, different models will be
used for different tasks and those models may require explanation in different
ways. Moreover, the way that data is input to the model can vary wildly –
images and video data structures often look quite different from text, and all
of these require different handling and processing methods from tabular data.
Model agnostic explanation methods aim to handle any of these input methods.

LIME specifically aims to be model-agnostic and achieves this by uncovering
locally-interpretable models. SHAP, building on the foundation of LIME, also
inherits this property. Though some specifics between e.g KernelSHAP [23] and
TreeExplainer [22] differ, the core of the methods remain the same. This means
that the skills associated with interpreting e.g. Shapley values are
transferrable across models.

SmoothGrad is not model agnostic and is only usable within differentiable
models. In fact, SmoothGrad is specifically useful in the case of
convolutional neural networks used for computer vision applications. This
makes it a powerful tool for identifying where in an image the model is
“paying attention”, but limits the usefulness of the method in general.

##  4 Weaknesses of Explainability Methods

Model trust is a critically important concept, gaining the attention of many,
including the National Institute of Standards and Technology [38] and the
parliament of the European Union [8]. This concept of trust, however, builds
on a shaky foundation. In particular, nearly all legislation proposed to date
includes a requirement for model interpretability. Lipton [21] offers a
stunning rebuke of the term itself, as the term has no agreed upon meaning. In
essence, the question becomes not whether a model is interpretable or not, but
rather to whom and under what circumstances model predictions can be
understood.

###  4.1 Human Factors in Explanations

One critique leveled at fairness in machine learning [12] is the notion that
one must conceive of an “ideal world” against which the current world is
compared. This can lead to unexpected negative outcomes for certain groups and
notions of fairness that leave everyone worse off: for example, a perfectly
fair judge who always denies bail and parole. The weaknesses of metrizable
fairness then promotes the desire for explanations – _why_ was bail denied?

A bevy of work has shown that although explainability methods have been widely
promoted, the explanations provided by the likes of LIME, SmoothGrad, and SHAP
can also range from being useless to outright harmful. Kaur et al. [19] show
that data scientists tend to misuse and over-rely on explanations from tools
like SHAP. Moreover, decision-makers often defer to algorithmic decision
support systems [15] and struggle to use the algorithms effectively – often
underperforming compared to both humans who are not assisted and the
algorithms themselves [20]. Model-agnostic methods are not alone here, as
Grad-CAM [31] has been shown to perform quite poorly on tasks it was
specifically designed to excel at [27] under benchmark conditions that are not
sufficiently realistic.

Explainability often uses healthcare for piloting its methods, likely due to
the superhuman performance of machine learning methods on a variety of medical
tasks [7, 26, 18]. SHAP in particular has been used in healthcare contexts
[24] and has been touted as a machine learning explainability method with
promise to improve healthcare worker trust in algorithms. This is very likely
to be true, as even when users are presented explanations are wrong [6] or
completely random [37], they tend to believe that the algorithm is correct.
Indeed, in the healthcare imaging context [14], localizing a region of an
image does not inform a human exactly _what_ in that region the model
considered useful. Combining these two phenomena – a lack of clarity in the
explanation paired with human deference to decision support algorithms – is
ultimately putting a human in the loop purely for decoration in the best case.

###  4.2 Robustness of Explainers

Beyond the human factors, the theoretical properties of explanation methods
leaves much to be desired. Agarwal et al. [1] investigate robustness for
C-LIME and SmoothGrad in certain settings, but find that the robustness is
sensitive to variance in the data. Robustness is a particularly valuable
attribute for explanations, as humans expect the important factors for data
that are “near” each other to be similar. Despite the equivalence of
perturbation and gradient-based methods in expectation, perturbation-based
methods are empirically worse [4] at providing consistent explanations given
small modifications to the input. Moreover, since there are so many models and
explanation methods that achieve comparable performance, this phenomenon may
lead to selecting models on the basis of how pleasing the explanations are
[16] without regard for the consistency of those explanations. Rahnama and
Boström [28] also find that LIME is not robust to changes in the distribution
of the data – a common occurrence in production applications of machine
learning.

This lack of robustness also allows for explainers to be “tricked” [35] by
models that aim to offer pleasing explanations, even when those explanations
do not provide visibility into the model itself. In image classification,
similarly, so-called “adversarial examples” [39] – inputs with specially-
crafted perturbations that are imperceptible to humans – can be crafted to
arbitrarily change saliency maps [10, 17]. As a result of this, a model
designer who is for whatever reason disinterested in removing bias from their
model is able to provide explanations with whatever properties they wish – a
property that Aivodji et al. [2] have termed “fairwashing”.

Model explanations are, of course, also impacted by human behavior that is
used as input. In recent work, Arora et al. [5] ask participants to edit hotel
reviews in such a way that a human reader can still derive whether a review is
still positive, negative, or mixed, while model confidence for the predicted
class is minimized. The study finds that for BERT [9], a transformer model
widely used in natural language processing, local explanations via LIME and
Integrated Gradients offer no additional ability for participants to reduce
the confidence of the model, while a linear model trained only on the
predictions of the BERT model offered participants significantly more ability
to change the label associated with the sample. Ultimately, this demonstrates
that the relative utility of the local explanations is lower than simply using
feature coefficients from a linear model that approximates the global model.

##  5 Conclusion

Post-hoc explanation methods offer significant opportunity to improve the
usability and human comprehensibility of machine learning methods. However,
current popular methods face a variety of problems from both a theoretical and
sociotechnical perspective. Though these problems may not be unsolvable or
inherent, further investigation is needed on how to increase the robustness
and usefulness of explanations. Given the concomitant phenomena of human
deference to decision support systems, human willingness to accept incorrect
explanations, a lack of robustness for explanations, and a lack of theoretical
guarantees for extant explanation methods, the idea of a “human-in-the-loop”
serves as nothing more than a security blanket. In order to deal with model
interpretability and explainability, more foundational work needs to be done
to formalize problems in interpretability and consider ideas around causality
and contestability. Counterfactual explanations offer a potential path
forward, though extant counterfactual generation methods have their own
weaknesses and biases.

## References

  * [1] Agarwal, S., Jabbari, S., Agarwal, C., Upadhyay, S., Wu, S., and Lakkaraju, H. Towards the unification and robustness of perturbation and gradient based explanations.  In International Conference on Machine Learning (2021), PMLR, pp. 110–119.
  * [2] Aïvodji, U., Arai, H., Fortineau, O., Gambs, S., Hara, S., and Tapp, A. Fairwashing: the risk of rationalization.  In International Conference on Machine Learning (2019), PMLR, pp. 161–170.
  * [3] Alber, M., Lapuschkin, S., Seegerer, P., Hägele, M., Schütt, K. T., Montavon, G., Samek, W., Müller, K.-R., Dähne, S., and Kindermans, P.-J. innvestigate neural networks!  Journal of Machine Learning Research 20, 93 (2019), 1–8.
  * [4] Alvarez-Melis, D., and Jaakkola, T. S. On the robustness of interpretability methods.  ICML 2018 Workshop on Human Interpretability in Machine Learning (2018).
  * [5] Arora, S., Pruthi, D., Sadeh, N., Cohen, W. W., Lipton, Z. C., and Neubig, G. Explain, edit, and understand: Rethinking user study design for evaluating model explanations.  In 36th AAAI Conference on Artificial Intelligence (2022).
  * [6] Bansal, G., Wu, T., Zhou, J., Fok, R., Nushi, B., Kamar, E., Ribeiro, M. T., and Weld, D. Does the whole exceed its parts? the effect of ai explanations on complementary team performance.  In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems (2021), pp. 1–16.
  * [7] Choudhury, A., Asan, O., et al. Role of artificial intelligence in patient safety outcomes: systematic literature review.  JMIR medical informatics 8, 7 (2020), e18599.
  * [8] Commission, E., et al. Proposal for a regulation of the european parliament and of the council laying down harmonised rules on artificial intelligence (artificial intelligence act) and amending certain union legislative acts.  COM (2021) 206 (2021).
  * [9] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805 (2018).
  * [10] Dombrowski, A.-K., Alber, M., Anders, C., Ackermann, M., Müller, K.-R., and Kessel, P. Explanations can be manipulated and geometry is to blame.  Advances in Neural Information Processing Systems 32 (2019).
  * [11] Doshi-Velez, F., and Kim, B. Towards a rigorous science of interpretable machine learning.  arXiv (2017).
  * [12] Fazelpour, S., and Lipton, Z. C. Algorithmic fairness from a non-ideal perspective.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (2020), pp. 57–63.
  * [13] Gade, K., Geyik, S. C., Kenthapadi, K., Mithal, V., and Taly, A. Explainable ai in industry.  In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining (2019), pp. 3203–3204.
  * [14] Ghassemi, M., Oakden-Rayner, L., and Beam, A. L. The false hope of current approaches to explainable artificial intelligence in health care.  The Lancet Digital Health 3, 11 (2021), e745–e750.
  * [15] Green, B., and Chen, Y. The principles and limits of algorithm-in-the-loop decision making.  Proceedings of the ACM on Human-Computer Interaction 3, CSCW (2019), 1–24.
  * [16] Hancox-Li, L. Robustness in machine learning explanations: does it matter?  In Proceedings of the 2020 conference on fairness, accountability, and transparency (2020), pp. 640–647.
  * [17] Heo, J., Joo, S., and Moon, T. Fooling neural network interpretations via adversarial model manipulation.  Advances in Neural Information Processing Systems 32 (2019).
  * [18] Hosny, A., Parmar, C., Quackenbush, J., Schwartz, L. H., and Aerts, H. J. Artificial intelligence in radiology.  Nature Reviews Cancer 18, 8 (2018), 500–510.
  * [19] Kaur, H., Nori, H., Jenkins, S., Caruana, R., Wallach, H., and Wortman Vaughan, J. Interpreting interpretability: understanding data scientists’ use of interpretability tools for machine learning.  In Proceedings of the 2020 CHI conference on human factors in computing systems (2020), pp. 1–14.
  * [20] Lai, V., and Tan, C. On human predictions with explanations and predictions of machine learning models: A case study on deception detection.  In Proceedings of the conference on fairness, accountability, and transparency (2019), pp. 29–38.
  * [21] Lipton, Z. C. The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery.  Queue 16, 3 (2018), 31–57.
  * [22] Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee, S.-I. From local explanations to global understanding with explainable ai for trees.  Nature Machine Intelligence 2, 1 (2020), 2522–5839.
  * [23] Lundberg, S. M., and Lee, S.-I. A unified approach to interpreting model predictions.  In Proceedings of the 31st international conference on neural information processing systems (2017), pp. 4768–4777.
  * [24] Lundberg, S. M., Nair, B., Vavilala, M. S., Horibe, M., Eisses, M. J., Adams, T., Liston, D. E., Low, D. K.-W., Newman, S.-F., Kim, J., et al. Explainable machine-learning predictions for the prevention of hypoxaemia during surgery.  Nature Biomedical Engineering 2, 10 (2018), 749.
  * [25] Molnar, C. Interpretable machine learning.  Lulu. com, 2020.
  * [26] Oren, O., Gersh, B. J., and Bhatt, D. L. Artificial intelligence in medical imaging: switching from radiographic pathological data to clinically meaningful endpoints.  The Lancet Digital Health 2, 9 (2020), e486–e488.
  * [27] Prakash, E. I., Shrikumar, A., and Kundaje, A. Towards more realistic simulated datasets for benchmarking deep learning models in regulatory genomics.  In Machine Learning in Computational Biology (2022), PMLR, pp. 58–77.
  * [28] Rahnama, A. H. A., and Boström, H. A study of data and label shift in the lime framework.  2019 NeurIPS Workshop on Human-Centric Machine Learning (2019).
  * [29] Ribeiro, M. T., Singh, S., and Guestrin, C. ” why should i trust you?” explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (2016), pp. 1135–1144.
  * [30] Schmidt, P., and Biessmann, F. Quantifying interpretability and trust in machine learning systems.  AAAI-19 Workshop on Network Interpretability for Deep learning (2019).
  * [31] Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra, D. Grad-cam: Visual explanations from deep networks via gradient-based localization.  In Proceedings of the IEEE international conference on computer vision (2017), pp. 618–626.
  * [32] Shapley, L. Quota solutions op n-person games1.  Edited by Emil Artin and Marston Morse (1953), 343.
  * [33] Shrikumar, A., Greenside, P., and Kundaje, A. Learning important features through propagating activation differences.  In Proceedings of the 34th International Conference on Machine Learning (06–11 Aug 2017), D. Precup and Y. W. Teh, Eds., vol. 70 of Proceedings of Machine Learning Research, PMLR, pp. 3145–3153.
  * [34] Simonyan, K., Vedaldi, A., and Zisserman, A. Deep inside convolutional networks: Visualising image classification models and saliency maps.  arXiv preprint arXiv:1312.6034 (2013).
  * [35] Slack, D., Hilgard, S., Jia, E., Singh, S., and Lakkaraju, H. Fooling lime and shap: Adversarial attacks on post hoc explanation methods.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (2020), pp. 180–186.
  * [36] Smilkov, D., Thorat, N., Kim, B., Viégas, F., and Wattenberg, M. Smoothgrad: removing noise by adding noise.  International Conference on Machine Learning Workshop on Visualization for Deep Learning (2017).
  * [37] Springer, A., Hollis, V., and Whittaker, S. Dice in the black box: User experiences with an inscrutable algorithm.  In 2017 AAAI Spring Symposium Series (2017).
  * [38] Stanton, B., and Jensen, T. Trust and artificial intelligence, 2021-03-02 05:03:00 2021.
  * [39] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199 (2013).
  * [40] Tufte, E. R., McKay, S. R., Christian, W., and Matey, J. R. Visual explanations: Images and quantities, evidence and narrative, 1998\.
  * [41] Wolpert, D. H., and Macready, W. G. No free lunch theorems for optimization.  IEEE transactions on evolutionary computation 1, 1 (1997), 67–82.


# Computing SEQ-IC-LCS of Labeled Graphs

Yuki Yonemoto  Department of Information Science and Technology, Kyushu
University  Yuto Nakashima  Department of Informatics, Kyushu University
Shunsuke Inenaga  Department of Informatics, Kyushu University

###### 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}|\log|\Sigma|)$ time and
$O(|V_{1}||V_{2}||V_{3}|)$ space, where $\Sigma$ is the alphabet.

##  1 Introduction

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_ or
_hypertexts_ in the literature. Labeled graphs are a natural generalization of
usual (unary-path) strings, which can also be regarded as a compact
representation of a set of strings. After introduced by the Database community
[13], labeled graphs were then considered by the string matching community
[21, 23, 2, 22, 16, 17, 10]. Recently, graph representations of large-scale
string sets appear in the real-world applications including graph databases
[3] and pan-genomics [14]. For instance, _elastic degenerate strings_ [18, 4,
8, 19, 7], which recently gain attention with bioinformatics background, can
be regarded as a special case of labeled graphs. In the best case, a single
labeled graph can represent exponentially many strings. Thus, efficient string
algorithms that directly work on labeled graphs without expansion are of
significance both in theory and in practice.

Shimohira et al. [24] introduced the problem of computing the _longest common
subsequence_ (_LCS_) of two given labeled graphs, which, to our knowledge, the
first and the only known similarity measure of labeled graphs. Since we can
easily convert any labeled graph with string labels to an equivalent labeled
graph with single character labels (see Figure 1), in what follows, we
evaluate the size of a labeled graph by the number of vertices and edges in
the (converted) graph. Given two labeled graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$, Shimohira et al. [24] showed how to solve the LCS
problem on labeled graphs in $O(|E_{1}||E_{2}|)$ time and $O(|V_{1}||V_{2}|)$
space when both $G_{1}$ and $G_{2}$ are acyclic, and in
$O(|E_{1}||E_{2}|+|V_{1}||V_{2}|\log|\Sigma|)$ time and $O(|V_{1}||V_{2}|)$
space when $G_{1}$ and $G_{2}$ can be cyclic, where $\Sigma$ is the alphabet.
It is noteworthy that their solution is almost optimal since the quadratic
$O((|A||B|)^{1-\epsilon})$-time conditional lower bound [1, 9] with any
constant $\epsilon>0$ for the LCS problem on two strings $A,B$ also applies to
the LCS problem on labeled graphs.

The _constrained LCS problems_ on strings, which were first proposed by Tsai
[25] and then extensively studied in the literature [25, 12, 6, 11, 15, 27,
28], use a third input string $P$ which introduces a-priori knowledge of the
user to the solution string $Z$ to output. The task here is to compute the
longest common subsequence $Z$ of two target strings $A$ and $B$ that meets
the condition w.r.t. $P$, such that

STR-IC-LCS:

$Z$ includes (contains) $P$ as substring;

STR-EC-LCS:

$Z$ excludes (does not contain) $P$ as substring;

SEQ-IC-LCS:

$Z$ includes (contains) $P$ as subsequence;

SEQ-EC-LCS:

$Z$ excludes (does not contain) $P$ as subsequence.

While STR-IC-LCS can be solved in $O(|A||B|)$ time [15], the state-of-the-art
solutions to STR-EC-LCS and SEQ-IC/EC-LCS run in $O(|A||B||P|)$ time [12, 6,
11, 27].

In this paper, we consider the SEQ-IC-LCS problems on labeled graphs, where
the inputs are two target labeled graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$, and a constraint text $G_{3}=(V_{3},E_{3})$, and the
output is (the length of) a longest common subsequence of $G_{1}$ and $G_{2}$
such that $Z$ includes as subsequence some string that is represented by
$G_{3}$. 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}|\log|\Sigma|)$ time and
$O(|V_{1}||V_{2}||V_{3}|)$ space, where $\Sigma$ is the alphabet. The time
complexities of our algorithms and related work are summarized in Table 1. Our
algorithms for solving SEQ-IC-LCS on labeled graphs are based on the solutions
to SEQ-IC-LCS of usual strings proposed by Chin et al. [12]. We emphasize that
a faster $o(|E_{1}||E_{2}||E_{3}|)$-time solution to the SEQ-IC-LCS problems
implies a major improvement over the SEQ-IC-LCS problems for strings whose
best known solutions require cubic time.

A related work is the _regular language constrained sequence alignment_
(_RLCSA_) problem [5] for two input strings $A$ and $B$ in which the
constraint is given as an NFA. It is known that this problem can be solved in
$O(|A||B||V|^{3}/\log|V|)$ time [20], where $|V|$ denotes the number of states
in the NFA.

Table 1: Time complexities of algorithms for labeled graph/usual string
comparisons, for inputs text-1 $G_{1}=(V_{1},E_{1})$, text-2
$G_{2}=(V_{2},E_{2})$, and text-3 $G_{3}=(V_{3},E_{3})$. Here, a string input
of length $n$ is regarded as a unary path graph $G=(V,E)$ with $|E|=n$.

problem text-1 text-2 text-3 time complexity LCS string string -
$O(|E_{1}||E_{2}|)$ [26] DAG DAG - $O(|E_{1}||E_{2}|)$ [24] graph graph -
$O(|E_{1}||E_{2}|+|V_{1}||V_{2}|\log|\Sigma|)$ [24] SEQ-IC-LCS string string
string $O(|E_{1}||E_{2}||E_{3}|)$ [12, 6] DAG DAG DAG
$O(|E_{1}||E_{2}||E_{3}|)$ [this work] graph graph DAG
$O(|E_{1}||E_{2}||E_{3}|+|V_{1}||V_{2}||V_{3}|\log|\Sigma|)$ [this work] SEQ-
EC-LCS string string string $O(|E_{1}||E_{2}||E_{3}|)$ [11] STR-IC-LCS string
string - $O(|E_{1}||E_{2}|)$ [15] STR-EC-LCS string string -
$O(|E_{1}||E_{2}|)$ [27] RLCSA string string NFA
$O(|E_{1}||E_{2}||V_{3}|^{3}/\log|V_{3}|)$ [20]

##  2 Preliminaries

###  2.1 Strings and Graphs

Let $\Sigma$ be an alphabet. An element of $\Sigma^{*}$ is called a _string_.
The _length_ of a string $w$ is denoted by $|w|$. The _empty string_ , denoted
by $\varepsilon$, is a string of length $0$. Let
$\Sigma^{+}=\Sigma^{\ast}\setminus\\{\varepsilon\\}$. For a string $w=xyz$
with $x,y,z\in\Sigma^{*}$, strings $x$, $y$, and $z$ are called a _prefix_ ,
_substring_ , and _suffix_ of string $w$, respectively. The $i$th character of
a string $w$ is denoted by $w[i]$ for $1\leq i\leq|w|$, and the substring of
$w$ that begins at position $i$ and ends at position $j$ is denoted by
$w[i..j]$ for $1\leq i\leq j\leq|w|$. For convenience, let
$w[i..j]=\varepsilon$ for $i>j$. A string $u$ is a _subsequence_ of another
string $w$ if $u=\varepsilon$ or there exists a sequence of integers
$i_{1},\ldots,i_{|u|}$ such that $1\leq i_{1}<\cdots<i_{|u|}\leq|w|$ and
$u=w[i_{1}]\cdots w[i_{|u|}]$.

A _directed graph_ $G$ is an ordered pair $(V,E)$ of the set $V$ of _vertices_
and the set $E\subseteq V\times V$ of _edges_. The _in-degree_ of a vertex $v$
is denoted by $\mathsf{in\\_deg}(v)=|\\{u\mid(u,v)\in E\\}|$. A _path_ in a
(directed) graph $G=(V,E)$ is a sequence $v_{0},\ldots,v_{k}$ of vertices such
that $(v_{i-1},v_{i})\in E$ for every $i=1,\ldots,k$. A path
$\pi=v_{0},\ldots,v_{k}$ in graph $G$ is said to be _left-maximal_ if its
left-end vertex $v_{0}$ has no in-coming edges, and $\pi$ is said to be
_right-maximal_ if its right-end vertex $v_{k}$ has no out-going edges. A path
$\pi$ is said to be _maximal_ if $\pi$ is both left-maximal and right-maximal.
For any vertex $v\in V$, let $\mathsf{P}(v)$ denote the set of all paths
ending at vertex $v$, and $\mathsf{LMP}(v)$ denote the set of left-maximal
paths ending at $v$. The set of all paths in $G=(V,E)$ is denoted by
$\mathsf{P}(G)=\\{\mathsf{P}(v)\mid v\in V\\}$. Let $\mathsf{MP}(G)$ denote
the set of maximal paths in $G$.

###  2.2 Longest Common Subsequence (LCS) of Strings

The _longest common subsequence_ (LCS) problem for two given strings $A$ and
$B$ is to compute (the length of) the longest string $Z$ that is a
subsequences of both $A$ and $B$. It is well-known that LCS can be solved in
$O(|A||B|)$ time by using the following recurrence [26]:

$C_{i,j}=\begin{cases}0&\mbox{if $i=0$ or $j=0$};\\\ 1+C_{i-1,j-1}&\mbox{if
$i,j>0$ and $x[i]=y[j]$};\\\ \max(C_{i-1,j},C_{i,j-1})&\mbox{if $i,j>0$ and
$x[i]\not=y[j]$},\\\ \end{cases}$

where $C_{i,j}$ is the LCS length of $A[1..i]$ and $B[1..j]$.

###  2.3 SEQ-IC-LCS of Strings

Let $A$, $B$, and $P$ be strings. A string $Z$ is said to be an _SEQ-IC-LCS_
of two target strings $A$ and $B$ _including_ the pattern $P$ if $Z$ is a
longest string such that $P$ is a subsequence of $Z$ and that $Z$ is a common
subsequence of $A$ and $B$. Chin et al. [12] solved this problem in
$O(|A||B||P|)$ time by using the following recurrence:

$C_{i,j,k}=\begin{cases}0&\mbox{if $k=0$ and ($i=0$ or $j=0$)};\\\
-\infty&\mbox{if $k\neq 0$ and ($i=0$ or $j=0$)};\\\
C_{i-1,j-1,k-1}+1&\mbox{if $i,j,k>0$ and $A[i]=B[j]=P[k]$};\\\
C_{i-1,j-1,k}+1&\mbox{if $i,j>0$ and $A[i]=B[j]\neq P[k]$};\\\
\max(C_{i-1,j,k},C_{i,j-1,k})&\mbox{if $i,j>0$ and $A[i]\neq B[j]$},\\\
\end{cases}$ (1)

where $C_{i,j,k}$ is the SEQ-IC-LCS length of $A[1..i]$, $B[1..j]$, and
$P[1..k]$.

###  2.4 Labeled Graphs

A _labeled graph_ is a directed graph with vertices labeled by strings,
namely, it is a directed graph $G=(V,E,\mathit{L})$ where $V$ is the set of
vertices, $E$ is the set of edges, and $\mathit{L}:V\rightarrow\Sigma^{+}$ is
a labeling function that maps nodes $v\in V$ to non-empty strings
$\mathit{L}(v)\in\Sigma^{+}$. For a path
$\pi=v_{0},\ldots,v_{k}\in\mathsf{P}(G)$, let $\mathit{L}(\pi)$ denote the
string spelled out by $w$, namely
$\mathit{L}(\pi)=\mathit{L}(v_{0})\cdots\mathit{L}(v_{k})$. The size $|G|$ of
a labeled graph $G=(V,E,\mathit{L})$ is $|V|+|E|+\sum_{v\in
V}|\mathit{L}(v)|$. Let
$\mathsf{Subseq}(G)=\\{\mathsf{Subseq}(\mathit{L}(\pi))\mid\pi\in\mathsf{P}(G)\\}$
denote the set of subsequences of a labeled graph $G=(V,E,\mathit{L})$. For a
set $P\in\mathsf{P}(G)$ of paths in $G$, let
$\mathit{L}(P)=\\{\mathit{L}(\pi)\mid\pi\in P\\}$ denote the set of string
labels for the paths in $P$.

For a labeled graph $G=(V,E,\mathit{L})$, consider an “atomic” labeled graph
$G^{\prime}=(V^{\prime},E^{\prime},\mathit{L}^{\prime})$ such that
$\mathit{L}^{\prime}:V^{\prime}\rightarrow\Sigma$,

$\displaystyle V^{\prime}$ $\displaystyle=$
$\displaystyle\\{v_{i,j}\mid\mathit{L}^{\prime}(v_{i,j})=\mathit{L}(v_{i})[j],v_{i}\in
V,1\leq j\leq|\mathit{L}(v_{i})|\\},\mbox{ and}$ $\displaystyle E^{\prime}$
$\displaystyle=$
$\displaystyle\\{(v_{i,|\mathit{L}(v_{i})|},v_{k,1})\mid(v_{i},v_{k})\in
E\\}\cup\\{(v_{i,j},v_{i,j+1})\mid v_{i}\in V,1\leq j<|\mathit{L}(v_{i})|\\},$

that is, $G^{\prime}$ is a labeled graph with each vertex being labeled by a
single character, which represents the same set of strings as $G$. An example
is shown in Figure 1.

Figure 1: A labeled graph $G=(V,E,\mathit{L})$ with
$\mathit{L}:V\rightarrow\Sigma^{+}$ and its corresponding atomic labeled graph
$G^{\prime}=(V^{\prime},E^{\prime},\mathit{L}^{\prime})$ with
$\mathit{L}^{\prime}:V^{\prime}\rightarrow\Sigma$.

Since $|V^{\prime}|=\sum_{v\in V}|\mathit{L}(v)|$,
$|E^{\prime}|=|E|+\sum_{v\in V}(|\mathit{L}(v)|-1)$, and $\sum_{v^{\prime}\in
V^{\prime}}|\mathit{L}(v^{\prime})|=\sum_{v\in V}|\mathit{L}(v)|$, we have
$|G^{\prime}|=O(|G|)$. We remark that given $G$, we can easily construct
$G^{\prime}$ in $O(|G|)$ time. Observe that
$\mathsf{Subseq}(G)=\mathsf{Subseq}(G^{\prime})$ also holds.

In the sequel we only consider atomic labeled graphs where each vertex is
labeled with a single character.

###  2.5 LCS of Acyclic Labeled Graphs

The problem of computing the length of longest common subsequence of two input
acyclic labeled graphs is formalized by Shimohira et al. [24] as follows.

######  Problem 1 (Longest common subsequence problem for acyclic labeled
graphs).

Input:

Labeled graphs $G_{1}=(V_{1},E_{1},\mathit{L}_{1})$ and
$G_{2}=(V_{2},E_{2},\mathit{L}_{2})$.

Output:

The length of a longest string in
$\mathsf{Subseq}(G_{1})\cap\mathsf{Subseq}(G_{2})$.

This problem can be solved in $O(|E_{1}||E_{2}|)$ time and $O(|V_{1}||V_{2}|)$
space by sorting $G_{1}$ and $G_{2}$ topologically and using the following
recurrence:

$\displaystyle C^{\prime}_{i,j}=$ (2)
$\displaystyle\begin{cases}1\\!+\\!\max(\\{C^{\prime}_{k,\ell}\mid{(v_{1,k},v_{1,i})\\!\in\\!E_{1},(v_{2,\ell},v_{2,j})\\!\in\\!E_{2}}\\}\cup\\{0\\})&\mbox{if
$\mathit{L}_{1}(v_{1,i})\\!=\\!\mathit{L}_{2}(v_{2,j})$};\\\
\max\\!\left(\begin{array}[]{l}\\{C^{\prime}_{k,j}\mid{(v_{1,k},v_{1,i})\\!\in\\!E_{1}}\\}\cup{}\\\
\\{C^{\prime}_{i,\ell}\mid{(v_{2,\ell},v_{2,j})\\!\in\\!E_{2}}\\}\cup\\{0\\}\end{array}\right)&\mbox{otherwise},\end{cases}$

where $v_{1,i}$ and $v_{2,j}$ are respectively the $i$th and $j$th vertices of
$G_{1}$ and in $G_{2}$ in topological order, for $1\leq i\leq|V_{1}|$ and
$1\leq j\leq|V_{2}|$, and $C^{\prime}_{i,j}$ is the length of a longest string
in
$\mathsf{Subseq}(\mathit{L}_{1}(\mathsf{P}(v_{1,i})))\cap\mathsf{Subseq}(\mathit{L}_{2}(\mathsf{P}(v_{2,j})))$.

###  2.6 LCS of Cyclic Labeled Graphs

Here we consider a generalized version of Problem 1 where the input labeled
graphs $G_{1}$ and/or $G_{2}$ can be cyclic. In this problem, the output is
$\infty$ if there is a string
$s\in\mathsf{Subseq}(G_{1})\cap\mathsf{Subseq}(G_{2})$ such that $|s|=\infty$,
and that is the length of a longest string in
$\mathsf{Subseq}(G_{1})\cap\mathsf{Subseq}(G_{2})$. Shimohira et al. [24]
proposed an $O(|E_{1}||E_{2}|+|V_{1}||V_{2}|\log{|\Sigma|})$ time and
$O(|V_{1}||V_{2}|)$ space algorithm solving this problem. Their algorithm
judges whether the output is $\infty$ by using a balanced tree, and computes
the length of the solution by using Equation (2) and the balanced tree if the
output is not $\infty$.

##  3 The SEQ-IC-LCS Problem for Labeled Graphs

In this paper, we tackle the problem of computing the SEQ-IC-LCS length of
three labeled graphs, which formalized as follows:

######  Problem 2 (SEQ-IC-LCS problem for labeled graphs).

Input:

Labeled graphs $G_{1}=(V_{1},E_{1},\mathit{L}_{1})$,
$G_{2}=(V_{2},E_{2},\mathit{L}_{2})$, and
$G_{3}=(V_{3},E_{3},\mathit{L}_{3})$.

Output:

The length of a longest string in the set
$\\{z\mid\exists~{}q\in\mathit{L}_{3}(\mathsf{MP}(G_{3}))\mbox{ such that
}q\in\mathsf{Subseq}(z)\mbox{ and
}z\in\mathsf{Subseq}(G_{1})\cap\mathsf{Subseq}(G_{2})\\}$.

Intuitively, Problem 2 asks to compute a longest string $z$ such that $z$ is a
subsequence occurring in both $G_{1}$ and $G_{2}$ and that there exists a
string $q$ which corresponds to a maximal path of $G_{3}$ and is a subsequence
of $z$.

For a concrete example, see the labeled graphs $G_{1}$, $G_{2}$ and $G_{3}$ of
Figure 2. String $\mathtt{cdba}$ is a common subsequence of $G_{1}$ and
$G_{2}$ and that contains an element $\mathtt{ba}$ of a maximal path string in
$\mathit{L}_{3}(\mathsf{MP}(G_{3}))$. Since $\mathtt{cdba}$ is such a longest
string, we ouput the SEQ-IC-LCS length $|\mathtt{cdba}|=4$ as the solution to
this instance.

In the sequel, Section 4 presents our solution to the case where the all input
labeled graphs are acyclic, and Section 5 presents our solutions case where
$G_{1}$ and/or $G_{2}$ can be cyclic and $G_{3}$ is acyclic.

##  4 Computing SEQ-IC-LCS of Acyclic Labeled Graphs

In this section, we present our algorithm which solves Problem 2 in the case
where all of $G_{1}$, $G_{2}$ and $G_{3}$ are acyclic. The following is our
result:

######  Theorem 1.

Problem 2 where input labeled graphs $G_{1}$, $G_{2}$ and $G_{3}$ are all
acyclic is solvable in $O(|E_{1}||E_{2}||E_{3}|)$ time and
$O(|V_{1}||V_{2}||V_{3}|)$ space.

  * Proof. We perform topological sort to the vertices of $G_{1}$, $G_{2}$, and $G_{3}$ in $O(|E_{1}|+|E_{2}|+|E_{3}|)$ time and $O(|V_{1}|+|V_{2}|+|V_{3}|)$ space. For $1\leq i\leq|V_{1}|$, $1\leq j\leq|V_{2}|$, and $1\leq k\leq|V_{3}|$, let $v_{1,i}$, $v_{2,j}$, $v_{3,k}$ denote the $i$th, $j$th, and $k$th vertices in $G_{1}$, $G_{2}$, and $G_{3}$ in topological order, respectively. Let

$\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})=\left\\{z~{}\middle|~{}\begin{array}[]{l}\exists
q\in\mathit{L}_{3}(\mathsf{LMP}(v_{3,k}))\mbox{ such that
}q\in\mathsf{Subseq}(z)\\\ \mbox{and
}z\in\mathsf{Subseq}(\mathit{L}_{1}(\mathsf{P}(v_{1,i})))\cap\mathsf{Subseq}(\mathit{L}_{2}(\mathsf{P}(v_{2,j})))\end{array}\right\\}$

be the set of candidates of SEQ-IC-LCS strings for the maximal induced graphs
of $G_{1}$, $G_{2}$, and $G_{3}$ whose sinks are $v_{1,i}$, $v_{2,j}$, and
$v_{3,k}$, respectively. Let $D_{i,j,k}$ denote the length of a longest string
in $\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})$. The solution to
Problem 2 (the SEQ-IC-LCS length) is the maximum value of $D_{i,j,k}$ for
which $v_{3,k}$ does not have out-going edges (i.e. $v_{3,k}$ is the end of a
maximal path in $G_{3}$).

When $k=0$, then the problem is equivalent to Problem 1 of computing SEQ-IC-
LCS of strings. In that follows, we show how to compute $D_{i,j,k}$ for $k>0$:

    1. 1.

If $\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})=\mathit{L}_{3}(v_{3,k})$,
there are three cases to consider:

      1. (a)

If $v_{1,i}$ does not have in-coming edges or $v_{2,j}$ does not have in-
coming edges, and if $v_{3,k}$ does not have in-coming edges (i.e.,
$\mathsf{in\\_deg}(v_{1,i})=\mathsf{in\\_deg}(v_{3,k})=0$, or
$\mathsf{in\\_deg}(v_{2,j})=\mathsf{in\\_deg}(v_{3,k})=0$), then clearly
$D_{i,j,k}=1$.

      2. (b)

If $v_{1,i}$ does not have in-coming edges or $v_{2,j}$ does not have in-
coming edges, and if $v_{3,k}$ has some in-coming edge(s) (i.e.,
$\mathsf{in\\_deg}(v_{1,i})=0$ and $\mathsf{in\\_deg}(v_{3,k})\geq 1$, or
$\mathsf{in\\_deg}(v_{2,j})=0$ and $\mathsf{in\\_deg}(v_{3,k})\geq 1$), then
clearly $D_{i,j,k}=-\infty$.

      3. (c)

If both $v_{1,i}$ and $v_{2,j}$ have some in-coming edge(s) and $v_{3,k}$ does
not have in-coming edges (i.e., $\mathsf{in\\_deg}(v_{1,i})\geq 1$,
$\mathsf{in\\_deg}(v_{2,j})\geq 1$, and $\mathsf{in\\_deg}(v_{3,k})=0$), then
let $v_{1,x}$ and $v_{2,y}$ be any nodes s.t. $(v_{1,x},v_{1,i})\in E_{1}$,
and $(v_{2,y},v_{2,j})\in E_{2}$, respectively. Let $s$ be a longest string in
$\mathsf{Subseq}(\mathit{L}_{1}(\mathsf{P}(v_{1,i})))\cap\mathsf{Subseq}(\mathit{L}_{2}(\mathsf{P}(v_{2,j})))$.
Assume on the contrary that there exists a string
$t\in\mathsf{Subseq}(\mathit{L}_{1}(\mathsf{P}(v_{1,x})))\cap\mathsf{Subseq}(\mathit{L}_{2}(\mathsf{P}(v_{2,y})))$
such that $|t|>|s|-1$. This contradicts that $s$ is a longest common
subsequence of $\mathit{L}_{1}(\mathsf{P}(v_{1,i}))$ and
$\mathit{L}_{2}(\mathsf{P}(v_{2,j}))$, since
$\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})$. Hence $|t|\leq|s|-1$. If
$v_{1,x}$ and $v_{2,y}$ are vertices satisfying $C^{\prime}_{x,y,0}=|s|-1$,
then $C^{\prime}_{i,j,k}=C^{\prime}_{x,y,0}+1$. Note that such nodes $v_{1,x}$
and $v_{2,y}$ always exist.

      4. (d)

Otherwise (all $v_{1,i}$, $v_{2,j}$, and $v_{3,k}$ have some in-coming
edge(s)), let $v_{1,x}$, $v_{2,y}$ and $v_{3,z}$ be any nodes s.t.
$(v_{1,x},v_{1,i})\in E_{1}$, $(v_{2,y},v_{2,j})\in E_{2}$ and
$(v_{3,z},v_{3,k})\in E_{3}$, respectively. Let $s$ be a longest string in
$\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})$. Assume on the contrary
that there exists a string
$t\in\mathsf{S}_{\mathrm{IC}}(v_{1,x},v_{2,y},v_{3,z})$ such that $|t|>|s|-1$.
This contradicts that $s$ is a SEQ-IC-LCS of
$\mathit{L}_{1}(\mathsf{P}(v_{1,i}))$, $\mathit{L}_{2}(\mathsf{P}(v_{2,j}))$
and $\mathit{L}_{3}(\mathsf{LMP}(v_{3,k}))$, since
$\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})=\mathit{L}_{3}(v_{3,k})$.
Hence $|t|\leq|s|-1$. If $v_{1,x}$, $v_{2,y}$ and $v_{3,z}$ are vertices
satisfying $D_{x,y,z}=|s|-1$, then $D_{i,j,k}=D_{x,y,z}+1$. Note that such
nodes $v_{1,x}$, $v_{2,y}$ and $v_{3,z}$ always exist.

    2. 2.

If
$\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})\neq\mathit{L}_{3}(v_{3,k})$,
there are two cases to consider:

      1. (a)

If $v_{1,i}$ does not have in-coming edges or $v_{2,j}$ does not have-incoming
edges (i.e., $\mathsf{in\\_deg}(v_{1,i})=0$ or
$\mathsf{in\\_deg}(v_{2,j})=0$), then clearly $D_{i,j,k}$ does not exist and
let $D_{i,j,k}=-\infty$.

      2. (b)

Otherwise (both $v_{1,i}$ and $v_{2,j}$ have in-coming edge(s)), let $v_{1,x}$
and $v_{2,y}$ be any nodes s.t. $(v_{1,x},v_{1,i})\in E_{1}$ and
$(v_{2,y},v_{2,j})\in E_{2}$, respectively. Let $s$ be a longest string in
$\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})$. Assume on the contrary
that there exists a string
$t\in\mathsf{S}_{\mathrm{IC}}(v_{1,x},v_{2,y},v_{3,k})$ such that $|t|>|s|-1$.
This contradicts that $s$ is a SEQ-IC-LCS of
$\mathit{L}_{1}(\mathsf{P}(v_{1,i}))$, $\mathit{L}_{2}(\mathsf{P}(v_{2,j}))$
and $\mathit{L}_{3}(\mathsf{LMP}(v_{3,k}))$, since
$\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})$. Hence $|t|\leq|s|-1$. If
$v_{1,x}$, $v_{2,y}$ and $v_{3,k}$ are vertices satisfying $D_{x,y,k}=|s|-1$,
then $D_{i,j,k}=D_{x,y,k}+1$. Note that such nodes $v_{1,x}$, $v_{2,y}$ and
$v_{3,k}$ always exist.

    3. 3.

If $\mathit{L}_{1}(v_{1,i})\neq\mathit{L}_{2}(v_{2,j})$, there are two cases
to consider:

      1. (a)

If $v_{1,i}$ does not have in-coming edges and $v_{2,j}$ does not have in-
coming edges (i.e.,
$\mathsf{in\\_deg}(v_{1,i})=\mathsf{in\\_deg}(v_{2,j})=0$), then clearly
$D_{i,j,k}$ does not exist and let $D_{i,j,k}=-\infty$.

      2. (b)

Otherwise ($v_{1,i}$ has some in-coming edge(s) or $v_{2,j}$ has some in-
coming edge(s)), let $v_{1,x}$ and $v_{2,y}$ be any nodes such that
$(v_{1,x},v_{1,i})\in E_{1}$ and $(v_{2,y},v_{2,j})\in E_{2}$, respectively.
Let $s$ be a $\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})$. Assume on
the contrary that there exists a string
$t\in\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})$ such that $|t|>|s|$.
This contradicts that $s$ is a SEQ-IC-LCS of
$\mathit{L}_{1}(\mathsf{P}(v_{1,i}))$, $\mathit{L}_{2}(\mathsf{P}(v_{2,j}))$
and $\mathit{L}_{3}(\mathsf{LMP}(v_{3,k}))$, since
$\mathsf{S}_{\mathrm{IC}}(v_{1,x},v_{2,y},v_{3,k})\subseteq\mathsf{S}_{\mathrm{IC}}(v_{1,i},v_{2,j},v_{3,k})$.
Hence $|t|\leq|s|$. If $v_{1,x}$ is a vertex satisfying $D_{x,j,k}=|z|$, then
$D_{i,j,k}=D_{x,j,k}$. Similarly, if $v_{2,y}$ is a vertex satisfying
$D_{i,y,k}=|s|$, then $D_{i,j,k}=D_{i,y,k}$. Note that such node $v_{1,x}$ or
$v_{2,y}$ always exists.

Consequently we obtain the following recurrence:

$\displaystyle D_{i,j,k}=$ (3) $\displaystyle\begin{cases}\mbox{Recurrence in
Equation}~{}(\ref{eq:subseq-nl})&\mbox{if $k=0$};\\\
1+\max\left(\left\\{D_{x,y,z}~{}\middle|~{}\begin{array}[]{l}(v_{1,x},v_{1,i})\in
E_{1},\\\ (v_{2,y},v_{2,j})\in E_{2},\\\ (v_{3,z},v_{3,k})\in E_{3},\\\ \mbox{
or }z=0\end{array}\right\\}\cup\\{\gamma\\}\right)&\begin{array}[]{l}\mbox{if
}k>0\mbox{ and}\\\ \mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})\\\
=\mathit{L}_{3}(v_{3,k});\end{array}\\\
\max\left(\left\\{1+D_{x,y,k}~{}\middle|~{}\begin{array}[]{l}(v_{1,x},v_{1,i})\\!\in\\!E_{1},\\\
(v_{2,y},v_{2,j})\\!\in\\!E_{2}\end{array}\right\\}\cup\\{-\infty\\}\right)&\begin{array}[]{l}\mbox{if
}k>0\mbox{ and}\\\ \mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})\\\
\neq\mathit{L}_{3}(v_{3,k});\end{array}\\\
\max\left(\begin{array}[]{l}\\{D_{x,j,k}\mid(v_{1,x},v_{1,i})\in
E_{1}\\}\cup{}\\\ \\{D_{i,y,k}\mid{(v_{2,y},v_{2,j})\in
E_{2}}\\}\cup\\{-\infty\\}\end{array}\right)&\mbox{otherwise}.\end{cases}$

where

$\displaystyle\gamma$ $\displaystyle=$
$\displaystyle\begin{cases}0&\begin{array}[]{l}\mbox{if $v_{1,i}$ does not
have in-coming edges at all or $v_{2,j}$ does not have}\\\ \mbox{in-coming
edges at all, and $v_{3,k}$ does not have in-coming edges};\end{array}\\\
-\infty&\mbox{otherwise}.\end{cases}$

We compute $D_{i,j,k}$ for all $1\leq i\leq|V_{1}|$, $1\leq j\leq|V_{2}|$ and
$0\leq k\leq|V_{3}|$, using a dynamic programming table of size
$O(|V_{1}||V_{2}||V_{3}|)$.

Below we analyze the time complexity for computing $D_{i,j,k}$ with the
recurrence:

    * –

The first case with Equation (2) takes $O(|E_{1}||E_{2}|)$ time (Section 2.5).

    * –

Second, let us analyze the time cost for computing

$M_{i,j,k}=\max\\{D_{x,y,z}\mid(v_{1,x},v_{1,i})\in E_{1},(v_{2,y},v_{2,j})\in
E_{2},(v_{3,z},v_{3,k})\in E_{3},\mbox{ or }z=0\\}$

in the second case of the recurrence for all $i,j,k$. For each fixed pair of
$(v_{1,x},v_{1,i})\in E_{1}$ and $(v_{2,y},v_{2,j})\in E_{2}$, we refer the
value of $D_{x,y,z}$ for all $1\leq z<k$ such that $(v_{3,z},v_{3,k})\in
E_{3}$, in $O(|E_{3}|)$ time. For each fixed $(v_{1,x},v_{1,i})\in E_{1}$, we
refer the value of $D_{x,y,z}$ for all $1\leq y<j$ such that
$(v_{2,y},v_{2,j})\in E_{2}$ and all $1\leq z<k$ such that
$(v_{3,z},v_{3,k})\in E_{3}$, in $O(|E_{2}||E_{3}|)$ time. Therefore, the
total time complexity for computing all $M_{i,j,k}$ for all $i,j,k$ is
$O(|E_{1}||E_{2}||E_{3}|)$.

    * –

Third, let us analyze the time cost for computing

$M^{\prime}_{i,j,k}=\max\\{D_{x,y,k}\mid(v_{1,x},v_{1,i})\in
E_{1},(v_{2,y},v_{2,j})\in E_{2}\\}$

in the third case of the recurrence for all $i,j,k$. For each fixed pair of
$(v_{1,x},v_{1,i})\in E_{1}$ and $(v_{2,y},v_{2,j})\in E_{2}$, we refer the
value of $D_{x,y,k}$ for all $1\leq k\leq|V_{3}|$, in $O(|V_{3}|)$ time. For
each fixed $(v_{1,x},v_{1,i})\in E_{1}$, we refer the value of $D_{x,y,k}$ for
all $1\leq y<j$ such that $(v_{2,y},v_{2,j})\in E_{2}$ and all $1\leq
k\leq|V_{3}|$, in $O(|E_{2}||V_{3}|)$ time. Therefore, the total time
complexity for computing $M^{\prime}_{i,j,k}$ for all $i,j,k$ is
$O(|E_{1}||E_{2}||V_{3}|)\subseteq O(|E_{1}||E_{2}||E_{3}|)$.

    * –

Fourth, let us analyze the time cost for computing

$M^{\prime\prime}_{i,j,k}=\max\\{D_{x,j,k},D_{i,y,k}\mid(v_{1,x},v_{1,i})\in
E_{1},(v_{2,y},v_{2,j})\in E_{2}\\}$

in the fourth case of the recurrence for all $i,j,k$. For each fixed
$(v_{1,x},v_{1,i})\in E_{1}$, we refer the value of $D_{x,j,k}$ for all $1\leq
j\leq|V_{2}|$ and all $1\leq k\leq|V_{3}|$ in $O(|V_{2}||V_{3}|)$ time.
Similarly, for each fixed $(v_{2,y},v_{2,j})\in E_{2}$, we refer the value of
$D_{i,y,k}$ for all $1\leq i\leq|V_{1}|$ and all $1\leq k\leq|V_{3}|$ in
$O(|V_{1}||V_{3}|)$ time. Therefore, the total time cost for computing
$M^{\prime\prime}_{i,j,k}$ for all $i,j,k$ is
$O(|V_{3}|(|V_{2}||E_{1}|+|V_{1}||E_{2}|))\subseteq O(|E_{1}||E_{2}||E_{3}|)$.

Thus the total time complexity is $O(|E_{1}||E_{2}||E_{3}|)$. ∎

An example of computing $D_{i,j,k}$ using dynamic programming is show in
Figure 2. We remark that the recurrence in Equation (3) is a natural
generalization of the recurrence in Equation (1) for computing the SEQ-IC-LCS
length of given two strings.

Algorithm 1 in Appendix A shows a pseudo-code of our algorithm which solves
Problem 2 in the case where all $G_{1}$, $G_{2}$ and $G_{3}$ are acyclic.

Figure 2: Example of dynamic programming table $D$ for computing the SEQ-IC-
LCS length of acyclic labeled graphs $G_{1}$, $G_{2}$ and $G_{3}$. Each vertex
is annotated with its topological order. In this example, $v_{3,2}$ and
$v_{3,4}$ with $k\in\\{2,4\\}$ in $G_{3}$ are vertices with no out-going
edges. The maximum value of $D_{i,j,k}$ with $k\in\\{2,4\\}$ is $D_{6,6,2}=4$,
and the corresponding SEQ-IC-LCS is $\mathtt{cdba}$ of length $4$.

##  5 Computing SEQ-IC-LCS of Cyclic Labeled Graphs

In this section, we present an algorithm to solve Problem 2 in case where
$G_{1}$ and/or $G_{2}$ can be cyclic and $G_{3}$ is acyclic. We output
$\infty$ if the set of output candidates in Problem 2 contains a string of
infinite length, and outputs the (finite) SEQ-IC-LCS length otherwise.

Figure 3: Example of dynamic programming table $\hat{D}$ for computing the
SEQ-IC-LCS length of cyclic labeled graphs $G_{1}$ and $G_{2}$, and acyclic
labeled graph $G_{3}$. $\hat{G}_{1}$ and $\hat{G}_{2}$ are the labeled graphs
which are transformed from $G_{1}$ and $G_{2}$ by grouping vertices into
strongly connected components. Each vertex is annotated with its topological
order. In this example, $v_{3,2}$ and $v_{3,4}$ with $k\in\\{2,4\\}$ in
$G_{3}$ are vertices with no out-going edges. The maximum value of
$\hat{D}_{i,j,k}$ with $k\in\\{2,4\\}$ is $\hat{D}_{4,3,2}=3$, and the
corresponding SEQ-IC-LCS is $\mathtt{aab}$ of length $3$.

To deal with cyclic graphs, we follow the approach by Shimohira et al. [24]
which transforms a cyclic labeled graph $G=(V,E,\mathit{L})$ into an acyclic
labeled graph $\hat{G}=(\hat{V},\hat{E},\hat{\mathit{L}})$ based on the
strongly connected components.

For each vertex $v\in V$, let $[v]$ denote the set of vertices that belong to
the same strongly connected component. Formally,
$\hat{G}=(\hat{V},\hat{E},\hat{\mathit{L}})$ is defined by

$\displaystyle\hat{V}$ $\displaystyle=$ $\displaystyle\\{[v]\mid v\in V\\},$
$\displaystyle\hat{E}$ $\displaystyle=$
$\displaystyle\\{([v],[u])\mid[v]\neq[u],\mbox{$(\hat{v},\hat{u})\in E$ for
some $\hat{v}\in[v]$, $\hat{u}\in[u]$}\\}\cup\\{(v,v)\mid|[v]|\geq 2\\},$

and $\hat{\mathit{L}}([v])=\\{\mathit{L}(v)\mid v\in[v]\\}\subseteq\Sigma$. We
regard each $[v]$ as a single vertex that is contracted from vertices in
$[v]$. Observe that $\mathsf{Subseq}(\hat{G})=\mathsf{Subseq}(G)$. An example
of transformed acyclic labeled graphs is shown in Figure 3.

It is possible that a vertex $\hat{v}\in\hat{V}$ in the transformed graph
$\hat{G}$ has a self-loop. We regard that a self-loop $(\hat{v},\hat{v})$ is
also an in-coming edge of vertex $\hat{v}$. We say that vertex $\hat{v}$ does
not have in-coming edges _at all_ , if $\hat{v}$ does not have in-coming edges
from _any_ vertex in $\hat{V}$ (including $\hat{v}$).

Our main result of this section follows:

######  Theorem 2.

Problem 2, where input labeled graphs $G_{1}$ and $G_{2}$ can be cyclic and
$G_{3}$ is acyclic, is solvable in
$O(|E_{1}||E_{2}||E_{3}|+|V_{1}||V_{2}||V_{3}|\log|\Sigma|)$ time and
$O(|V_{1}||V_{2}||V_{3}|)$ space.

  * Proof. We first transform cyclic labeled graphs $G_{1}$ and $G_{2}$ into corresponding acyclic labeled graphs $\hat{G}_{1}$ and $\hat{G}_{2}$, as described previously. For $1\leq i\leq|\hat{V}_{1}|$ and $1\leq j\leq|\hat{V}_{2}|$, let $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ respectively denote the $i$th and $j$th vertices in $\hat{G}_{1}$ and $\hat{G}_{2}$ in topological order. Let $v_{3,k}$ denote the $k$-th vertex in topological ordering in $G_{3}$ for $1\leq k\leq|V_{3}|$.

Let

$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})=\left\\{z~{}\middle|~{}\begin{array}[]{l}\exists
q\in\mathit{L}_{3}(\mathsf{MP}(v_{3,k}))\mbox{ such that
}q\in\mathsf{Subseq}(z)\\\ \mbox{and
}z\in\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{P}(\hat{v}_{1,i})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{P}(\hat{v}_{2,j})))\end{array}\right\\}.$

Let $\hat{D}_{i,j,k}$ denote the length of a longest string in
$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})$. For
convenience, we let $\hat{D}_{i,j,k}=-\infty$ if
$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})=\emptyset$.
The solution to Problem 2 (the SEQ-IC-LCS length) is the maximum value of
$\hat{D}_{i,j,k}$ for which $v_{3,k}$ has no out-going edges (i.e. $v_{3,k}$
is the end of a maximal path in $G_{3}$).

$\hat{D}_{i,j,k}$ can be computed as follows:

    1. 1.

If both $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ are cyclic vertices (i.e.
$|[\hat{v}_{1,i}]|\geq 2$ and $|[\hat{v}_{2,j}]|\geq 2$), then remark that
both $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ have some self-loop(s). There are
four cases to consider:

      1. (a)

If $k=0$, there are two cases to consider:

        1. i.

If
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$,
then clearly $\hat{D}_{i,j,k}=\infty$.

        2. ii.

Otherwise, there are two cases to consider:

          1. A.

If the in-coming edges of $\hat{v}_{1,i}$ are $\hat{v}_{2,j}$ only self-loops,
then clearly $\hat{D}_{i,j,k}=0$.

          2. B.

Otherwise ($\hat{v}_{1,i}$ has some in-coming edge(s) other than self-loops,
or $\hat{v}_{2,j}$ has some in-coming edge(s) other than self-loops), let
$\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ be any nodes such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively. Let $s$ be a
longest string in the set
$\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j})))$.
Assume on the contrary that there is a string
$t\in\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,x})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j})))$
such that $|t|>|s|$. This contradicts that $s$ is a longest common subsequence
of $\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i}))$ and
$\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j}))$, since
$\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,x})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j})))\subseteq\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j})))$.
Hence $|t|\leq|s|$. If $\hat{v}_{1,x}$ is a vertex satisfying
$\hat{D}_{x,j,k}=|s|$, then $\hat{D}_{i,j,k}=\hat{D}_{x,j,k}$. Similarly, if
$\hat{v}_{2,y}$ is a vertex satisfying $\hat{D}_{i,y,k}=|s|$, then
$\hat{D}_{i,j,k}=\hat{D}_{i,y,k}$. Note that such $\hat{v}_{1,x}$ or
$\hat{v}_{2,y}$ always exists.

      2. (b)

If $k>0$ and
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}\neq\emptyset$,
there are two cases to consider:

        1. i.

If $v_{3,k}$ has no in-coming edges, let $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$
be any nodes such that $(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively (these edges may
be self-loops). If $\hat{D}_{x,y,0}=-\infty$ for all $1\leq x<i$ and $1\leq
y<j$, then clearly $\hat{D}_{i,j,k}=-\infty$. Otherwise, clearly
$\hat{D}_{i,j,k}=\infty$.

        2. ii.

Otherwise ($v_{3,k}$ has some in-coming edge(s)), let $\hat{v}_{1,x}$,
$\hat{v}_{2,y}$ and $v_{3,z}$ be any nodes such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$,
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$ and $(v_{3,z},v_{3,k})\in
E_{3}$, respectively (the first two edges may be self-loops). If
$\hat{D}_{x,y,z}=-\infty$ for all $1\leq x<i$ and $1\leq y<j$, then clearly
$\hat{D}_{i,j,k}=-\infty$. Otherwise, $\hat{D}_{i,j,k}=\infty$.

      3. (c)

If $k>0$ and
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}=\emptyset$
and
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$,
there are two cases to consider:

        1. i.

If the in-coming edges of $\hat{v}_{1,i}$ are $\hat{v}_{2,j}$ only self-loops,
then clearly $\hat{D}_{i,j,k}=-\infty$.

        2. ii.

Otherwise ($\hat{v}_{1,i}$ has some in-coming edge(s) other than self-loops,
or $\hat{v}_{2,j}$ has some in-coming edge(s) other than self-loops), let
$\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ be any nodes such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively. If all
$\hat{D}_{x,y,k}=-\infty$, then clearly $\hat{D}_{i,j,k}=-\infty$. Otherwise,
clearly $\hat{D}_{i,j,k}=\infty$.

      4. (d)

If $k>0$ and
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})=\emptyset$,
there are two cases to consider:

        1. i.

If the in-coming edges of $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ are only self-
loops, then clearly $\hat{D}_{i,j,k}=-\infty$.

        2. ii.

Otherwise ($\hat{v}_{1,i}$ has some in-coming edge(s) other than self-loops,
or $\hat{v}_{2,j}$ has some in-coming edge(s) other than self-loops), let
$\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ be any nodes such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively. Let $s$ be a
longest string in
$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})$. Assume
on the contrary that there exists a string
$t\in\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})$ such
that $|t|>|s|$. This contradicts that $s$ is a SEQ-IC-LCS of
$\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i}))$,
$\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j}))$ and
$\mathit{L}_{3}(\mathsf{MP}(v_{3,k}))$, since
$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,x},\hat{v}_{2,y},v_{3,k})\subseteq\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})$.
Hence $|t|\leq|s|$. If $\hat{v}_{1,x}$ is a vertex satisfying
$\hat{D}_{x,j,k}=|z|$, then $\hat{D}_{i,j,k}=\hat{D}_{x,j,k}$. Similarly, if
$\hat{v}_{2,y}$ is a vertex satisfying $\hat{D}_{i,y,k}=|s|$, then
$\hat{D}_{i,j,k}=\hat{D}_{i,y,k}$. Note that such $\hat{v}_{1,x}$ or
$\hat{v}_{2,y}$ always exists.

    2. 2.

Otherwise ($v_{1,i}$ is not a cyclic vertex and/or $v_{2,j}$ is not a cyclic
vertex), there are four cases to consider:

      1. (a)

If $k=0$, there are two cases to consider:

        1. i.

If
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$,
there are two cases to consider:

          1. A.

If $\hat{v}_{1,i}$ does not have in-coming edges at all or $\hat{v}_{2,j}$
does not have in-coming edges at all, then clearly $\hat{D}_{i,j,k}=1$.

          2. B.

Otherwise (both $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ have some in-coming
edge(s) including self-loops), let $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ be any
nodes such that $(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively. Let $s$ be a
longest string in the set $\mathsf{Subseq}(\hat{\mathit{L}}_{1}$
$(\mathsf{LMP}(\hat{v}_{1,i})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j})))$.
Assume on the contrary that there is a string
$t\in\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,x})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,y})))$
such that $|t|>|s|-1$. This contradicts that $s$ is a longest common
subsequence of $\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i}))$ and
$\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j}))$, since
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$.
Hence $|t|\leq|s|-1$. If $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ are vertices
satisfying $\hat{D}_{x,y,k}=|s|-1$, then $\hat{D}_{i,j,k}=\hat{D}_{x,y,k}+1$.
Note that such $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ always exist.

        2. ii.

Otherwise, then this case is the same as Case 1(a)ii.

      2. (b)

If
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}\neq\emptyset$,
there are three cases to consider:

        1. i.

If $\hat{v}_{1,i}$ does not have in-coming edges at all or $\hat{v}_{2,j}$
does not have in-coming edges at all, and if $v_{3,k}$ does not have in-coming
edges, then clearly $\hat{D}_{i,j,k}=1$.

        2. ii.

If $\hat{v}_{1,i}$ does not have in-coming edges at all or $\hat{v}_{2,j}$
does not have in-coming edge at all, and if $v_{3,k}$ has some in-coming
edge(s), then clearly $\hat{D}_{i,j,k}=-\infty$.

        3. iii.

If both $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ have some in-coming edge(s)
including self-loops and $v_{3,k}$ does not have in-coming edges, let
$\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ be any nodes such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively. Let $s$ be a
longest string in the set
$\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j})))$.
Assume on the contrary that there exists a string
$t\in\mathsf{Subseq}(\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,x})))\cap\mathsf{Subseq}(\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,y})))$
such that $|t|>|s|-1$. This contradicts that $s$ is a longest common
subsequence of $\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i}))$ and
$\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j}))$, since
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$.
Hence $|t|\leq|s|-1$. If $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ are vertices
satisfying $\hat{D}_{x,y,0}=|s|-1$, then $\hat{D}_{i,j,k}=\hat{D}_{x,y,0}+1$.
Note that such $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ always exist.

        4. iv.

Otherwise (all $\hat{v}_{1,i}$, $\hat{v}_{2,j}$, and $\hat{v}_{3,k}$ have some
in-coming edge(s) including self-loops), let $\hat{v}_{1,x}$, $\hat{v}_{2,y}$
and $v_{3,z}$ be any nodes such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$,
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, and $(v_{3,z},v_{3,k})\in
E_{3}$, respectively. Let $s$ be a longest string in
$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})$. Assume
on the contrary that there exists a string
$t\in\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,x},\hat{v}_{2,y},v_{3,z})$ such
that $|t|>|s|-1$. This contradicts that $s$ is a SEQ-IC-LCS of
$\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i}))$,
$\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j}))$ and
$\mathit{L}_{3}(\mathsf{MP}(v_{3,k}))$, since
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap{\mathit{L}_{3}(v_{3,k})}\neq\emptyset$.
Hence $|t|\leq|s|-1$. If $\hat{v}_{1,x}$, $\hat{v}_{2,y}$ and $v_{3,z}$ are
vertices satisfying $\hat{D}_{x,y,z}=|s|-1$, then
$\hat{D}_{i,j,k}=\hat{D}_{x,y,z}+1$. Note that such $\hat{v}_{1,x}$,
$\hat{v}_{2,y}$ and $v_{3,z}$ always exist.

      3. (c)

If
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}=\emptyset$
and
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$,
there are two cases to consider:

        1. i.

If $\hat{v}_{1,i}$ does not have in-coming edges at all or $\hat{v}_{2,j}$
does not have in-coming edges at all, then clearly $\hat{D}_{i,j,k}=-\infty$.

        2. ii.

Otherwise (both $\hat{v}_{1,i}$ and $\hat{v}_{2,j}$ have some in-coming edges
including self-loops), let $\hat{v}_{1,x}$ and $\hat{v}_{2,y}$ be any nodes
such that $(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$, respectively. Let $s$ be a
longest string in
$\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,i},\hat{v}_{2,j},v_{3,k})$. Assume
on the contrary that there exists a string
$t\in\hat{\mathsf{S}}_{\mathrm{IC}}(\hat{v}_{1,x},\hat{v}_{2,y},v_{3,k})$ such
that $|t|>|s|-1$. This contradicts that $s$ is a SEQ-IC-LCS of
$\hat{\mathit{L}}_{1}(\mathsf{LMP}(\hat{v}_{1,i}))$,
$\hat{\mathit{L}}_{2}(\mathsf{LMP}(\hat{v}_{2,j}))$ and
$\mathit{L}_{3}(\mathsf{MP}(v_{3,k}))$, since
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i}]\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$.
Hence $|t|\leq|s|-1$. If $\hat{v}_{1,x}$, $\hat{v}_{2,y}$ and $v_{3,k}$ are
vertices satisfying $\hat{D}_{x,y,k}=|s|-1$, then
$\hat{D}_{i,j,k}=\hat{D}_{x,y,k}+1$. Note that such $\hat{v}_{1,x}$,
$\hat{v}_{2,y}$ and $v_{3,k}$ always exist.

      4. (d)

If
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})=\emptyset$,
then this case is the same as Case 1d.

The above arguments lead us to the following recurrence:

$\displaystyle\hat{D}_{i,j,k}=$
$\displaystyle\begin{cases}\delta\\!+\\!\max\left(\left\\{\hat{D}_{x,y,k}~{}\middle|~{}\begin{array}[]{l}(\hat{v}_{1,x},\hat{v}_{1,i})\\!\in\\!\hat{E}_{1},\\\
(\hat{v}_{2,y},\hat{v}_{2,j})\\!\in\\!\hat{E}_{2}\end{array}\right\\}\cup\\!\\{0\\}\right)&\begin{array}[]{l}\mbox{if
$k=0$ and}\\\
\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset;\end{array}\\\
\max\\!\left(\\!\begin{array}[]{l}\\{\hat{D}_{x,j,k}\mid{(\hat{v}_{1,x},\hat{v}_{1,i})\\!\in\\!\hat{E}_{1}}\\}\cup{}\\\
\\{\hat{D}_{i,y,k}\\!\mid\\!{(\hat{v}_{2,y},\hat{v}_{2,j})\\!\in\\!\hat{E}_{2}}\\}\cup\\{0\\}\\\
\end{array}\\!\right)&\begin{array}[]{l}\mbox{if $k=0$ and}\\\
\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})=\emptyset;\end{array}\\\
\delta\\!+\\!\max\\!\left(\\!\left\\{\hat{D}_{x,y,z}\\!~{}\middle|~{}\\!\begin{array}[]{l}(\hat{v}_{1,x},\hat{v}_{1,i})\\!\in\\!\hat{E}_{1},\\\
(\hat{v}_{2,y},\hat{v}_{2,j})\\!\in\\!\hat{E}_{2},\\\
(v_{3,z},v_{3,k})\\!\in\\!E_{3}\\\ \mbox{or
}z=0\end{array}\right\\}\cup\\{\gamma\\}\\!\right)&\begin{array}[]{l}\mbox{if
$k>0$ and}\\\
\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}([v_{3,k}])\\}\\\
\neq\emptyset;\end{array}\\\
\max\\!\left(\\!\left\\{\\!\delta+\hat{D}_{x,y,k}\\!~{}\middle|~{}\\!\begin{array}[]{l}(\hat{v}_{1,x},\hat{v}_{1,i})\\!\in\\!\hat{E}_{1},\\\
(\hat{v}_{2,y},\hat{v}_{2,j})\\!\in\\!\hat{E}_{2}\end{array}\\!\right\\}\cup\\{-\infty\\}\\!\right)&\begin{array}[]{l}\mbox{if
$k>0$,}\\\
\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}\\\
=\emptyset,\mbox{ and
}\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\\!\cap\\!\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\\!\neq\\!\emptyset;\end{array}\\\
\max\\!\left(\\!\begin{array}[]{l}\\{\hat{D}_{x,j,k}\mid{(\hat{v}_{1,x},\hat{v}_{1,i})\\!\in\\!\hat{E}_{1}}\\}\cup{}\\\
\\{\hat{D}_{i,y,k}\\!\mid\\!{(\hat{v}_{2,y},\hat{v}_{2,j})\\!\in\\!\hat{E}_{2}}\\}\cup\\{-\infty\\}\end{array}\\!\right)&\mbox{otherwise},\end{cases}$

where

$\displaystyle\delta$ $\displaystyle=$
$\displaystyle\begin{cases}\infty&\mbox{if both
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})$ and
$\hat{\mathit{L}}_{2}(\hat{v}_{2,j})$ are cyclic vertices;}\\\
1&\mbox{otherwise},\end{cases}$ $\displaystyle\gamma$ $\displaystyle=$
$\displaystyle\begin{cases}0&\begin{array}[]{l}\mbox{if $\hat{v}_{1,i}$ does
not have in-coming edges at all or $\hat{v}_{2,j}$ does not have}\\\ \mbox{in-
coming edges at all, and $v_{3,k}$ does not have in-coming
edges};\end{array}\\\ -\infty&\mbox{otherwise}.\end{cases}$

In the above recurrence, we use a convention that $\infty+(-\infty)=-\infty$.

We perform preprocessing which transforms $G_{1}$ and $G_{2}$ into
$\hat{G}_{1}$ and $\hat{G}_{2}$ in $O(|E_{1}|+|E_{2}|)$ time with
$O(|V_{1}|+|V_{2}|)$ space, based on strongly connected components.

To examine the conditions in the above recurrence, we explicitly construct the
intersection of the character labels of the given vertices
$\hat{v}_{1,i}\in\hat{V_{1}}$, $\hat{v}_{2,j}\in\hat{V_{2}}$, and
$\hat{v}_{3,k}\in V_{3}$ by using balanced trees, as follows:

  * –

Checking whether
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})=\emptyset$
or $\neq\emptyset$: Let $\Sigma_{1}$ and $\Sigma_{2}$ be the sets of
characters that appear in $G_{1}$ and $G_{2}$, respectively. For every node
$\hat{v}_{1,i}\in\hat{V}_{1}$ of the transformed graph $\hat{G}_{1}$, we build
a balanced tree $\mathcal{T}_{i}$ which consists of the characters in
$\hat{\mathit{L}}_{1}(\hat{v}_{i})$. Since the total number of characters in
the original graph $G_{1}=(V_{1},E_{1})$ is equal to $|V_{1}|$, we can build
the balanced trees $\mathcal{T}_{i}$ for all $i$ in a total of
$O(|V_{1}|\log{|\Sigma_{1}|})$ time and $O(|V_{1}|)$ space. Then, for each
fixed $\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\in\hat{V}_{1}$, by using its
balanced tree, the intersection
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})$
can be computed in $O(|V_{2}|\log|\Sigma_{1}|)$ time for all
$\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\in V_{2}$. Therefore,
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})$
for all $1\leq i\leq|\hat{V}_{1}|$ and $1\leq j\leq|\hat{V}_{2}|$ can be
computed in $O(|V_{1}||V_{2}|\log|\Sigma_{1}|)$ total time.

  * –

Checking whether
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\mathit{L}_{3}(v_{3,k})=\emptyset$
or $\neq\emptyset$: While computing
$\Sigma_{i,j}=\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})$
in the above, we also build another balanced tree $\mathcal{T}_{i,j}$ which
consists of the characters in $\Sigma_{i,j}$ for every $1\leq
i\leq|\hat{V}_{1}|$ and $1\leq j\leq|\hat{V}_{2}|$. This can be done in
$O(|V_{1}||V_{2}|\log|\Sigma_{1}|)$ total time and $O(|V_{1}||V_{2}|)$ space.
Then, for each fixed $1\leq i\leq|\hat{V}_{1}|$ and $1\leq
j\leq|\hat{V}_{2}|$,
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\mathit{L}_{3}(v_{3,k})$
can be computed in a total of $O(|V_{3}|\log|\Sigma_{i,j}|)$ time. Therefore,
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\mathit{L}_{3}(v_{3,k})$
for all $1\leq i\leq|\hat{V}_{1}|$, $1\leq j\leq|\hat{V}_{2}|$ and, $1\leq
k\leq|V_{3}|$ can be computed in $O(|V_{1}||V_{2}||V_{3}|\log|\Sigma|)$ time.

Assuming that the above preprocessing for the conditions in the recurrence are
all done, we can compute $\hat{D}_{i,j,k}$ for all $1\leq i\leq|\hat{V}_{1}|$,
$1\leq j\leq|\hat{V}_{2}|$ and $1\leq k\leq|V_{3}|$ using dynamic programming
of size $O(|\hat{V}_{1}||\hat{V}_{2}||V_{3}|)$ in
$O(|\hat{E}_{1}||\hat{E}_{2}||E_{3}|)$ time, in a similar way to the acyclic
case for Theorem 1.

Overall, the total time complexity is
$O(|E_{1}|+|E_{2}|+|E_{3}|+|\hat{V}_{1}||\hat{V}_{2}|\log|\Sigma_{1}|+|\hat{V}_{1}||\hat{V}_{2}||V_{3}|\log|\Sigma|+|\hat{E}_{1}||\hat{E}_{2}||E_{3}|)\subseteq
O(|E_{1}||E_{2}||E_{3}|+|V_{1}||V_{2}||V_{3}|\log|\Sigma|)$.

The total space complexity is
$O(|V_{1}||V_{2}|+|\hat{V}_{1}||\hat{V}_{2}||V_{3}|)\subseteq
O(|V_{1}||V_{2}||V_{3}|)$. ∎

An example of computing $\hat{D}_{i,j,k}$ using dynamic programming is shown
in Figure 3.

Algorithm 2 in Appendix B shows a pseudo-code of our algorithm which solves
Problem 2 in the case where $G_{1}$ and $G_{2}$ can be cyclic and $G_{3}$ is
acyclic.

##  6 Conclusions and Open Questions

In this paper, we introduced the new problem of computing the SEQ-IC-LCS on
labeled graphs. We showed that when the all the input labeled graphs are
acyclic, the problem can be solved in $O(|E_{1}||E_{2}|||E_{3})$ time and
$O(|V_{1}||V_{2}||V_{3}|)$ space by a dynamic programming approach.
Furthermore, we extend our algorithm to a more general case where the two
target labeled graphs can contain cycles, and presented an efficient algorithm
that runs in $O(|E_{1}||E_{2}||E_{3}|+|V_{1}||V_{2}||V_{3}|\log{|\Sigma|})$
time and $O(|V_{1}||V_{2}||V_{3}|)$ space.

Interesting open questions are whether one can extend the framework of our
methods to the other variants STR-IC/EC-LCS and SEQ-EC-LCS of the constrained
LCS problems in the case of labeled graph inputs. We believe that SEQ-EC-LCS
for labeled graphs can be solved by similar methods to our SEQ-IC-LCS methods,
within the same bounds.

## Acknowledgments

This work was supported by JSPS KAKENHI Grant Numbers JP21K17705 (YN),
JP23H04386 (YN), JP22H03551 (SI), and JP23K18466 (SI).

## References

  * [1] A. Abboud, A. Backurs, and V. V. Williams.  Tight hardness results for LCS and other sequence similarity measures.  In FOCS 2015, pages 59–78, 2015.
  * [2] A. Amir, M. Lewenstein, and N. Lewenstein.  Pattern matching in hypertext.  In WADS 1997, volume 1272 of LNCS, pages 160–173, 1997.
  * [3] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter, and D. Vrgoc.  Foundations of modern query languages for graph databases.  ACM Comput. Surv., 50(5):68:1–68:40, 2017.
  * [4] K. Aoyama, Y. Nakashima, T. I, S. Inenaga, H. Bannai, and M. Takeda.  Faster online elastic degenerate string matching.  In CPM 2018, volume 105 of LIPIcs, pages 9:1–9:10, 2018\.
  * [5] A. N. Arslan.  Regular expression constrained sequence alignment.  Journal of Discrete Algorithms, 5(4):647–661, 2007.  Selected papers from Combinatorial Pattern Matching 2005.
  * [6] A. N. Arslan and Ö. Egecioglu.  Algorithms for the constrained longest common subsequence problems.  Int. J. Found. Comput. Sci., 16(6):1099–1109, 2005.
  * [7] G. Bernardini, P. Gawrychowski, N. Pisanti, S. P. Pissis, and G. Rosone.  Elastic-degenerate string matching via fast matrix multiplication.  SIAM J. Comput., 51(3):549–576, 2022.
  * [8] G. Bernardini, N. Pisanti, S. P. Pissis, and G. Rosone.  Approximate pattern matching on elastic-degenerate text.  Theor. Comput. Sci., 812:109–122, 2020.
  * [9] K. Bringmann and M. Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In FOCS 2015, pages 79–97, 2015.
  * [10] M. Cáceres.  Parameterized algorithms for string matching to DAGs: Funnels and beyond.  In CPM 2023, volume 259 of LIPIcs, pages 7:1–7:19, 2023\.
  * [11] Y.-C. Chen and K.-M. Chao.  On the generalized constrained longest common subsequence problems.  Journal of Combinatorial Optimization, 21(3):383–392, Apr 2011\.
  * [12] F. Y. Chin, A. D. Santis, A. L. Ferrara, N. Ho, and S. Kim.  A simple algorithm for the constrained sequence problems.  Information Processing Letters, 90(4):175 – 179, 2004.
  * [13] J. Conklin.  Hypertext: An introduction and survey.  IEEE Computer, 20(9):17–41, 1987.
  * [14] T. C. P.-G. Consortium.  Computational pan-genomics: status, promises and challenges.  Briefings in Bioinformatics, 19(1):118–135, 2016.
  * [15] S. Deorowicz.  Quadratic-time algorithm for a string constrained lcs problem.  Information Processing Letters, 112(11):423 – 426, 2012.
  * [16] M. Equi, R. Grossi, V. Mäkinen, and A. I. Tomescu.  On the complexity of string matching for graphs.  In ICALP 2019, volume 132 of LIPIcs, pages 55:1–55:15, 2019\.
  * [17] M. Equi, V. Mäkinen, and A. I. Tomescu.  Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails.  In SOFSEM 2021, volume 12607 of Lecture Notes in Computer Science, pages 608–622, 2021.
  * [18] R. Grossi, C. S. Iliopoulos, C. Liu, N. Pisanti, S. P. Pissis, A. Retha, G. Rosone, F. Vayani, and L. Versari.  On-line pattern matching on similar texts.  In CPM 2017, volume 78 of LIPIcs, pages 9:1–9:14, 2017\.
  * [19] C. S. Iliopoulos, R. Kundu, and S. P. Pissis.  Efficient pattern matching in elastic-degenerate strings.  Inf. Comput., 279:104616, 2021.
  * [20] G. Kucherov, T. Pinhas, and M. Ziv-Ukelson.  Regular language constrained sequence alignment revisited.  In IWOCA 2011, pages 404–415, 2011.
  * [21] U. Manber and S. Wu.  Approximate string matching with arbitrary costs for text and hypertext.  In Proc. IAPR, pages 22–33, 1992.
  * [22] G. Navarro.  Improved approximate pattern matching on hypertext.  Theoretial Computer Science, 237(1–2):455–463, 2000.
  * [23] K. Park and D. K. Kim.  String matching in hypertext.  In Proc. CPM’95, pages 318–329, 1995.
  * [24] K. Shimohira, S. Inenaga, H. Bannai, and M. Takeda.  Computing longest common substring/subsequence of non-linear texts.  In PSC 2011, pages 197–208, 2011.
  * [25] Y.-T. Tsai.  The constrained longest common subsequence problem.  Information Processing Letters, 88(4):173 – 176, 2003.
  * [26] R. A. Wagner and M. J. Fischer.  The string-to-string correction problem.  J. ACM, 21(1):168–173, Jan. 1974.
  * [27] L. Wang, X. Wang, Y. Wu, and D. Zhu.  A dynamic programming solution to a generalized LCS problem.  Inf. Process. Lett., 113(19-21):723–728, 2013.
  * [28] Y. Yonemoto, Y. Nakashima, S. Inenaga, and H. Bannai.  Space-efficient STR-IC-LCS computation.  In SOFSEM 2023, volume 13878 of LNCS, pages 372–384, 2023\.

##  Appendix A Pseudo-code for SEQ-IC-LCS of Acyclic Labeled Graphs

Input: Acyclic labeled graphs
$G_{1}=(V_{1},E_{1},\mathit{L}_{1}),G_{2}=(V_{2},E_{2},\mathit{L}_{2}),G_{3}=(V_{3},E_{3},\mathit{L}_{3})$

Output: Length of a longest string in the set

$\\{z\mid\exists~{}q\in\mathit{L}_{3}(\mathsf{MP}(G_{3}))\mbox{ such that
}q\in\mathsf{Subseq}(z)\mbox{ and
}z\in\mathsf{Subseq}(G_{1})\cap\mathsf{Subseq}(G_{2})\\}$

1 topological sort $G_{1}$, $G_{2}$, and $G_{3}$;

2 $V_{\mathrm{end}}\leftarrow$ the vertices of $G_{3}$ which have no out-going
edges;

3 $n\leftarrow|V_{1}|$; $m\leftarrow|V_{2}|$; $l\leftarrow|V_{3}|+1$;

4 Let $D$ be an $n\times m\times l$ integer array;

5

6for  _$i\leftarrow 1$ to $n$_ do

7 for  _$j\leftarrow 1$ to $m$_ do

$D_{i,j,0}\leftarrow D_{i,j}$ ;

// Algorithm by Shimohira et al.

8

9

10

11for  _$i\leftarrow 1$ to $n$_ do

12 for  _$j\leftarrow 1$ to $m$_ do

13 for  _$k\leftarrow 1$ to $l$_ do

14 if
_$\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})=\mathit{L}_{3}(v_{3,k})$_
then

15 if  _there are no in-coming edges to $v_{3,k}$_ then $D_{i,j,k}\leftarrow
1$ ;

16 else $D_{i,j,k}\leftarrow-\infty$ ;

17 forall  _$v_{1,x}$ s.t. $(v_{1,x},v_{1,i})\in E_{1}$_ do

18 forall  _$v_{2,y}$ s.t. $(v_{2,y},v_{2,j})\in E_{2}$_ do

19 if  _there are no in-coming edges to $v_{3,k}$_ then

20 if  _$D_{i,j,k} <1+D_{x,y,0}$_ then

21 $D_{i,j,k}\leftarrow 1+D_{x,y,0}$;

22

23

24 else

25 forall  _$v_{3,z}$ s.t. $(v_{3,z},v_{3,k})\in E_{3}$_ do

26 if  _$D_{i,j,k} <1+D_{x,y,z}$_ then $D_{i,j,k}\leftarrow 1+D_{x,y,z}$ ;

27

28

29

30

31

32 else if
_$\mathit{L}_{1}(v_{1,i})=\mathit{L}_{2}(v_{2,j})\neq\mathit{L}_{3}(v_{3,k})$_
then

33 $D_{i,j,k}\leftarrow-\infty$;

34 forall  _$v_{1,x}$ s.t. $(v_{1,x},v_{1,i})\in E_{1}$_ do

35 forall  _$v_{2,y}$ s.t. $(v_{2,y},v_{2,j})\in E_{2}$_ do

36 if  _$D_{i,j,k} <1+D_{x,y,k}$_ then $D_{i,j,k}\leftarrow 1+D_{x,y,k}$ ;

37

38

39

40 else

41 $D_{i,j,k}\leftarrow-\infty$;

42 forall  _$v_{1,x}$ s.t. $(v_{1,x},v_{1,i})\in E_{1}$_ do

43 if  _$D_{i,j,k} <D_{x,j,k}$_ then $D_{i,j,k}\leftarrow D_{x,j,k}$ ;

44

45 forall  _$v_{2,y}$ s.t. $(v_{2,y},v_{2,j})\in E_{2}$_ do

46 if  _$D_{i,j,k} <D_{i,y,k}$_ then $D_{i,j,k}\leftarrow D_{i,y,k}$ ;

47

48

49

50

51

52return $\max\\{D_{i,j,k}\mid 1\leq i\leq n,1\leq j\leq m,k\in
V_{\mathrm{end}}\\}$;

Algorithm 1 Computie the SEQ-IC-LCS length of acyclic labeled graphs

##  Appendix B Pseudo-code for SEQ-IC-LCS of Cyclic Labeled Graphs

Input: Labeled graphs $G_{1}=(V_{1},E_{1},\mathit{L}_{1})$,
$G_{2}=(V_{2},E_{2},\mathit{L}_{2})$, and acyclic labeled graph
$G_{3}=(V_{3},E_{3},\mathit{L}_{3})$

Output: Length of a longest string in the set

$\\{z\mid\exists~{}q\in\mathit{L}_{3}(\mathsf{MP}(G_{3}))\mbox{ such that
}q\in\mathsf{Subseq}(z)\mbox{ and
}z\in\mathsf{Subseq}(G_{1})\cap\mathsf{Subseq}(G_{2})\\}$

1

2$G^{\prime}_{1}\leftarrow$ Graph obtained from $G_{1}$ based on its strongly
connected components;

3 $G^{\prime}_{2}\leftarrow$ Graph obtained from $G_{2}$ based on its strongly
connected components;

4 topological sort $\hat{G}_{1}$, $\hat{G}_{2}$, $G_{3}$;

5 $V_{\mathrm{end}}\leftarrow$ the vertices of $G_{3}$ which have no out-going
edges;

6 Let $\hat{D}$ be a $|\hat{V}_{1}|\times|\hat{V}_{2}|\times(|V_{3}|+1)$
integer array;

7 Let $M$ be a $|\hat{V}_{1}|\times|\hat{V}_{2}|$ integer array;

8 for  _$i\leftarrow 1$ to $|\hat{V}_{1}|$_ do

9 for  _$j\leftarrow 1$ to $|\hat{V}_{2}|$_ do

10 if
_$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\neq\emptyset$_
then $M_{i,j}\leftarrow 1$ ;

11 else $M_{i,j}\leftarrow 0$ ;

12

13

14Let $S$ be a $|\hat{V}_{1}|\times|\hat{V}_{2}|$ array to store pointers to
balanced trees;

15 Let $B$ be a $|\hat{V}_{1}|$ array to store pointers to balanced trees;

16

17for  _$i\leftarrow 1$ to $|\hat{V}_{1}|$_ do

18 $B_{i}\leftarrow$ balanced tree of characters in
$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})$;

19

20for  _$i\leftarrow 1$ to $|\hat{V}_{1}|$_ do

21 for  _$j\leftarrow 1$ to $|\hat{V}_{2}|$_ do

22 if  _some characters in $\hat{\mathit{L}}_{2}(\hat{v}_{2,j})$ are in
$B_{i}$_ then

23 $M_{i,j}\leftarrow 1$;

24 $S_{i,j}\leftarrow$ balanced trees of all characters in
$B_{i}\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})$;

25

26 else $M_{i,j}\leftarrow 0$ ;

27

28

29

Compute $\hat{D}_{i,j,0}$; ;

// Algorithm 3

30

31for  _$i\leftarrow 1$ to $|\hat{V}_{1}|$_ do

32 for  _$j\leftarrow 1$ to $|\hat{V}_{2}|$_ do

33 for  _$k\leftarrow 1$ to $|V_{3}|$_ do

34 if  _$(\hat{v}_{1,i},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,j},\hat{v}_{2,j})\in\hat{E}_{2}$_ then

Compute $\hat{D}_{i,j,k}$ if $(\hat{v}_{1,i},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,j},\hat{v}_{2,j})\in\hat{E}_{2}$ ;

// Algorithm 4

35

36 else

Compute $\hat{D}_{i,j,k}$ if $(\hat{v}_{1,i},\hat{v}_{1,i})\notin\hat{E}_{1}$
or $(\hat{v}_{2,j},\hat{v}_{2,j})\notin\hat{E}_{2}$ ;

// Algorithm 5

37

38

39

40

41

42return $\max\\{\hat{D}_{i,j,k}\mid 1\leq i\leq|\hat{V}_{1}|,1\leq
j\leq|\hat{V}_{2}|,k\in V_{\mathrm{end}}\\}$;

Algorithm 2 Compute the SEQ-IC-LCS length of cyclic labeled graphs

1 for  _$i\leftarrow 1$ to $|\hat{V}_{1}|$_ do

2 for  _$j\leftarrow 1$ to $|\hat{V}_{2}|$_ do

3 if  _$(\hat{v}_{1,i},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,j},\hat{v}_{2,j})\in\hat{E}_{2}$_ then

4 if  _$M_{i,j}=1$_ then

5 $\hat{D}_{i,j,k}\leftarrow\infty$;

6

7 else

8 $\hat{D}_{i,j,0}\leftarrow 0$;

9 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

10 if  _$\hat{D}_{i,j,0} <\hat{D}_{x,j,0}$_ then

11 $\hat{D}_{i,j,0}\leftarrow\hat{D}_{x,j,0}$;

12

13

14 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

15 if  _$\hat{D}_{i,j,0} <\hat{D}_{i,y,0}$_ then

16 $\hat{D}_{i,j,0}\leftarrow\hat{D}_{i,y,0}$;

17

18

19

20

21 else

22 if  _$M_{i,j}=1$_ then

23 $\hat{D}_{i,j,k}\leftarrow 1$;

24 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

25 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

26 if  _$\hat{D}_{i,j,0} <1+\hat{D}_{x,y,0}$_ then

27 $\hat{D}_{i,j,0}\leftarrow 1+\hat{D}_{x,y,0}$;

28

29

30

31

32 else

33 $\hat{D}_{i,j,0}\leftarrow 0$;

34 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

35 if  _$\hat{D}_{i,j,0} <\hat{D}_{x,j,0}$_ then

36 $\hat{D}_{i,j,0}\leftarrow\hat{D}_{x,j,0}$;

37

38

39 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

40 if  _$\hat{D}_{i,j,0} <\hat{D}_{i,y,0}$_ then

41 $\hat{D}_{i,j,0}\leftarrow\hat{D}_{i,y,0}$;

42

43

44

45

46

47

Algorithm 3 Compute $\hat{D}_{i,j,0}$

1 if
_$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}\neq\emptyset$_
then

2 $\hat{D}_{i,j,k}\leftarrow-\infty$;

3 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

4 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

5 if  _there are no in-coming edges to $v_{3,k}$_ then

6 if  _$\hat{D}_{x,y,0}\neq-\infty$_ then

7 $\hat{D}_{i,j,k}\leftarrow\infty$;

8

9

10 else

11 forall  _$\hat{v}_{3,z}$ such that
$(\hat{v}_{3,z},\hat{v}_{3,k})\in\hat{E}_{3}$_ do

12 if  _$\hat{D}_{x,y,z}\neq-\infty$_ then

13 $\hat{D}_{i,j,k}\leftarrow\infty$;

14

15

16

17

18

19

20else if  _$M_{i,j}=1$_ then

21 $\hat{D}_{i,j,k}\leftarrow-\infty$;

22 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

23 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

24 if  _$\hat{D}_{x,y,k}\neq-\infty$_ then

25 $\hat{D}_{i,j,k}\leftarrow\infty$;

26

27

28

29

30else

31 $\hat{D}_{i,j,k}\leftarrow-\infty$;

32 forall  _$v_{1,x}$ such that $(v_{1,x},v_{1,i})\in E_{1}$_ do

33 if  _$\hat{D}_{i,j,k} <\hat{D}_{x,j,k}$_ then

34 $\hat{D}_{i,j,k}\leftarrow\hat{D}_{x,j,k}$;

35

36

37 forall  _$v_{2,y}$ such that $(v_{2,y},v_{2,j})\in E_{2}$_ do

38 if  _$\hat{D}_{i,j,k} <\hat{D}_{i,y,k}$_ then

39 $\hat{D}_{i,j,k}\leftarrow\hat{D}_{i,y,k}$;

40

41

42

Algorithm 4 Compute $\hat{D}_{i,j,k}$ when
$(\hat{v}_{1,i},\hat{v}_{1,i})\in\hat{E}_{1}$ and
$(\hat{v}_{2,j},\hat{v}_{2,j})\in\hat{E}_{2}$

1 if
_$\hat{\mathit{L}}_{1}(\hat{v}_{1,i})\cap\hat{\mathit{L}}_{2}(\hat{v}_{2,j})\cap\\{\mathit{L}_{3}(v_{3,k})\\}\neq\emptyset$_
then

2 if  _there are no in-coming edges to $v_{3,k}$_ then

3 $\hat{D}_{i,j,k}\leftarrow 1$;

4

5 else

6 $\hat{D}_{i,j,k}\leftarrow-\infty$;

7

8 forall  _$\hat{v}_{1,x}$ such that $(\hat{v}_{1,x},v_{1,i})\in\hat{E}_{1}$_
do

9 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

10 if  _there are no in-coming edges to $v_{3,k}$_ then

11 if  _$\hat{D}_{i,j,k} <1+\hat{D}_{x,y,0}$_ then

12 $\hat{D}_{i,j,k}\leftarrow 1+\hat{D}_{x,y,0}$;

13

14

15 else

16 forall  _$v_{3,z}$ such that $(v_{3,z},v_{3,k})\in E_{3}$_ do

17 if  _$\hat{D}_{i,j,k} <1+\hat{D}_{x,y,z}$_ then

18 $\hat{D}_{i,j,k}\leftarrow 1+\hat{D}_{x,y,z}$;

19

20

21

22

23

24

25else if  _$M_{i,j}=1$_ then

26 $\hat{D}_{i,j,k}\leftarrow-\infty$;

27 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

28 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

29 if  _$\hat{D}_{i,j,k} <1+\hat{D}_{x,y,k}$_ then

30 $\hat{D}_{i,j,k}\leftarrow 1+\hat{D}_{x,y,k}$;

31

32

33

34

35else

36 $\hat{D}_{i,j,k}\leftarrow-\infty$;

37 forall  _$\hat{v}_{1,x}$ such that
$(\hat{v}_{1,x},\hat{v}_{1,i})\in\hat{E}_{1}$_ do

38 if  _$\hat{D}_{i,j,k} <\hat{D}_{x,j,k}$_ then

39 $\hat{D}_{i,j,k}\leftarrow\hat{D}_{x,j,k}$;

40

41

42 forall  _$\hat{v}_{2,y}$ such that
$(\hat{v}_{2,y},\hat{v}_{2,j})\in\hat{E}_{2}$_ do

43 if  _$\hat{D}_{i,j,k} <\hat{D}_{i,y,k}$_ then

44 $\hat{D}_{i,j,k}\leftarrow\hat{D}_{i,y,k}$;

45

46

47

Algorithm 5 Compute $\hat{D}_{i,j,k}$ when
$(\hat{v}_{1,i},\hat{v}_{1,i})\notin\hat{E}_{1}$ or
$(\hat{v}_{2,j},\hat{v}_{2,j})\notin\hat{E}_{2}$